Algorithme pour trouver le top 10 des termes de recherche
Je suis actuellement en train de préparer pour une entrevue, et cela me rappelle une question que m'a demandé une fois dans une précédente interview qui disait quelque chose comme:
"Il vous a été demandé de concevoir un logiciel pour afficher en permanence le top 10 des termes de recherche sur Google. Vous avez accès à une alimentation qui fournit une interminable de flux en temps réel des termes de recherche actuellement en cours de recherche sur Google. Décrire ce que l'algorithme et structures de données vous pouvez utiliser pour mettre en œuvre cette. Vous êtes à la conception de deux variantes:
(i) Afficher les 10 premiers termes de recherche de tous les temps (c'est à dire depuis que vous avez commencé la lecture de l'alimentation).
(ii) d'Afficher uniquement le top 10 des termes de recherche pour le mois passé, mis à jour toutes les heures.
Vous pouvez utiliser une approximation pour obtenir la liste du top 10, mais vous devez justifier votre choix."
J'ai bombardé dans cette interview et encore ont vraiment aucune idée de comment le mettre en œuvre.
La demande, en premier lieu pour les 10 les plus fréquentes des éléments dans un développement continu de la sous-séquence d'une liste infinie. J'ai regardé dans les algorithmes de sélection, mais ne pouvais pas trouver toutes les versions en ligne pour résoudre ce problème.
La seconde partie utilise une liste restreinte, mais en raison de la grande quantité de données en cours de traitement, vous ne pouvez pas vraiment de magasin sur l'ensemble du mois de termes de recherche dans la mémoire et de calculer un histogramme de chaque heure.
Le problème est rendu plus difficile par le fait que le top 10 liste est continuellement mise à jour, donc, en quelque sorte, vous devez être le calcul de votre top 10 sur une fenêtre glissante.
Des idées?
- Ce n'est pas une stupide question de l'entrevue, c'est une mauvaise interprétation sur l'OP de la partie. Ce n'est pas pour vous demander le plus fréquent des éléments dans une liste infinie, il est demandé pour les plus fréquentes des éléments finis sous-suite d'une liste infinie. Pour continuer votre analogie,
what is the most frequent item in the subsequence [2; 2; 3; 3; 3; 4; 4; 4; 4; 5; 5] of your sequence? - C'est certainement une question difficile, mais je ne vois pas pourquoi il est stupide, il semble que représentant d'un assez typique de problème que les entreprises avec d'énormes ensembles de données sont confrontés. @IVlad - Fixe à votre suggestion, une mauvaise formulation de ma part!
Vous devez vous connecter pour publier un commentaire.
Bien, ressemble à un tas de données, avec peut-être un coût prohibitif pour stocker toutes les fréquences. Lorsque la quantité de données est si grande que nous ne pouvons pas espérer pour stocker l'ensemble, nous entrons dans le domaine de flux de données algorithmes.
Livre utile dans ce domaine:
Muthukrishnan - "Flux de Données: Algorithmes et Applications"
Étroitement liés référence à un problème qui j'ai pris de la ci-dessus:
Manku, Motwani - "Fréquence Approximative Compte plus de Flux de Données" [pdf]
Par la voie, Motwani, de Stanford, (edit) était un auteur de la très importante "Algorithmes Randomisés" livre.
Le 11e chapitre de ce livre traite de ce problème. Edit: Désolé, mauvaise référence, ce chapitre est un problème différent. Après vérification, j'ai plutôt recommander l'article 5.1.2 de Muthukrishnan s livre, disponible en ligne.Heh, nice questions de l'entrevue.
Fréquence D'Estimation Aperçu
Il y a quelques algorithmes les plus connus qui peuvent fournir des estimations de la fréquence pour un tel flux à l'aide d'un montant fixe de stockage. On est Fréquentes, par Misra et de Gries (1982). À partir d'une liste de n éléments, c'trouver tous les éléments qui se produisent plus que n /k fois, à l'aide de k - 1 compteurs. C'est une généralisation de Boyer et Moore Majorité algorithme (Fischer-Salzberg, 1982), où k est 2. Manku et Motwani de LossyCounting (2002) et Metwally de Encombrant (2005), les algorithmes de semblables exigences en matière d'espace, mais peut fournir des estimations plus précises, sous certaines conditions.
La chose importante à retenir est que ces algorithmes ne peuvent fournir des estimations de la fréquence. Plus précisément, le Misra-Gries estimation de sous-comptage de la fréquence réelle par (n /k) éléments.
Supposons que vous avez eu un algorithme qui pourrait identifier avec certitude un élément seulement si elle se produit plus de 50% du temps. Nourrir cet algorithme un flux de N articles distincts, puis ajouter un autre N - 1 copies d'un élément, x, pour un total de 2N - 1 éléments. Si l'algorithme vous dit que x dépasse 50% du total, il doit avoir été dans le premier volet; si elle ne l'est pas, x n'était pas dans le premier volet. Pour que l'algorithme pour faire cette détermination, il faut stocker le flux initial (ou sommaire de certaines proportionnelle à sa longueur)! Donc, on peut le prouver à nous-mêmes que l'espace requis par une telle "exacte" de l'algorithme serait Ω(N).
Au lieu de cela, ces fréquences algorithmes décrits ici de fournir une estimation, d'identifier tout élément qui dépasse le seuil, le long avec certains éléments qui sont en-dessous d'une certaine marge. Par exemple, le Majorité algorithme, à l'aide d'un seul compteur, donnera toujours un résultat; si un élément est supérieur à 50% du flux, il sera trouvé. Mais il peut aussi vous donner un élément qui ne se produit qu'une fois. Vous ne savez pas sans faire un second passage sur les données (à l'aide, encore une fois, un seul compteur, mais seulement à la recherche de cet élément).
Fréquentes Algorithme
Voici une description simple de Misra-Gries' Fréquentes algorithme. Demaine (2002) et d'autres ont optimisé l'algorithme, mais cela vous donne l'essentiel.
Spécifier le seuil de fraction, 1 /k; tout élément qui apparaît plus que n /k temps sera trouvé. Créer une carte vide (comme un rouge-noir arbre); les clés sont des termes de recherche, et les valeurs sera un contre pour ce terme.
Notez que vous pouvez traiter une quantité infinie de données avec un montant fixe de stockage (juste la taille fixe de la carte). La quantité de stockage requise dépend uniquement du seuil d'intérêt, et la taille du flux n'a pas d'importance.
Comptage Des Recherches
Dans ce contexte, peut-être vous avez de la mémoire tampon d'une heure de recherches, et d'effectuer cette procédure sur l'heure de données. Si vous pouvez prendre une seconde pour passer au-dessus de cette heure du journal de recherche, vous pouvez obtenir un nombre exact d'occurrences des meilleurs "candidats" identifiés lors de la première passe. Ou, peut-être bien pour faire une seule passe, et de faire rapport tous les candidats, sachant que chaque élément qui doit y être inclus, et tous les extras sont que le bruit qui va disparaître dans les prochaines heures.
Les candidats qui dépassent le seuil d'intérêt sont enregistrés comme un résumé. Garder l'équivalent d'un mois de ces résumés, de jeter le plus ancien de chaque heure, et vous devriez avoir une bonne approximation de la plus commune des termes de recherche.
1/(1+X)et qu'est-ce que la théorie derrière tout cela?C'est l'un des projet de recherche que je suis actuelle en passant par. L'exigence est presque exactement comme le vôtre, et nous avons développé de nice algorithmes pour résoudre le problème.
L'Entrée
L'entrée est un flux sans fin de l'anglais des mots ou des phrases (nous nous référons comme
tokens).La Sortie
loin de tous les jetons que nous avons
vu!)
historique de la fenêtre, disons, dernier jour ou
la semaine dernière.
Une application de cette recherche est de trouver le sujet d'actualité et les tendances de sujet dans Twitter ou Facebook. Nous avons un reptile qui rampe sur le site web, qui génère un flux de mots, ce qui permettra d'alimenter le système. Ensuite, le système affichera les mots ou les phrases de fréquence supérieure soit globale ou historique. Imaginez dans les deux dernières semaines, le membre de phrase "Coupe du Monde" seraient apparaît de nombreuses fois dans Twitter. Ne sorte de "Paul le poulpe". 🙂
Chaîne de caractères en nombres Entiers
Le système a un nombre entier ID pour chaque mot. Bien qu'il est presque infini de 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 bas. Nous avons déjà trouvé 4 millions de mots différents, et d'attribuer un IDENTIFIANT unique pour chaque. Cet ensemble de données peut être chargé dans la mémoire comme une table de hachage, consommant environ 300MO de mémoire. (Nous avons mis en place notre propre table de hachage. La Java de la mise en œuvre prend énorme surcharge de la mémoire)
Chaque phrase peut alors être identifié comme un tableau d'entiers.
C'est important, parce que, de tri et de comparaisons sur des entiers est beaucoup beaucoup plus rapide que sur des chaînes de caractères.
De Données D'Archives
Le système permet d'archiver des données pour chaque jeton. En gros, c'est des paires de
(Token, Frequency). Toutefois, la table qui stocke les données seraient énormes, tels que nous avons à la partition de la table physiquement. Une fois que la partition système est fondé sur ngrams du jeton. Si le jeton est un seul mot, il est 1gram. Si le jeton est de deux mots de la phrase, il est 2gram. Et ce qui se passe. À peu près à 4gram nous avons 1 milliard d'enregistrements, avec une table de taille moyenne autour de 60 GO.De Traitement Des Flux Entrants
Le système absorbe entrant phrases jusqu'à ce que la mémoire devient pleinement utilisé (Ya, nous avons besoin d'un MemoryManager). Après la prise de la N des phrases et de la stocker dans la mémoire, le système s'arrête, et commence à marquer chaque phrase en mots et en phrases. Chaque jeton (mot ou phrase) est compté.
Très fréquentes jetons, ils sont toujours gardés en mémoire. Pour les moins fréquentes jetons, ils sont triés en fonction Id (souvenez-vous de nous traduire la Chaîne dans un tableau de nombres entiers), et sérialisée dans un fichier sur disque.
(Cependant, pour votre problème, puisque vous comptez uniquement sur les mots, alors vous pouvez mettre tous les mot-fréquence de la carte dans la mémoire. Soigneusement conçu la structure de données de la consommer seulement 300 MO de mémoire pour 4 millions de mots différents. Un indice: utiliser des caractères ASCII dans le fichier pour représenter des Chaînes de caractères), et c'est tout à fait acceptable.
Pendant ce temps, il y aura un autre processus qui est activé une fois qu'il trouve un fichier de disque généré par le système, puis démarrer la fusion elle. Depuis le disque fichier est trié, la fusion prendrait un processus similaire comme la fusion de tri. Certains de conception doivent être pris en compte ici, car nous voulons éviter de trop aléatoire du disque cherche. L'idée est d'éviter de lire (processus de fusion)/write (sortie du système) en même temps, et de laisser le processus de fusion de lire un disque lors de l'écriture sur un disque différent. C'est comme pour la mise en œuvre d'un verrouillage.
La fin de la Journée
À la fin de la journée, le système aura beaucoup de fréquentes jetons avec la fréquence enregistrée dans la mémoire, et beaucoup d'autres moins fréquentes jetons stockées dans plusieurs fichiers de disque (et chaque fichier est trié).
La purge du système de la carte mémoire dans un fichier de disque (tri). Maintenant, le problème devient de la fusion d'un ensemble de triés fichier de disque. A l'aide du même processus, on obtient une triés fichier de disque à la fin.
Ensuite, la tâche finale consiste à fusionner la triées disque fichier dans l'archive de la base de données.
Dépend de la taille de l'archive de la base de données, l'algorithme fonctionne comme ci-dessous s'il est assez gros:
L'intuition est que, après un certain temps, le nombre d'insertion va devenir de plus en plus petites. De plus en plus et de l'opération de mise à jour uniquement. Et cette mise à jour ne sera pas pénalisé par l'index.
Espère que toute cette explication pourrait l'aider. 🙂
Vous pouvez utiliser un table de hachage combiné avec un un arbre de recherche binaire. Mettre en œuvre un
<search term, count>dictionnaire qui vous indique le nombre de fois que chaque terme de recherche a été recherché.Évidemment une itération à l'ensemble de la table de hachage de chaque heure, le top 10 est très mauvais. Mais c'est google nous parlons, de sorte que vous pouvez supposer que le top dix obtiendrez tout, disons plus de 10 000 visites (c'est probablement un nombre beaucoup plus grand bien). Donc chaque fois qu'un terme de recherche count est supérieur à 10 000, de l'insérer dans la BST. Puis toutes les heures, vous n'avez qu'à obtenir le premier 10 de la BST, qui devrait contenir relativement peu d'entrées.
Ce qui résout le problème de la top 10 de tous les temps.
La partie vraiment difficile est de traiter avec un terme de prendre une autre place dans le rapport mensuel (par exemple, "stack overflow" peut avoir les 50 000 visites au cours des deux derniers mois, mais seulement 10 000 le mois dernier, tandis que "amazon" peut avoir les 40 000 pour les deux derniers mois, mais 30 000 pour le mois passé. Vous voulez "amazon" avant de "stack overflow" dans votre rapport mensuel). Pour ce faire, je voudrais stocker, pour tous les grands (plus de 10 000 toutes les recherches en temps) des termes de recherche, une liste de 30 jours qui vous indique le nombre de fois que le terme a été recherché pour chaque jour. La liste pourrait fonctionner comme une file d'attente FIFO: vous supprimez le premier jour et insérer un nouveau chaque jour (ou chaque heure, mais vous pourriez avoir besoin pour stocker davantage d'informations, ce qui signifie plus de mémoire /de l'espace. Si la mémoire n'est pas un problème de le faire, sinon rendez-vous pour que ce "rapprochement" ils parlent).
Cela ressemble à un bon début. Vous pouvez ensuite vous soucier de l'élagage dans les termes qui ont > 10 000 coups, mais n'ai pas eu beaucoup depuis longtemps, et des trucs comme ça.
cas i)
Maintenir une table de hachage pour tous les searchterms, ainsi qu'un classement parmi les dix premiers de la liste distincte de la table de hachage. Chaque fois qu'une recherche se produit, incrémenter l'élément approprié dans la table de hachage et de vérifier pour voir si l'élément en question doit maintenant être activée avec le 10ème élément en haut de la liste des dix.
O(1) recherche pour le top-ten de la liste, et max O(log(n)) à une insertion dans la table de hachage (en supposant que les collisions géré par un auto-équilibrage arbre binaire).
cas ii)
Au lieu de maintenir un énorme table de hachage et une petite liste, nous maintenons une table de hachage et une liste trié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 triée, le terme peut être vérifié pour voir si il faut passer par le terme d'après elle. Un auto-équilibrage arbre binaire pourrait fonctionnent bien pour cela, que nous devons également être en mesure d'interroger rapidement (plus sur cela plus tard).
En outre, nous maintenons également une liste des "heures" sous la forme d'une liste FIFO (file d'attente). Chaque 'heure' élément doit contenir une liste de toutes les recherches effectuées au sein de cette heure. Ainsi, par exemple, la liste de nos heures pourrait ressembler à ceci:
Puis, à chaque heure: Si la liste contient au moins 720 heures (c'est le nombre d'heures dans les 30 jours), regarde le premier élément dans la liste, et pour chaque terme de recherche, de décrémentation de cet élément dans la table de hachage par le montant approprié. Ensuite, supprimez cette première heure de l'élément de la liste.
Donc, disons que nous en sommes à l'heure 721, et nous sommes prêts à regarder la première heure dans notre liste (ci-dessus). Nous avions décrémenter des trucs gratuits par 56 dans la table de hachage, de drôles de photos par 321, etc., puis retirez l'heure 0 à partir de la liste complètement puisque nous n'aurez plus jamais besoin de le regarder de nouveau.
La raison pour laquelle nous maintenir une liste triée de tous les termes qui permet d'obtenir rapidement des requêtes est parce que toutes les heures que nous passons à travers les termes de recherche à partir de 720 heures, nous devons nous assurer que le top-ten reste de liste triée. Si, comme nous l'décrémenter 'trucs' de 56 dans la table de hachage par exemple, nous aimerions vérifier pour voir où elle appartient maintenant dans la liste. Parce que c'est un auto-équilibrage arbre binaire, tout cela peut être accompli bien en O(log(n)) de temps.
Edit: autant Sacrifier la précision de l'espace...
Il pourrait être utile de mettre en œuvre un grand liste dans le premier comme dans le second. Nous pourrions appliquer la suite de l'optimisation de l'espace sur les deux cas: Exécuter une tâche cron pour supprimer tous les, mais le haut x éléments dans la liste. Cela permettrait de limiter les besoins d'espace en bas (et donc faire des requêtes sur la liste des plus rapide). Bien sûr, il en résulterait un résultat approximatif, mais c'est autorisé. x pourrait être calculé avant le déploiement de l'application en fonction de la mémoire disponible, et de régler dynamiquement si plus de mémoire devient disponible.
Approximative de la pensée...
Pour le top 10 de tous les temps
Mensuel top 10 mis à jour toutes les heures:
Euh... un sens? Je ne pense pas que cette grâce comme je le ferais dans la vraie vie
Ah oui, j'ai oublié de mentionner, l'horaire "copier/aplatissement" requis pour le mensuel de statistiques peut réutiliser le même code utilisé pour le top 10 de tous les temps, un bel effet.
Solution exacte
Tout d'abord, une solution qui garantit des résultats corrects, mais nécessite beaucoup de mémoire (une carte).
"De tous les temps" variante
Maintenir un hachage de la carte avec des requêtes comme des clés et de leur compte en tant que valeurs. En outre, une liste f 10 la plupart des requêtes fréquentes jusqu'à présent et le compte de la 10e plus fréquentes count (un seuil).
Constamment mise à jour de la carte comme le flux de requêtes de lecture. Chaque fois qu'un nombre dépasse le seuil de courant, procédez comme suit: retirez le 10e requête du "Top 10" de la liste, la remplacer par une requête, vous avez juste mis à jour, et de mettre à jour le seuil ainsi.
"Derniers mois" variante
Garder le même "Top 10" de la liste et de la mise à jour de la même manière que ci-dessus. Aussi, gardez une carte du même type, mais cette fois de stocker des vecteurs de 30*24 = 720 count (une pour chaque heure) en tant que valeurs. À chaque heure, procédez de la manière suivante pour chaque touche: supprimer le plus ancien compteur à partir du vecteur d'en ajouter une nouvelle (initialisé à 0) à la fin. Retirez la clé de la carte si le vecteur est de zéro pour tous. Aussi, à chaque heure, vous devez calculer le "Top 10" de la liste à partir de zéro.
Note: Oui, cette fois nous sommes le stockage de 720 entiers au lieu d'un, mais il y a beaucoup moins de touches (de tous les temps de la variante a un vraiment longue queue).
Approximations
Ces approximations ne garantit pas la bonne solution, mais sont de moins en moins de mémoire longue.
Top 10 des termes de recherche pour le mois passé
À l'aide de la mémoire efficace d'indexation ou de structure de données, tels que serrés tente (entrées de wikipedia sur essaie) environ définit une relation entre les exigences de mémoire et de n - nombre de termes.
Dans le cas de la mémoire nécessaire est disponible (hypothèse 1), vous pouvez garder exacte mensuel de la statistique et de l'agréger tous les mois dans tous les temps de statistiques.
Il est, aussi, une hypothèse ici que l'interprète de la "le mois dernier", comme fenêtre fixe.
Mais même si les mensualités fenêtre coulissante de la procédure ci-dessus montre le principe (glissement peut être assimilée à des fenêtres fixes de taille donnée).
Cela me rappelle de round-robin de la base de données à l'exception de quelques statistiques sont calculées sur "tous les temps" (dans un sens que toutes les données sont conservées; rrd consolide les périodes faisant abstraction des détails en moyenne, résumant ou en choisissant des valeurs max/min, en tâche donnée le détail qui est perdu, c'est de l'information sur la faible fréquence des éléments, ce qui peut introduire des erreurs).
Hypothèse 1
Si l'on ne peut pas tenir le parfait stats pour le mois entier, alors nous devrions être en mesure de trouver une certaine période P pour lesquelles nous devrions être en mesure de tenir parfaite stats.
Par exemple, en supposant que nous avons parfait statistiques sur une certaine période P, qui va dans le mois n fois.
Parfait stats définir la fonction
f(search_term) -> search_term_occurance.Si nous pouvons garder toutes
nparfait stat tables en mémoire, puis de glissement mensuel de statistiques peut être calculé comme ceci:nparfait stat tables)Cependant, si nous ne garder que des top 10 sur le niveau agrégé (mensuel), alors nous serons en mesure de jeter un grand nombre de données à partir de l'stats complètes de la période fixée. Cela donne déjà une procédure de travail qui a fixe (en supposant que la limite supérieure de parfait stat table pour la période P) à la mémoire.
Le problème avec la procédure ci-dessus est que si nous continuons d'info sur le seul top 10 des conditions pour une fenêtre coulissante (de même pour tous les temps), alors que les stats vont être correct pour des termes de recherche de pointe dans une période, mais pourrait ne pas voir les stats pour les termes de recherche que peu de choses dans la permanence dans le temps.
Cela peut être compensé par le maintien d'info sur le plus de top 10 des conditions, par exemple les 100 meilleurs conditions, en espérant que le top 10 sera correct.
Je pense qu'une analyse plus approfondie pourrait porter le nombre minimum d'occurrences requis pour une entrée pour devenir une partie de l'stats (qui est liée à l'erreur maximale).
(Dans le choix des entrées doit devenir une partie de l'stats on pourrait aussi surveiller et de suivre les tendances; par exemple, si une extrapolation linéaire des occurrences dans chaque période P pour chaque terme vous dit que le terme va devenir important dans un mois ou deux, vous pouvez déjà commencer à les localiser. Selon le même principe s'applique pour enlever le terme de recherche à partir de la zone de la piscine.)
Pire des cas pour le ci-dessus, c'est quand vous avez beaucoup de presque aussi fréquente termes et ils changent tout le temps (par exemple si le suivi de seulement 100 termes, alors si top 150 des conditions se produisent aussi fréquemment, mais top 50 sont le plus souvent dans les premiers mois et de peur que, souvent, quelque temps plus tard, alors que les statistiques ne serait pas maintenu correctement).
Aussi il pourrait y avoir une autre approche qui n'est pas fixé à la taille de la mémoire (bien strictement parlant, ce n'est pas le ci-dessus), ce qui permettrait de définir minimum de signification en termes d'occurrences/période (jour, mois, année, de tous les temps) pour lequel garder les stats. Cela pourrait garantir max d'erreur dans chacun des statistiques au cours de l'agrégation (voir round robin de nouveau).
Ce sujet d'une adaptation de la "l'horloge de l'algorithme de remplacement de page" (aussi connu comme la "seconde chance")? Je peux imaginer que cela fonctionne très bien si les requêtes de recherche sont répartis de manière égale (ce qui signifie que la plupart des termes recherchés apparaissent régulièrement plutôt que de 5mio fois dans une rangée, puis plus jamais).
Voici une représentation visuelle de l'algorithme:
Stocker le nombre de termes de recherche dans un géant de la table de hachage, où chaque nouvelle recherche des causes d'un élément particulier d'être incrémenté de un. Suivre le top 20 ou si les termes de recherche; lorsque l'élément dans la 11ème place est incrémenté, vérifier si elle a besoin d'échanger les positions avec #10* (il n'est pas nécessaire de garder le top 10 triés; tout ce qui vous intéresse est de faire la distinction entre le 10ème et 11ème).
*Similaire chèques doivent être faits pour voir si un nouveau terme de recherche est à la 11ème place, de sorte que cet algorithme bulles vers le bas à d'autres termes de recherche aussi, donc je simplifie un peu.
parfois, la meilleure réponse est "je ne sais pas".
Mal prendre un profond coup de poignard. Mon premier réflexe serait de nourrir les résultats dans un Q. Un processus en permanence les éléments de processus à venir dans le Q. Le processus serait de maintenir une carte de
terme -> count
chaque fois qu'un Q élément est traité, il vous suffit de rechercher le terme de recherche et d'incrémenter le compteur.
En même temps, je voudrais maintenir une liste de références pour le top 10 des entrées dans la carte.
L'entrée qui est actuellement mis en œuvre, voir si son nombre est supérieur au nombre de le nombre de la plus petite entrée dans le top 10.(si pas dans la liste déjà). Si c'est, remplacer le plus petit avec l'entrée.
Je pense que ce serait le travail. Aucune opération n'est consommateur de temps. Vous devez trouver un moyen de gérer la taille de l'compter de la carte. mais ça devrait bien assez pour une interview réponse.
Ils ne s'attend pas à une solution, que vous voulez voir si vous pouvez penser. Vous n'avez pas à écrire la solution puis et là....
queue,Qest une lettre :).Une façon est que pour chaque recherche, vous stockez le terme de recherche, et son timbre de temps. De cette façon, trouver le top dix pour toute période de temps est tout simplement une question de comparer tous les termes de recherche dans la période de temps donnée.
L'algorithme est simple, mais l'inconvénient serait plus de la mémoire et du temps de consommation.
Que sur l'utilisation d'un Splay Tree avec 10 nœuds? Chaque fois que vous essayez d'accéder à une valeur (terme de recherche) qui n'est pas contenue dans l'arbre, jetez les feuilles, insérer la valeur au lieu et à y accéder.
L'idée derrière cela est la même que dans mes autres réponse. Sous l'hypothèse que les termes de recherche sont accessibles uniformément/régulièrement cette solution doit effectuer très bien.
modifier
On peut aussi stocker de plusieurs termes de recherche dans l'arbre (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 qui peut être accessible très bientôt de nouveau. Le plus les valeurs de l'un des magasins en elle, meilleurs sont les résultats.
Ne sais pas si je la comprends bien ou pas.
Ma solution est d'utiliser un segment de mémoire.
Parce que le top 10 des articles de recherche, je construis un segment dont la taille 10.
Puis mise à jour de ce segment avec une nouvelle recherche. Si une nouvelle recherche de la fréquence est plus grande que tas(Tas Max) top, les mettre à jour. Abandonner celui avec la plus petite fréquence.
Mais, comment calculer la fréquence de la recherche spécifique sera compté sur quelque chose d'autre.
Peut-être que tout le monde dit, le flux de données de l'algorithme....
Utilisez cm-esquisse pour stocker comte de toutes les recherches effectuées depuis le début, garder un min-tas de taille 10 avec elle pour le top 10.
Pour mensuel conséquent, continuer à 30 cm-croquis/table de hachage et min-tas avec elle, chacun de commencer le comptage et la mise à jour de la dernière 30, 29 .., 1 jour. Comme un passage de jour, le dernier et l'utiliser comme le jour 1.
De même pour les horaires, garder 60 table de hachage et min-tas et commencer à compter pour une durée de 60, 59, ...1 minute. Une minute passe, le dernier et l'utiliser comme la minute 1.
Mensuel résultat est précis dans la plage de 1 jour, horaire résultat est précis dans la plage de 1 min
Le problème n'est pas universellement résoluble quand vous avez une quantité fixe de mémoire et d'une infinie (pense très très grand) flux de jetons.
Un rude explication...
De voir pourquoi, considérons un jeton de flux qui a un pion (c'est à dire, word) T pour tout N jetons dans le flux d'entrée.
Aussi, supposons que la mémoire peut contenir des références (id et mot compte) d'au plus M jetons.
Avec ces conditions, il est possible de construire un flux d'entrée où le jeton T ne sera jamais détecté si N est assez grand de sorte que le flux de données contient différents M de jetons entre T.
Ceci est indépendant de la top-N algorithme de détails. Il ne dépend que de la limiter M.
De voir pourquoi ce qui est vrai, considérer le flux entrant des groupes de deux jetons identiques:
où l'a, et b sont tous valides jetons pas égal à T.
Avis que dans ce flux, le T apparaît deux fois pour chaque a-i et b-je. Pourtant, il apparaît rarement suffisante pour être supprimées du système.
De départ avec une mémoire vide, le premier jeton (T) va prendre une fente dans la mémoire (délimitée par M). Puis a1 va consommer une fente, tout le chemin à a-(M-1) lorsque le " M " est épuisé.
Quand un-M arrive l'algorithme doit déposer un symbole qu'il en soit, le T.
Le prochain symbole sera b-1 qui va provoquer un-1 pour être vidées, etc.
Donc, le T ne vais pas rester résident en mémoire assez longtemps pour mettre en place un véritable comte. En bref, tout algorithme va manquer un jeton de suffisamment basse fréquence locale mais à haute fréquence globale de la fréquence (en plus de la longueur du cours d'eau).