Algorithme pour trouver les 10 principaux termes de recherche

Je me prépare actuellement à une entrevue, et cela m’a rappelé une question qui m’a été une fois posée dans une interview précédente et qui ressemblait à ceci:

«Il vous a été demandé de concevoir des logiciels pour afficher en permanence les 10 principaux termes de recherche sur Google. Vous avez access à un stream fournissant un stream de termes de recherche en temps réel sans fin sur Google. vous utiliseriez pour l’implémenter Vous devez concevoir deux variantes:

(i) Affiche les 10 principaux termes de recherche de tous les temps (c.-à-d. depuis que vous avez commencé à lire le stream).

(ii) Afficher uniquement les 10 principaux termes de recherche du mois écoulé, mis à jour toutes les heures.

Vous pouvez utiliser une approximation pour obtenir la liste des 10 meilleurs, mais vous devez justifier vos choix. ”
J’ai bombardé lors de cette interview et je n’ai toujours aucune idée de la manière de l’implémenter.

La première partie demande les 10 éléments les plus fréquents dans une sous-séquence en croissance continue d’une liste infinie. J’ai examiné les algorithmes de sélection, mais je n’ai trouvé aucune version en ligne pour résoudre ce problème.

La seconde partie utilise une liste finie, mais en raison de la grande quantité de données en cours de traitement, vous ne pouvez pas vraiment stocker le mois entier des termes de recherche en mémoire et calculer un histogramme toutes les heures.

Le problème est rendu plus difficile par le fait que la liste des 10 meilleurs est continuellement mise à jour. Vous devez donc calculer votre top 10 sur une fenêtre glissante.

Des idées?

Eh bien, cela ressemble à beaucoup de données, avec un coût peut-être prohibitif pour stocker toutes les fréquences. Lorsque la quantité de données est si importante que nous ne pouvons pas espérer tout stocker, nous entrons dans le domaine des algorithmes de stream de données .

Livre utile dans ce domaine: Muthukrishnan – “Data Streams: Algorithms and Applications”

Référence étroitement liée au problème que j’ai choisi parmi ceux-ci: Manku, Motwani – “Nombre approximatif de fréquences sur les stream de données” [pdf]

Au fait, Motwani, de Stanford, (edit) était un auteur du très important livre “Algorithmes aléatoires” . Le 11ème chapitre de ce livre traite de ce problème . Edit: Désolé, mauvaise référence, ce chapitre particulier est sur un problème différent. Après vérification, je recommande plutôt la section 5.1.2 du livre de Muthukrishnan , disponible en ligne.

Heh, belle question d’entretien.

Aperçu de l’estimation de fréquence

Certains algorithmes bien connus peuvent fournir des estimations de fréquence pour un tel stream en utilisant une quantité de stockage fixe. One is Frequent, de Misra et Gries (1982). À partir d’une liste de n éléments, il trouve tous les éléments qui surviennent plus de n / k fois, en utilisant les compteurs k – 1 . Il s’agit d’une généralisation de l’algorithme majoritaire de Boyer et Moore (Fischer-Salzberg, 1982), où k est égal à 2. Les algorithmes LossyCounting (2002) et SpaceSaving (2005) de Manku et Motwani ont des besoins en espace similaires conditions.

La chose importante à retenir est que ces algorithmes ne peuvent fournir que des estimations de fréquence. Plus précisément, l’estimation de Misra-Gries peut sous-estimer la fréquence réelle par (n / k) éléments.

Supposons que vous disposiez d’un algorithme permettant d’identifier positivement un élément uniquement s’il se produit plus de 50% du temps. Nourrissez cet algorithme un stream de N éléments distincts, puis ajoutez un autre N – 1 copies d’un élément, x , pour un total de 2N – 1 éléments. Si l’algorithme vous indique que x dépasse 50% du total, il doit avoir été dans le premier stream; si ce n’est pas le cas, x n’était pas dans le stream initial. Pour que l’algorithme puisse effectuer cette détermination, il doit stocker le stream initial (ou un résumé proportionnel à sa longueur)! Nous pouvons donc nous prouver que l’espace requirejs par un tel algorithme “exact” serait Ω ( N ).

Au lieu de cela, ces algorithmes de fréquence décrits ici fournissent une estimation, identifiant tout élément qui dépasse le seuil, ainsi que certains éléments qui tombent en dessous d’une certaine marge. Par exemple, l’algorithme Majority , utilisant un seul compteur, donnera toujours un résultat; si un élément dépasse 50% du stream, il sera trouvé. Mais cela peut aussi vous donner un élément qui ne se produit qu’une fois. Vous ne sauriez pas faire un deuxième passage sur les données (en utilisant, encore une fois, un seul compteur, mais en ne recherchant que cet élément).

L’algorithme fréquent

Voici une description simple de l’algorithme fréquent de Misra-Gries. Demaine (2002) et d’autres ont optimisé l’algorithme, mais cela vous donne l’essentiel.

Spécifiez la fraction de seuil, 1 / k ; tout élément survenant plus de n / k fois sera trouvé. Créer une carte vide (comme un arbre rouge-noir); les clés seront des termes de recherche, et les valeurs seront un compteur pour ce terme.

  1. Regardez chaque élément dans le stream.
  2. Si le terme existe dans la carte, incrémentez le compteur associé.
  3. Sinon, si la carte est inférieure à k – 1 entrées, ajoutez le terme à la carte avec un compteur de un.
  4. Cependant, si la carte a déjà k – 1 entrées, décrémentez le compteur dans chaque entrée. Si un compteur atteint zéro pendant ce processus, supprimez-le de la carte.

Notez que vous pouvez traiter une quantité infinie de données avec un volume de stockage fixe (uniquement la carte de taille fixe). La quantité de stockage requirejse dépend uniquement du seuil d’intérêt et la taille du stream n’a pas d’importance.

Comptage des recherches

Dans ce contexte, vous stockez peut-être une heure de recherche et effectuez ce processus sur les données de cette heure. Si vous pouvez passer une seconde fois sur le journal de recherche de cette heure, vous pouvez obtenir un décompte exact des occurrences des principaux “candidats” identifiés lors de la première passe. Ou, peut-être est-il acceptable de faire un seul passage, et de signaler tous les candidats, sachant que tout élément qui devrait être là est inclus, et tous les extras ne sont que du bruit qui disparaîtra dans l’heure suivante.

Les candidats qui dépassent réellement le seuil d’intérêt sont stockés sous forme de résumé. Gardez un mois de ces résumés, en jetant les plus anciens chaque heure, et vous auriez une bonne approximation des termes de recherche les plus courants.

C’est l’un des projets de recherche que je suis en train de traverser. L’exigence est presque identique à la vôtre et nous avons développé de bons algorithmes pour résoudre le problème.

L’entrée

L’entrée est un stream sans fin de mots anglais ou de phrases (nous les appelons des tokens ).

Le résultat

  1. Sortie des N meilleurs jetons que nous avons vus jusqu’ici (de tous les jetons que nous avons vus!)
  2. Affiche les N premiers jetons dans une fenêtre historique, par exemple, le dernier jour ou la semaine dernière.

Une application de cette recherche est de trouver le sujet d’actualité ou les tendances du sujet sur Twitter ou Facebook. Nous avons un robot d’exploration sur le site Web, qui génère un stream de mots, qui alimentera le système. Le système affichera alors les mots ou les phrases de la fréquence la plus élevée, soit globalement, soit historiquement. Imaginez-vous ces dernières semaines que l’expression “Coupe du monde” apparaîtrait plusieurs fois sur Twitter. Il en va de même pour “Paul le poulpe”. 🙂

Chaîne en entiers

Le système a un identifiant entier pour chaque mot. Bien qu’il y ait presque des mots possibles sur Internet, mais après avoir accumulé un grand nombre de mots, la possibilité de trouver de nouveaux mots devient de plus en plus faible. Nous avons déjà trouvé 4 millions de mots différents et nous leur avons atsortingbué un identifiant unique. L’ensemble de ces données peut être chargé en mémoire sous forme de table de hachage, consommant environ 300 Mo de mémoire. (Nous avons implémenté notre propre table de hachage. L’implémentation de Java nécessite une énorme surcharge de mémoire)

Chaque phrase peut alors être identifiée comme un tableau d’entiers.

Ceci est important car le sorting et les comparaisons sur des nombres entiers sont beaucoup plus rapides que sur des chaînes.

Données d’archive

Le système conserve les données d’archive pour chaque jeton. Fondamentalement, ce sont des paires de (Token, Frequency) . Cependant, la table qui stocke les données serait si énorme que nous devions partitionner physiquement la table. Une fois le schéma de partition basé sur les ngrams du jeton. Si le jeton est un seul mot, c’est 1gram. Si le jeton est une phrase de deux mots, c’est 2gram. Et ça continue. À peu près à 4 grammes, nous avons 1 milliard d’enregistrements, avec une taille de table d’environ 60 Go.

Traitement des stream entrants

Le système absorbe les phrases entrantes jusqu’à ce que la mémoire soit pleinement utilisée (Ya, nous avons besoin d’un MemoryManager). Après avoir pris N phrases et stocké en mémoire, le système s’arrête et commence à numéroter chaque phrase en mots et en phrases. Chaque jeton (mot ou phrase) est compté.

Pour les jetons très fréquents, ils sont toujours conservés en mémoire. Pour les jetons moins fréquents, ils sont sortingés en fonction des identifiants (souvenez-vous que nous traduisons la chaîne en un tableau d’entiers) et sérialisés dans un fichier disque.

(Cependant, pour votre problème, puisque vous ne comptez que des mots, vous ne pouvez mettre en mémoire que toutes les cartes de mots-fréquences. Une structure de données soigneusement conçue consum 300 Mo de mémoire pour 4 millions de mots différents. représentent des chaînes), et c’est bien acceptable.

Pendant ce temps, il y aura un autre processus qui sera activé dès qu’il trouvera un fichier disque généré par le système, puis commencera à le fusionner. Étant donné que le fichier de disque est sortingé, la fusion prend un processus similaire au sorting par fusion. Certaines conceptions doivent également être sockets en compte, car nous voulons éviter que trop de recherches aléatoires sur disque ne soient effectuées. L’idée est d’éviter la lecture (processus de fusion) / écriture (sortie système) en même temps, et de laisser le processus de fusion lire un disque en écrivant sur un autre disque. Ceci est similaire à la mise en œuvre d’un locking.

Fin de la journée

À la fin de la journée, le système disposera de nombreux jetons fréquents avec une fréquence stockée en mémoire et de nombreux autres jetons moins fréquents stockés dans plusieurs fichiers de disque (et chaque fichier est sortingé).

Le système vide la carte en mémoire dans un fichier disque (sortingez-le). Maintenant, le problème devient la fusion d’un ensemble de fichiers de disque sortingés. En utilisant un processus similaire, nous obtiendrions un fichier disque sortingé à la fin.

Ensuite, la dernière tâche consiste à fusionner le fichier de disque sortingé dans la firebase database d’archive. Dépend de la taille de la firebase database d’archive, l’algorithme fonctionne comme ci-dessous s’il est assez grand:

  for each record in sorted disk file update archive database by increasing frequency if rowcount == 0 then put the record into a list end for for each record in the list of having rowcount == 0 insert into archive database end for 

L’intuition est qu’après un certain temps, le nombre d’insertion deviendra de plus en plus petit. De plus en plus d’opérations seront mises à jour uniquement. Et cette mise à jour ne sera pas pénalisée par index.

J’espère que toute cette explication pourrait aider. 🙂

Vous pouvez utiliser une table de hachage combinée à un arbre de recherche binary . Implémentez un dictionnaire qui vous indique combien de fois chaque terme de recherche a été recherché.

Évidemment, itérer toutes les heures la table de hachage pour obtenir le top 10 est très mauvais. Mais nous parlons de Google, donc vous pouvez supposer que les dix premiers auront tous, disons plus de 10 000 visites (c’est probablement un nombre beaucoup plus important). Donc, chaque fois qu’un nombre de termes de recherche dépasse 10 000, insérez-le dans le BST. Ensuite, toutes les heures, il suffit d’obtenir les 10 premières de la BST, qui doivent contenir relativement peu d’inscriptions.

Cela résout le problème du top-10-of-all-time.


La partie la plus délicate concerne le fait qu’un terme occupe une place dans le rapport mensuel (par exemple, le «débordement de stack» peut atteindre 50 000 visites au cours des deux derniers mois, mais seulement 10 000 le mois dernier, alors que «amazon» en a 40). 000 pour les deux derniers mois, mais 30 000 pour le mois dernier.Vous voulez que “amazon” arrive avant “débordement de stack” dans votre rapport mensuel). Pour ce faire, je stockerais, pour tous les termes de recherche majeurs (supérieurs à 10 000 recherches), une liste de 30 jours vous indiquant combien de fois ce terme a été recherché chaque jour. La liste fonctionnerait comme une queue FIFO: vous supprimez le premier jour et vous en insérez un nouveau chaque jour (ou chaque heure, mais vous devrez peut-être stocker plus d’informations, ce qui signifie plus de mémoire / espace). ça, sinon optez pour cette “approximation” dont ils parlent).

Cela semble être un bon début. Vous pouvez alors vous soucier de l’élagage des termes ayant plus de 10 000 visites, mais vous n’en avez pas eu beaucoup depuis longtemps.

cas i)

Maintenir une table de hachage pour tous les mots-clés, ainsi qu’une liste des dix premiers sortingés distincte de la table de hachage. Chaque fois qu’une recherche se produit, incrémentez l’élément approprié dans la table de hachage et vérifiez si cet élément devrait maintenant être remplacé par le 10ème élément de la liste des dix premiers.

O (1) recherche de la liste des dix premiers, et max O (log (n)) insertion dans la table de hachage (en supposant des collisions gérées par un arbre binary à équilibrage automatique).

case ii) Au lieu de maintenir une énorme table de hachage et une petite liste, nous maintenons une table de hachage et une liste sortingée de tous les éléments. Chaque fois qu’une recherche est effectuée, ce terme est incrémenté dans la table de hachage et, dans la liste sortingée, le terme peut être vérifié pour voir s’il doit être remplacé par le terme suivant. Un arbre binary auto-équilibré pourrait bien fonctionner pour cela, car nous devons également pouvoir l’interroger rapidement (plus d’informations à ce sujet plus loin).

De plus, nous maintenons une liste d’heures sous la forme d’une liste FIFO (queue). Chaque élément “heure” contiendrait une liste de toutes les recherches effectuées au cours de cette heure particulière. Ainsi, par exemple, notre liste d’heures pourrait ressembler à ceci:

 Time: 0 hours -Search Terms: -free stuff: 56 -funny pics: 321 -stackoverflow: 1234 Time: 1 hour -Search Terms: -ebay: 12 -funny pics: 1 -stackoverflow: 522 -BP sucks: 92 

Puis, toutes les heures: Si la liste a au moins 720 heures (soit le nombre d’heures en 30 jours), examinez le premier élément de la liste et, pour chaque terme de recherche, décrémentez cet élément dans la table de hachage par le montant approprié. . Supprimez ensuite cet élément de la première heure de la liste.

Alors, disons que nous sums à l’heure 721, et nous sums prêts à regarder la première heure de notre liste (ci-dessus). Nous décrémentions les choses libres de 56 dans la table de hachage, les images amusantes de 321, etc., et nous supprimerions complètement l’heure 0 de la liste car nous n’aurons jamais besoin de la revoir.

La raison pour laquelle nous maintenons une liste sortingée de tous les termes qui permettent des requêtes rapides est que chaque heure après les termes de la recherche il y a 720 heures, nous devons nous assurer que la liste des dix premiers rest sortingée. Ainsi, comme nous décrémentons par exemple le “free stuff” de 56 dans la table de hachage, nous vérifierions son emplacement actuel dans la liste. Comme il s’agit d’un arbre binary à équilibrage automatique, tout cela peut très bien s’effectuer dans le temps O (log (n)).


Modifier: sacrifier la précision pour l’espace …

Il pourrait être utile de mettre en place une grande liste dans le premier, comme dans le second. Ensuite, nous pourrions appliquer l’optimisation de l’espace suivante dans les deux cas: Exécutez un travail cron pour supprimer tous les éléments sauf les x supérieurs de la liste. Cela réduirait l’encombrement (et, par conséquent, rendrait les requêtes plus rapides sur la liste). Bien sûr, cela donnerait un résultat approximatif, mais cela est autorisé. x peut être calculé avant le déploiement de l’application en fonction de la mémoire disponible et ajusté dynamicment si davantage de mémoire devient disponible.

Pensée dure …

Pour le top 10 de tous les temps

  • Utiliser une collection de hachage où un compte pour chaque terme est stocké (assainir les termes, etc.)
  • Un tableau sortingé contenant le top 10 en cours, un terme / un compte ajouté à ce tableau chaque fois que le compte d’un terme devient égal ou supérieur au plus petit nombre du tableau

Pour le top 10 mensuel mis à jour toutes les heures:

  • En utilisant un tableau indexé sur le nombre d’heures écastings depuis le début du modulo 744 (nombre d’heures pendant un mois), quelles entrées de tableau sont constituées par une collecte de hachage où est stocké un compte pour chaque terme rencontré. Une entrée est réinitialisée chaque fois que le compteur horaire change
  • Les statistiques du tableau indexé sur le créneau horaire doivent être collectées chaque fois que le compteur de créneaux horaires actuel change (au plus une fois par heure), en copiant et en aplatissant le contenu de ce tableau indexé sur les créneaux horaires.

Errr … a du sens? Je n’ai pas pensé cela comme je le ferais dans la vraie vie

Ah oui, j’ai oublié de mentionner que la “copie / aplatissement” horaire nécessaire pour les statistiques mensuelles peut réellement réutiliser le même code utilisé pour le top 10 de tous les temps, un effet secondaire agréable.

Solution exacte

Tout d’abord, une solution qui garantit des résultats corrects, mais nécessite beaucoup de mémoire (une grande carte).

Variante “tout temps”

Conservez une carte de hachage avec des requêtes en tant que clés et leur nombre en tant que valeurs. De plus, conservez une liste des 10 requêtes les plus fréquentes à ce jour et le décompte du 10ème compte le plus fréquent (un seuil).

Mettez constamment à jour la carte lorsque le stream de requêtes est lu. Chaque fois qu’un nombre dépasse le seuil actuel, procédez comme suit: supprimez la 10ème requête de la liste “Top 10”, remplacez-la par la requête que vous venez de mettre à jour et mettez également à jour le seuil.

Variante “mois passé”

Conservez la même liste “Top 10” et mettez-la à jour de la même manière que ci-dessus. Conservez également une carte similaire, mais cette fois, stockez les vecteurs de 30 * 24 = 720 comptes (un pour chaque heure) en tant que valeurs. Chaque heure, procédez comme suit pour chaque clé: supprimez le compteur le plus ancien du vecteur et ajoutez-en un nouveau (initialisé à 0) à la fin. Supprimez la clé de la carte si le vecteur est à zéro. Aussi, chaque heure, vous devez calculer la liste “Top 10” à partir de zéro.

Note: Oui, cette fois nous stockons 720 entiers au lieu d’un, mais il y a beaucoup moins de clés (la variante de tous les temps a une très longue queue).

Approximations

Ces approximations ne garantissent pas la solution correcte, mais consumnt moins de mémoire.

  1. Traitez chaque n-ème requête en ignorant le rest.
  2. (Pour les variantes de tous les temps uniquement) Conservez au plus M paires de valeurs-clés dans la carte (M doit être aussi grand que vous pouvez vous le permettre). C’est une sorte de cache LRU: chaque fois que vous lisez une requête qui n’est pas dans la carte, supprimez la requête la moins récemment utilisée avec le compte 1 et remplacez-la par la requête en cours de traitement.

Top 10 des termes de recherche du mois dernier

En utilisant une structure d’indexation / de données efficace en termes de mémoire, telle que des tentatives très compactes (à partir d’entrées de wikipedia sur try ) définit approximativement une relation entre les besoins en mémoire et le nombre de termes.

Si la mémoire requirejse est disponible ( hypothèse 1 ), vous pouvez conserver des statistiques mensuelles exactes et les agréger tous les mois dans toutes les statistiques.

Il y a aussi une hypothèse qui interprète le «dernier mois» comme une fenêtre fixe. Mais même si la fenêtre mensuelle glisse, la procédure ci-dessus montre le principe (le glissement peut être approché avec des fenêtres fixes de taille donnée).

Cela me fait penser à une firebase database circulaire, à ceci près que certaines statistiques sont calculées sur «tout le temps» (toutes les données sont conservées; rrd consolide les périodes sans tenir compte des détails en faisant la moyenne, en additionnant ou en choisissant des valeurs max / min). dans une tâche donnée, les informations perdues sont des informations sur les éléments à basse fréquence, qui peuvent entraîner des erreurs).

Hypothèse 1

Si nous ne pouvons pas tenir de statistiques parfaites pour tout le mois, nous devrions pouvoir trouver une période P pour laquelle nous devrions être en mesure de conserver des statistiques parfaites. Par exemple, en supposant que nous ayons des statistiques parfaites sur une période de temps P, qui se répercute sur le mois n fois.
Des statistiques parfaites définissent la fonction f(search_term) -> search_term_occurance .

Si nous pouvons garder toutes les tables de statistiques parfaites en mémoire, les statistiques mensuelles glissantes peuvent être calculées comme ceci:

  • append des stats pour la nouvelle période
  • Supprime les statistiques pour la période la plus ancienne (il faut donc garder des tables stat parfaites)

Cependant, si nous ne conservons que le top 10 au niveau agrégé (mensuel), nous pourrons alors éliminer beaucoup de données des statistiques complètes de la période fixée. Cela donne déjà une procédure de travail qui a fixé (en supposant la limite supérieure sur la table de statistiques parfaite pour la période P) les besoins en mémoire.

Le problème avec la procédure ci-dessus est que si nous conservons des informations sur les 10 premiers termes pour une fenêtre glissante (de même pour tous les temps), alors les statistiques seront correctes pour les termes de recherche statistiques pour les termes de recherche qui arrivent constamment au fil du temps.

Cela peut être compensé en conservant des informations sur plus de 10 termes, par exemple les 100 principaux termes, en espérant que le top 10 sera correct.

Je pense qu’une parsing plus approfondie pourrait relier le nombre minimum d’occurrences requirejses pour qu’une entrée devienne une partie des statistiques (ce qui est lié à l’erreur maximale).

(Pour décider quelles entrées doivent faire partie des statistiques, vous pouvez également suivre et suivre les tendances, par exemple si une extrapolation linéaire des occurrences de chaque période P pour chaque terme vous indique que le terme deviendra significatif dans un mois ou deux. peut déjà commencer le suivi.Un principe similaire s’applique pour supprimer le terme de recherche du pool suivi.)

Le pire des cas est que vous avez beaucoup de termes presque identiques et qu’ils changent constamment (par exemple, si vous ne suivez que 100 termes, si les 150 termes les plus fréquents sont les mêmes, mais que les 50 premiers sont plus fréquents le premier mois). de temps en temps, les statistiques ne seraient pas conservées correctement.

Il pourrait aussi y avoir une autre approche qui n’est pas fixe dans la taille de la mémoire (bien au contraire, ce n’est pas le cas ci-dessus), qui définirait la signification minimale en termes d’occurrences / période (jour, mois, année, tous les temps). Statistiques. Cela pourrait garantir une erreur maximale dans chacune des statistiques pendant l’agrégation (voir à nouveau le round robin).

Qu’en est-il d’une adaptation de “l’algorithme de remplacement de page d’horloge” (également connu sous le nom de “seconde chance”)? Je peux imaginer que cela fonctionne très bien si les demandes de recherche sont dissortingbuées de manière uniforme (cela signifie que la plupart des termes recherchés apparaissent régulièrement plutôt que 5 millions de fois de suite, puis plus jamais).

Voici une représentation visuelle de l’algorithme: algorithme de remplacement de page d'horloge

Stockez le nombre de termes de recherche dans une table de hachage géante, où chaque nouvelle recherche entraîne l’incrémentation d’un élément particulier. Gardez une trace des quelque 20 termes de recherche; Lorsque l’élément à la 11ème place est incrémenté, vérifiez s’il doit changer de position avec # 10 * (il n’est pas nécessaire de garder les 10 premiers sortingés; tout ce qui vous intéresse est de faire la distinction entre le 10ème et le 11ème).

* Des vérifications similaires doivent être faites pour voir si un nouveau terme de recherche est à la 11ème place, donc cet algorithme bascule également vers d’autres termes de recherche – donc je simplifie un peu.

parfois, la meilleure réponse est “je ne sais pas”.

Je vais prendre un coup plus profond. Mon premier instinct serait de transmettre les résultats dans un Q. Un processus traiterait continuellement des éléments entrant dans le Q. Le processus maintiendrait une carte de

terme -> compter

Chaque fois qu’un élément Q est traité, il vous suffit de rechercher le terme de recherche et d’incrémenter le nombre.

Parallèlement, je maintiendrais une liste de références aux 10 premières entrées de la carte.

Pour l’entrée actuellement implémentée, vérifiez si son compte est supérieur au nombre de décomptes de la plus petite entrée dans le top 10. (si ce n’est déjà fait dans la liste). Si c’est le cas, remplacez le plus petit par l’entrée.

Je pense que ça marcherait. Aucune opération ne demande beaucoup de temps. Vous devrez trouver un moyen de gérer la taille de la carte de comptage. mais cela devrait suffire pour répondre à une interview.

Ils n’attendent pas de solution, ils veulent voir si vous pouvez penser. Vous n’avez pas besoin d’écrire la solution alors et là ….

Un moyen est que pour chaque recherche, vous stockez ce terme de recherche et son horodatage. De cette façon, il suffit de comparer tous les termes de recherche au cours d’une période donnée pour trouver le top dix pour une période donnée.

L’algorithme est simple, mais l’inconvénient serait une plus grande consommation de mémoire et de temps.

Qu’en est-il de l’utilisation d’un arbre Splay avec 10 nœuds? Chaque fois que vous essayez d’accéder à une valeur (terme de recherche) qui n’est pas contenue dans l’arborescence, lancez n’importe quelle feuille, insérez la valeur à la place et accédez-y.

L’idée derrière cela est la même que dans mon autre réponse . En supposant que les termes de recherche sont consultés régulièrement / régulièrement, cette solution devrait très bien fonctionner.

modifier

On pourrait également stocker d’autres termes de recherche dans l’arborescence (il en va de même pour la solution que je propose dans mon autre réponse) afin de ne pas supprimer un nœud auquel on pourrait accéder très bientôt. Plus on enregistre de valeurs, meilleurs sont les résultats.

Je ne sais pas si je comprends bien ou pas. Ma solution utilise heap. En raison des 10 principaux éléments de recherche, je crée un segment de taille 10. Mettez ensuite à jour ce segment avec une nouvelle recherche. Si la fréquence d’une nouvelle recherche est supérieure à heap (Max Heap) en haut, mettez-la à jour. Abandonnez celui avec la plus petite fréquence.

Mais, comment calculer la fréquence de la recherche spécifique sera compté sur autre chose. Peut-être comme tout le monde l’a dit, l’algorithme du stream de données …

Utilisez cm-sketch pour stocker le nombre de toutes les recherches depuis le début, conservez un min-heap de taille 10 avec le top 10. Pour le résultat mensuel, conservez 30 cm-sketch / table de hachage et min-heap compter et mettre à jour à partir des 30, 29, et 1 derniers jours. En tant que passe journalière, effacez la dernière et utilisez-la comme jour 1. Même pour le résultat horaire, gardez 60 table de hachage et min-tas et commencez à compter pour les dernières 60, 59, … 1 minutes. En une minute, effacez la dernière et utilisez-la comme minute 1.

Le résultat mensuel est précis dans la plage de 1 jour, le résultat horaire est précis dans la plage de 1 min

The problem is not universally solvable when you have a fixed amount of memory and an ‘infinite’ (think very very large) stream of tokens.

A rough explanation…

To see why, consider a token stream that has a particular token (ie, word) T every N tokens in the input stream.

Also, assume that the memory can hold references (word id and counts) to at most M tokens.

With these conditions, it is possible to construct an input stream where the token T will never be detected if the N is large enough so that the stream contains different M tokens between T’s.

This is independent of the top-N algorithm details. It only depends on the limit M.

To see why this is true, consider the incoming stream made up of groups of two identical tokens:

 T a1 a2 a3 ... aM T b1 b2 b3 ... bM ... 

where the a’s, and b’s are all valid tokens not equal to T.

Notice that in this stream, the T appears twice for each ai and bi. Yet it appears rarely enough to be flushed from the system.

Starting with an empty memory, the first token (T) will take up a slot in the memory (bounded by M). Then a1 will consume a slot, all the way to a-(M-1) when the M is exhausted.

When aM arrives the algorithm has to drop one symbol so let it be the T. The next symbol will be b-1 which will cause a-1 to be flushed, etc.

So, the T will not stay memory-resident long enough to build up a real count. In short, any algorithm will miss a token of low enough local frequency but high global frequency (over the length of the stream).