webentwicklung-frage-antwort-db.com.de

Algorithmus zum Finden der Top 10 Suchbegriffe

Ich bereite mich gerade auf ein Interview vor, und es erinnerte mich an eine Frage, die mir in einem früheren Interview einmal gestellt wurde.

"Sie wurden aufgefordert, eine Software zu entwerfen, die die Top 10 der Suchbegriffe bei Google kontinuierlich anzeigt. Sie erhalten Zugriff auf einen Feed, der einen endlosen Echtzeit-Stream von Suchbegriffen bereitstellt, die derzeit bei Google gesucht werden. Beschreiben Sie, welche Algorithmen und Datenstrukturen verwendet werden Um dies zu implementieren, müssen Sie zwei Varianten entwerfen: 

(i) Zeigt die Top 10 Suchbegriffe aller Zeiten an (d. h. seit Sie mit dem Lesen des Feeds begonnen haben). 

(ii) Zeigt nur die Top 10 Suchbegriffe für den letzten Monat an, stündlich aktualisiert. 

Sie können eine Annäherung verwenden, um die Top-10-Liste zu erhalten, aber Sie müssen Ihre Auswahl begründen. "
Ich habe in diesem Interview bombardiert und habe immer noch keine Ahnung, wie ich das umsetzen soll. 

Der erste Teil fragt nach den 10 häufigsten Elementen in einer kontinuierlich wachsenden Teilsequenz einer unendlichen Liste. Ich habe mir Auswahlalgorithmen angesehen, aber keine Online-Versionen gefunden, um dieses Problem zu lösen. 

Der zweite Teil verwendet eine endliche Liste, aber aufgrund der großen Datenmenge, die verarbeitet wird, können Sie nicht wirklich den gesamten Monat der Suchbegriffe im Speicher speichern und stündlich ein Histogramm berechnen. 

Das Problem wird durch die Tatsache erschwert, dass die Liste der Top 10 ständig aktualisiert wird. Daher müssen Sie Ihre Top 10 über ein Schiebefenster berechnen.

Irgendwelche Ideen?

112
del

Sieht aus wie eine Unmenge von Daten, mit möglicherweise unerschwinglichen Kosten für die Speicherung aller Frequenzen. Wenn die Datenmenge so groß ist , dass wir nicht hoffen können, alles zu speichern, geben wir die Domäne der Daten ein Stream-Algorithmen .

Nützliches Buch in diesem Bereich: Muthukrishnan - "Datenströme: Algorithmen und Anwendungen"

Eng verbundener Verweis auf das vorliegende Problem, das ich aus dem obigen herausgegriffen habe: Manku, Motwani - "Ungefähre Häufigkeit zählt über Datenströme" [pdf]

Übrigens war Motwani aus Stanford (Hrsg.) Ein Autor des sehr wichtigen Buches "Randomized Algorithms" Das 11. Kapitel dieses Buches befasst sich mit diesem Problem . Edit: Entschuldigung, schlechte Referenz, dieses bestimmte Kapitel befasst sich mit einem anderen Problem. Nach Überprüfung empfehle ich stattdessen Abschnitt 5.1.2 von Muthukrishnans Buch , online verfügbar.

Heh, nette Interviewfrage.

47

Übersicht über die Frequenzschätzung

Es gibt einige bekannte Algorithmen, die Frequenzschätzungen für einen solchen Strom unter Verwendung einer festen Speichermenge bereitstellen können. Einer ist Frequent, von Misra und Gries (1982). Aus einer Liste von n Elementen werden alle Elemente ermittelt, die mehr als n/k Mal vorkommen, wobei k - 1 Zähler verwendet werden. Dies ist eine Verallgemeinerung des Mehrheit - Algorithmus von Boyer und Moore (Fischer-Salzberg, 1982), wobei k 2 ist. Manku und Motwani LossyCounting (2002) ) und Metwallys SpaceSaving (2005) Algorithmen haben einen ähnlichen Platzbedarf, können jedoch unter bestimmten Bedingungen genauere Schätzungen liefern.

Wichtig ist, dass diese Algorithmen nur Frequenzschätzungen liefern können. Insbesondere kann die Misra-Gries-Schätzung die tatsächliche Häufigkeit um (n/k) Elemente unterzählen.

Angenommen, Sie hätten einen Algorithmus, mit dem ein Element eindeutig identifiziert werden kann nur, wenn es in mehr als 50% der Fälle vorkommt. Füttere diesen Algorithmus mit einem Strom von N verschiedenen Elementen und füge dann weitere N - 1 Kopien eines Elements x hinzu, um eine Gesamtsumme zu erhalten von 2N - 1 Elementen. Wenn der Algorithmus angibt, dass x 50% der Gesamtsumme überschreitet, muss er sich im ersten Stream befunden haben. Wenn dies nicht der Fall ist, war x nicht im ursprünglichen Stream. Damit der Algorithmus diese Bestimmung vornehmen kann, muss er den anfänglichen Datenstrom (oder eine zu seiner Länge proportionale Zusammenfassung) speichern! Wir können uns also selbst beweisen, dass der von einem solchen "exakten" Algorithmus benötigte Platz Ω (N) ist.

Stattdessen stellen diese hier beschriebenen Frequenzalgorithmen eine Schätzung bereit, die alle Elemente identifiziert, die den Schwellenwert überschreiten, sowie einige Elemente, die diesen um einen bestimmten Spielraum unterschreiten. Beispielsweise liefert der Algorithmus Majority unter Verwendung eines einzelnen Zählers immer ein Ergebnis. Wenn ein Element 50% des Streams überschreitet, wird es gefunden. Möglicherweise erhalten Sie jedoch auch einen Artikel, der nur einmal vorkommt. Sie würden es nicht wissen, ohne einen zweiten Durchgang über die Daten zu machen (erneut einen einzelnen Zähler zu verwenden, aber nur nach diesem Gegenstand zu suchen).

Der häufige Algorithmus

Hier ist eine einfache Beschreibung des Frequent -Algorithmus von Misra-Gries. Demaine (2002) und andere haben den Algorithmus optimiert, aber das gibt Ihnen das Wesentliche.

Geben Sie den Schwellenwert an: 1/k; Jedes Element, das mehr als n/k Mal vorkommt, wird gefunden. Erstellen Sie eine leere Karte (wie ein rot-schwarzer Baum). Die Schlüssel sind Suchbegriffe, und die Werte sind ein Zähler für diesen Begriff.

  1. Schauen Sie sich jedes Element im Stream an.
  2. Wenn der Begriff in der Map vorhanden ist, erhöhen Sie den zugehörigen Zähler.
  3. Andernfalls, wenn die Karte weniger als k - 1 Einträge enthält, fügen Sie der Karte den Begriff mit einem Zähler von eins hinzu.
  4. Wenn die Karte jedoch bereits k - 1 Einträge enthält, dekrementieren Sie den Zähler in jedem Eintrag. Wenn ein Zähler während dieses Vorgangs Null erreicht, entfernen Sie ihn von der Karte.

Beachten Sie, dass Sie eine unendliche Datenmenge mit einer festen Speichermenge verarbeiten können (nur die Karte mit fester Größe). Die erforderliche Speichermenge hängt nur von der interessierenden Schwelle ab, und die Größe des Streams spielt keine Rolle.

Suchen zählen

In diesem Zusammenhang puffern Sie möglicherweise eine Stunde lang Suchvorgänge und führen diesen Vorgang für die Daten dieser Stunde durch. Wenn Sie einen zweiten Durchgang über das Suchprotokoll dieser Stunde durchführen können, können Sie eine genaue Anzahl der Vorkommen der im ersten Durchgang identifizierten Top- "Kandidaten" abrufen. Oder vielleicht ist es in Ordnung, einen einzigen Durchgang zu machen und alle Kandidaten zu melden, in dem Wissen, dass jedes Element, das vorhanden sein sollte, enthalten ist, und alle Extras sind nur Geräusche, die in der nächsten Stunde verschwinden.

Alle Kandidaten, die die Schwelle des Interesses wirklich überschreiten, werden als Zusammenfassung gespeichert. Wenn Sie diese Zusammenfassungen einen Monat lang aufbewahren und jede Stunde die älteste wegwerfen, erhalten Sie eine gute Annäherung an die häufigsten Suchbegriffe.

54
erickson

Dies ist eines der Forschungsprojekte, die ich gerade durchläuft. Die Anforderung ist fast genau wie Ihre, und wir haben Nice-Algorithmen entwickelt, um das Problem zu lösen. 

Die Eingabe

Die Eingabe ist ein endloser Strom von englischen Wörtern oder Phrasen (wir verweisen sie auf tokens). 

Die Ausgabe

  1. Ausgabe top N Tokens, die wir so gesehen haben Weit (von allen Tokens, die wir haben Gesehen!)
  2. Ausgabe von Top N-Token in einem historischen Fenster, z. B. letzter Tag oder Letzte Woche.

Eine Anwendung dieser Forschung ist das Finden des aktuellen Themas oder der aktuellen Trends in Twitter oder Facebook. Wir haben einen Crawler, der auf der Website crawlt, wodurch ein Wortstrom erzeugt wird, der in das System eingespeist wird. Das System gibt dann die Wörter oder Ausdrücke mit der höchsten Frequenz entweder insgesamt oder historisch aus. Stellen Sie sich vor, der Begriff "Weltmeisterschaft" würde in den letzten Wochen viele Male in Twitter auftauchen. "Paul the octopus" auch. :) 

Zeichenfolge in ganzen Zahlen

Das System hat für jedes Word eine ganzzahlige ID. Zwar gibt es im Internet fast unendlich viele Wörter, aber nach Anhäufung einer großen Anzahl von Wörtern wird die Möglichkeit, neue Wörter zu finden, immer geringer. Wir haben bereits 4 Millionen verschiedene Wörter gefunden und jedem eine eindeutige ID zugewiesen. Dieser gesamte Datensatz kann als Hash-Tabelle in den Speicher geladen werden, was etwa 300 MB Speicherplatz beansprucht. (Wir haben unsere eigene Hashtabelle implementiert. Die Implementierung von Java erfordert einen hohen Speicheraufwand.)

Jede Phrase kann dann als ein Array von Ganzzahlen identifiziert werden. 

Dies ist wichtig, da das Sortieren und Vergleichen auf ganzen Zahlen viel schneller ist als auf Zeichenfolgen.

Archivdaten

Das System speichert Archivdaten für jedes Token. Im Grunde sind es Paare von (Token, Frequency). Die Tabelle, in der die Daten gespeichert werden, wäre jedoch so groß, dass wir die Tabelle physisch partitionieren müssen. Ein Partitionsschema basiert auf Ngrams des Tokens. Wenn das Token ein einzelnes Wort ist, ist es 1 Gramm. Wenn das Token aus zwei Wörtern besteht, handelt es sich um 2 Gramm. Und das geht weiter. Bei etwa 4 Gramm haben wir eine Milliarde Datensätze mit einer Größe von etwa 60 GB.

Verarbeitung eingehender Streams

Das System absorbiert eingehende Sätze, bis der Speicher voll ausgelastet ist (Ya, wir benötigen einen MemoryManager). Nach der Aufnahme von N Sätzen und Speichern im Speicher wird das System angehalten und beginnt, jeden Satz in Wörter und Ausdrücke zu kennzeichnen. Jedes Token (Wort oder Satz) wird gezählt. 

Bei sehr häufigen Spielmarken werden sie immer im Gedächtnis behalten. Bei weniger häufigen Token werden sie nach IDs sortiert (denken Sie daran, dass wir den String in ein Array von Ganzzahlen übersetzen) und in eine Festplattendatei serialisiert. 

(Für Ihr Problem können Sie jedoch, da Sie nur Wörter zählen, nur die gesamte Word-Frequency-Map in den Speicher ablegen. Eine sorgfältig entworfene Datenstruktur würde nur 300 MB Speicher für 4 Millionen verschiedene Wörter benötigen. Hinweis: Verwenden Sie ASCII char zur Darstellung von Strings), und das ist sehr akzeptabel.

In der Zwischenzeit gibt es einen weiteren Prozess, der aktiviert wird, sobald er eine vom System generierte Festplattendatei findet und diese dann zusammenführt. Da die Festplattendatei sortiert ist, würde das Zusammenführen einen ähnlichen Vorgang wie die Zusammenführungssortierung durchführen. Einige Designs müssen auch hier beachtet werden, da zu viele zufällige Festplatten gesucht werden sollen. Die Idee ist, das Lesen (Zusammenführungsvorgang)/Schreiben (Systemausgabe) zur gleichen Zeit zu vermeiden und den Zusammenführungsvorgang beim Schreiben auf eine andere Platte von einer Platte lesen zu lassen. Dies ähnelt dem Implementieren einer Verriegelung. 

Ende des Tages

Am Ende des Tages werden im System viele häufige Token gespeichert, deren Häufigkeit im Speicher gespeichert ist, und viele andere, weniger häufige Token, die in mehreren Plattendateien gespeichert sind (und jede Datei ist sortiert).

Das System spült die In-Memory-Map in eine Plattendatei (sortieren Sie sie). Nun wird das Problem beim Zusammenführen eines Satzes sortierter Datenträgerdateien. Mit einem ähnlichen Prozess erhalten wir am Ende eine sortierte Datenträgerdatei.

Die letzte Aufgabe besteht dann darin, die sortierte Datenträgerdatei in der Archivdatenbank zusammenzuführen. Abhängig von der Größe der Archivdatenbank funktioniert der Algorithmus wie folgt, wenn er groß genug ist:

   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

Die Intuition ist, dass nach einiger Zeit die Anzahl der Einfügungen immer kleiner wird. Immer mehr Operationen werden nur beim Update durchgeführt. Und diese Aktualisierung wird nicht durch den Index bestraft.

Hoffe, diese ganze Erklärung würde helfen. :)

17
SiLent SoNG

Sie könnten eine Hash-Tabelle verwenden, die mit einem binären Suchbaum kombiniert ist . Implementieren Sie ein <search term, count>-Wörterbuch, das Ihnen sagt, wie oft nach jedem Suchbegriff gesucht wurde. 

Offensichtlich ist das Durchlaufen der gesamten Hash-Tabelle jede Stunde, um die Top 10 zu erreichen, sehr schlecht. Wir sprechen hier jedoch von Google. Sie können also davon ausgehen, dass die Top-Ten alle über 10 000 Treffer erzielen werden (es ist jedoch wahrscheinlich eine viel größere Anzahl). Jedes Mal, wenn die Anzahl eines Suchbegriffs 10 000 überschreitet, fügen Sie ihn in die BST ein. Dann müssen Sie jede Stunde nur die ersten 10 von der BST holen, die relativ wenige Einträge enthalten sollte.

Dies löst das Problem der Top-10 aller Zeiten.


Der wirklich schwierige Teil betrifft den Begriff, dass ein Begriff einen anderen Platz im Monatsbericht einnimmt (zum Beispiel könnte "Stack overflow" in den letzten zwei Monaten 50.000 Treffer haben, aber nur 10.000 im letzten Monat, während "Amazon" 40 haben könnte 000 für die letzten zwei Monate, aber 30 000 für den letzten Monat. Sie möchten, dass "Amazon" in Ihrem Monatsbericht vor "Stapelüberlauf" steht. Um dies zu tun, würde ich für alle großen Suchbegriffe (über 10 000 Suchanfragen) eine 30-tägige Liste speichern, die angibt, wie oft dieser Begriff an jedem Tag gesucht wurde. Die Liste würde wie eine Warteschlange FIFO funktionieren: Sie entfernen den ersten Tag und fügen jeden Tag (oder jede Stunde) einen neuen ein. Möglicherweise müssen Sie jedoch mehr Informationen speichern, was mehr Speicherplatz bedeutet. Wenn es sich um Speicher handelt kein Problem, sonst gehen Sie für die "Annäherung", über die sie sprechen.

Das sieht nach einem guten Start aus. Sie können sich dann Gedanken machen, die Begriffe zu beschneiden, die> 10 000 Treffer haben, aber seit langem nicht viele und solche Sachen hatten. 

4
IVlad

Fall i)

Verwalten Sie eine Hashtabelle für alle Suchbegriffe sowie eine sortierte Top-Ten-Liste getrennt von der Hashtabelle. Erhöhen Sie bei jeder Suche das entsprechende Element in der Hashtabelle und überprüfen Sie, ob das Element jetzt mit dem 10. Element in der Top-Ten-Liste umgeschaltet werden soll.

O (1) sucht nach der Top-Ten-Liste und max O(log(n)) Einfügen in die Hashtabelle (unter der Annahme, dass Kollisionen von einem selbstausgleichenden Binärbaum verwaltet werden).

case ii) Anstatt eine große Hashtabelle und eine kleine Liste zu verwalten, pflegen wir eine Hashtabelle und eine sortierte Liste aller Elemente. Bei jeder Suche wird dieser Begriff in der Hashtabelle inkrementiert, und in der sortierten Liste kann der Begriff geprüft werden, um zu sehen, ob er mit dem Begriff dahinter wechseln soll. Ein selbstausgleichender Binärbaum könnte dafür gut funktionieren, da wir ihn auch schnell abfragen müssen (dazu später mehr). 

Zusätzlich führen wir eine Liste von 'Stunden' in Form einer FIFO -Liste (Warteschlange). Jedes "Stunden" -Element würde eine Liste aller Suchen enthalten, die innerhalb dieser bestimmten Stunde durchgeführt wurden. So könnte unsere Stundenliste beispielsweise so aussehen:

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

Dann jede Stunde: Wenn die Liste mindestens 720 Stunden lang ist (dies ist die Anzahl der Stunden in 30 Tagen), schauen Sie sich das erste Element in der Liste an und dekrementieren Sie dieses Element in der Hashtabelle um den entsprechenden Betrag . Anschließend löschen Sie das erste Stundenelement aus der Liste.

Nehmen wir an, wir sind um 721 Uhr und wir sind bereit, die erste Stunde in unserer Liste (oben) zu betrachten. Wir würden das kostenlose Zeug um 56 in der Hashtabelle, lustige Bilder um 321 usw. dekrementieren und dann die Stunde 0 vollständig von der Liste entfernen, da wir sie nie wieder ansehen müssen.

Der Grund, warum wir eine sortierte Liste aller Begriffe pflegen, die schnelle Abfragen zulässt, besteht darin, dass jede Stunde, nachdem wir die Suchbegriffe vor 720 Stunden durchgearbeitet haben, sichergestellt werden muss, dass die Top-Ten-Liste sortiert bleibt. Wenn wir beispielsweise 'free stuff' in der Hashtabelle um 56 dekrementieren, prüfen wir, wo es jetzt in der Liste steht. Da es sich um einen selbstausgleichenden binären Baum handelt, kann dies alles gut in der Zeit O(log(n)) durchgeführt werden.


Edit: Opfergenauigkeit für den Weltraum ...

Es kann nützlich sein, auch eine große Liste in der ersten Liste zu implementieren, wie in der zweiten. Dann könnten wir in beiden Fällen die folgende Speicherplatzoptimierung anwenden: Führen Sie einen Cron-Job aus, um alle Elemente mit Ausnahme der obersten x - Elemente in der Liste zu entfernen. Dies würde den Speicherplatzbedarf gering halten (und dadurch die Abfragen in der Liste schneller machen). Natürlich würde dies zu einem ungefähren Ergebnis führen, dies ist jedoch zulässig. x könnte vor der Bereitstellung der Anwendung basierend auf verfügbarem Speicher berechnet und dynamisch angepasst werden, wenn mehr Speicher verfügbar wird.

3
Cam

Top 10 Suchbegriffe für den letzten Monat

Durch die Verwendung einer speichereffizienten Indizierungs-/Datenstruktur, z. B. eng gepackte Versuche (aus Wikipedia-Einträgen auf Versuche ), wird ungefähr eine Beziehung zwischen dem Speicherbedarf und der n - Anzahl von Begriffen definiert.

Falls der benötigte Speicher verfügbar ist (Annahme 1), können Sie die genaue monatliche Statistik beibehalten und jeden Monat in alle Zeitstatistiken zusammenfassen.

Es gibt auch hier eine Annahme, die den "letzten Monat" als festes Fenster interpretiert. Aber selbst wenn das monatliche Fenster verschoben wird, zeigt das obige Verfahren das Prinzip (das Gleiten kann mit festen Fenstern gegebener Größe angenähert werden).

Dies erinnert mich an Round-Robin-Datenbank mit der Ausnahme, dass einige Statistiken für 'alle Zeiten' berechnet werden (in einem Sinn, dass nicht alle Daten gespeichert werden; rrd konsolidiert Zeiträume ohne Berücksichtigung von Details durch Mittelwertbildung, Summierung oder Auswahl von max/min-Werte, bei einer gegebenen Aufgabe gehen die Informationen, die verloren gehen, zu niederfrequenten Elementen, die Fehler verursachen können).

Annahme 1

Wenn wir keine perfekten Statistiken für den gesamten Monat halten können, sollten wir in der Lage sein, eine bestimmte Periode P zu finden, für die wir in der Lage sein sollten, perfekte Statistiken zu halten .. _. Zum Beispiel, vorausgesetzt, wir haben perfekte Statistiken für einen bestimmten Zeitraum P , die n-mal in Monat geht.
Perfekte Statistiken definieren die Funktion f(search_term) -> search_term_occurance.

Wenn wir alle n perfekten Statiktabellen im Speicher behalten können, können gleitende Monatsstatistiken folgendermaßen berechnet werden:

  • statistiken für den neuesten Zeitraum hinzufügen
  • werte für die älteste Zeit entfernen (also müssen wir n perfekte Statiktabellen behalten)

Wenn wir auf aggregierter Ebene (monatlich) jedoch nur die Top 10 behalten, können wir viele Daten aus den vollständigen Statistiken des festgelegten Zeitraums verwerfen. Dies gibt bereits einen Arbeitsablauf vor, der den Speicherbedarf festlegt (vorausgesetzt, die Obergrenze der perfekten Statiktabelle ist für Periode P festgelegt).

Das Problem mit dem oben beschriebenen Verfahren ist, dass, wenn wir Informationen nur für Top-10-Begriffe für ein Schiebefenster beibehalten (ähnlich wie für alle Zeit), die Statistiken für Suchbegriffe stimmen werden, die in einem Zeitraum ihren Höchststand erreichen, aber möglicherweise nicht angezeigt werden Statistiken für Suchbegriffe, die im Laufe der Zeit ständig einfließen.

Dies kann dadurch ausgeglichen werden, dass Informationen zu mehr als zehn Top-Termini, zum Beispiel Top-100-Termini, beibehalten werden, wobei gehofft wird, dass die Top 10 korrekt sind.

Meines Erachtens könnte eine weitere Analyse die Mindestanzahl von Vorkommnissen betreffen, die erforderlich sind, damit ein Eintrag Teil der Statistik wird (was mit dem maximalen Fehler zusammenhängt).

(Bei der Entscheidung, welche Einträge Teil der Statistik werden sollen, könnte man auch die Trends überwachen und verfolgen, zum Beispiel, wenn eine lineare Extrapolation der Vorkommnisse in jeder Periode P für jeden Begriff anzeigt, dass der Begriff in einem oder zwei Monaten signifikant wird kann bereits mit dem Tracking beginnen. Ein ähnliches Prinzip gilt für das Entfernen des Suchbegriffs aus dem Tracking Pool.

Der schlimmste Fall für das oben Gesagte ist, wenn Sie viele fast gleich häufige Begriffe haben und sich diese ständig ändern (wenn Sie beispielsweise nur 100 Begriffe nachverfolgen, dann treten die Top 150-Begriffe gleich häufig auf, die ersten 50 sind jedoch häufiger im ersten Monat und Sonst wird die Statistik häufig nicht korrekt aufbewahrt.

Es könnte auch einen anderen Ansatz geben, der nicht in der Speichergröße festgelegt ist (genau genommen ist dies auch nicht der oben genannte), der die minimale Signifikanz in Bezug auf Vorkommen/Zeitraum (Tag, Monat, Jahr, alle Zeit) definieren würde, für die der Speicher aufbewahrt werden soll Statistiken. Dies könnte einen maximalen Fehler in jeder Statistik während der Aggregation garantieren (siehe Round Robin erneut).

2
Unreason

Genaue Lösung

Erstens, eine Lösung, die korrekte Ergebnisse garantiert, aber viel Speicherplatz benötigt (große Karte).

"Allzeit" -Variante

Pflegen Sie eine Hash-Map mit Abfragen als Schlüsseln und deren Anzahl als Werten. Behalten Sie außerdem eine Liste mit den 10 häufigsten Abfragen und der Zählung der 10. Häufigkeit (eine Schwelle) bei.

Aktualisieren Sie die Karte ständig, während der Abfragestrom gelesen wird. Gehen Sie folgendermaßen vor, wenn ein Zähler den aktuellen Schwellenwert überschreitet: Entfernen Sie die 10. Abfrage aus der Liste "Top 10", ersetzen Sie sie durch die gerade aktualisierte Abfrage und aktualisieren Sie auch den Schwellenwert.

Variante "vergangenen Monat"

Behalten Sie die "Top 10" -Liste bei und aktualisieren Sie sie wie oben. Behalten Sie eine ähnliche Karte bei, aber speichern Sie diesmal Vektoren von 30 * 24 = 720 (eine für jede Stunde) als Werte. Führen Sie jede Stunde für jeden Schlüssel Folgendes aus: Entfernen Sie den ältesten Zähler aus dem Vektor, und fügen Sie am Ende einen neuen hinzu (auf 0 initialisiert). Entfernen Sie den Schlüssel aus der Karte, wenn der Vektor Null ist. Außerdem muss jede Stunde die "Top 10" -Liste von Grund auf neu berechnet werden.

Hinweis: Ja, diesmal speichern wir 720 Ganzzahlen statt einer, aber es gibt viel weniger Schlüssel (die All-Time-Variante hat einen wirklich langen Schwanz).

Annäherungen

Diese Annäherungen garantieren nicht die richtige Lösung, sind jedoch weniger speicherintensiv.

  1. Verarbeiten Sie jede N-te Abfrage und überspringen Sie den Rest.
  2. (Nur für alle Zeitvarianten) Behalten Sie höchstens M Schlüsselwertpaare in der Karte (M sollte so groß sein, wie Sie es sich leisten können). Es ist eine Art LRU-Cache: Wenn Sie eine Abfrage lesen, die sich nicht in der Map befindet, entfernen Sie die zuletzt verwendete Abfrage durch Anzahl 1 und ersetzen Sie sie durch die aktuell verarbeitete Abfrage.
2
Bolo

Grobes Denken ...

Für die Top 10 aller Zeiten

  • Verwendung einer Hash-Sammlung, in der eine Zählung für jeden Begriff gespeichert wird (Begriffe desinfizieren usw.)
  • Ein sortiertes Array, das die fortlaufenden Top 10 enthält, ein Term/Count, der zu diesem Array hinzugefügt wird, wenn der Count eines Terms gleich oder größer als der kleinste Count im Array ist

Für monatliche Top 10, die stündlich aktualisiert werden:

  • Bei Verwendung eines Arrays, das für die Anzahl der seit dem Start modulo 744 verstrichenen Stunden (Anzahl der Stunden pro Monat) indiziert ist, bestehen die Arrayeinträge aus einer Hash-Sammlung, in der eine Zählung für jeden in diesem Stundenbereich gefundenen Begriff gespeichert wird. Ein Eintrag wird zurückgesetzt, wenn sich der Stundenzähler ändert
  • die Statistiken in dem für Stundenfenster indizierten Array müssen immer dann erfasst werden, wenn sich der aktuelle Stundenzeitzähler ändert (höchstens einmal pro Stunde), indem der Inhalt dieses in Stundenzeilen indizierten Arrays kopiert und reduziert wird

Ähm ... macht Sinn? Ich habe das nicht so durchdacht wie im wirklichen Leben

Ah ja, ich habe vergessen zu erwähnen, dass das stündliche "Kopieren/Abflachen", das für die monatlichen Statistiken erforderlich ist, tatsächlich den gleichen Code wiederverwenden kann, der für die Top 10 aller Zeiten verwendet wird, ein Nizza-Nebeneffekt.

2
R. Hill

Wie sieht es mit einer Anpassung des "Clock Page Replacement Algorithmus" aus (auch als "second-chance" bezeichnet)? Ich kann mir vorstellen, dass es sehr gut funktioniert, wenn die Suchanfragen gleichmäßig verteilt werden (dh die meisten gesuchten Begriffe erscheinen regelmäßig und nicht 5 Millionen Mal hintereinander und dann nie wieder).

Hier ist eine visuelle Darstellung des Algorithmus: clock page replacement algorithm

2
Dave O.

Speichern Sie die Anzahl der Suchbegriffe in einer riesigen Hash-Tabelle, in der bei jeder neuen Suche ein bestimmtes Element um eins erhöht wird. Behalten Sie den Überblick über die Top-20-Suchbegriffe. Wenn das Element an 11. Stelle erhöht wird, prüfen Sie, ob Positionen mit # 10 * getauscht werden müssen (es ist nicht notwendig, die Top 10 zu sortieren; Sie müssen lediglich zwischen 10. und 11. unterscheiden).

*Ähnliche Überprüfungen müssen durchgeführt werden, um zu sehen, ob ein neuer Suchbegriff auf Platz 11 liegt. Daher sprudelt dieser Algorithmus auch auf andere Suchbegriffe - daher vereinfache ich etwas.

0
Ether

manchmal ist die beste Antwort "Ich weiß es nicht". 

Ich werde einen tieferen Stich nehmen. Mein erster Instinkt wäre, die Ergebnisse in ein Q zu füttern. Ein Prozess würde fortlaufend Elemente bearbeiten, die in das Q kommen 

begriff -> zählen

jedes Mal, wenn ein Q-Element verarbeitet wird, suchen Sie einfach nach dem Suchbegriff und erhöhen die Anzahl. 

Gleichzeitig würde ich eine Liste mit Verweisen auf die Top-10-Einträge in der Karte führen. 

Sehen Sie für den aktuell implementierten Eintrag nach, ob seine Anzahl größer ist als die Anzahl der kleinsten Einträge in den Top 10. (falls nicht bereits in der Liste enthalten). Ist dies der Fall, ersetzen Sie den kleinsten durch den Eintrag.

Ich denke das würde funktionieren. Keine Operation ist zeitintensiv. Sie müssten einen Weg finden, um die Größe der Count-Map zu verwalten. aber das sollte für ein Interview gut genug sein.

Sie erwarten keine Lösung, die sehen will, ob Sie denken können. Sie müssen nicht die Lösung dann und dort schreiben ....

0
hvgotcodes

Was ist mit einem Splay Tree mit 10 Knoten? Wenn Sie versuchen, auf einen Wert (Suchbegriff) zuzugreifen, der nicht in der Baumstruktur enthalten ist, werfen Sie ein beliebiges Blatt aus, fügen Sie stattdessen den Wert ein und greifen Sie darauf zu.

Die Idee dahinter ist die gleiche wie in meiner anderen Antwort . Unter der Annahme, dass auf die Suchbegriffe regelmäßig/regelmäßig zugegriffen wird, sollte diese Lösung sehr gut funktionieren.

bearbeiten

Man könnte auch einige weitere Suchbegriffe in der Baumstruktur speichern (das gleiche gilt für die Lösung, die ich in meiner anderen Antwort vorschlage), um einen Knoten nicht zu löschen, auf den möglicherweise bald wieder zugegriffen wird. Je mehr Werte darin gespeichert werden, desto besser sind die Ergebnisse.

0
Dave O.

Eine Möglichkeit ist, dass Sie für jede Suche diesen Suchbegriff und seinen Zeitstempel speichern. Auf diese Weise ist das Finden der Top Ten für einen beliebigen Zeitraum einfach ein Vergleich aller Suchbegriffe innerhalb des angegebenen Zeitraums.

Der Algorithmus ist einfach, aber der Nachteil wäre ein größerer Speicher- und Zeitaufwand.

0
Jesse Jashinsky

Das Problem ist nicht universell lösbar, wenn Sie über eine festgelegte Menge an Speicher verfügen und über einen unendlich großen (sehr sehr großen) Datenstrom von Token verfügen.

Eine grobe Erklärung ...

Um zu sehen, warum, betrachten Sie einen Tokenstrom, der ein bestimmtes Token (d. H. Word) T alle N Token im Eingabestrom hat.

Angenommen, der Speicher kann Verweise (Word-ID und Anzahl) auf höchstens M Token enthalten.

Mit diesen Bedingungen ist es möglich, einen Eingabestrom zu konstruieren, bei dem das Token T niemals erkannt wird, wenn N groß genug ist, so dass der Strom verschiedene M-Token zwischen T enthält.

Dies ist unabhängig von den Details des Top-N-Algorithmus. Es hängt nur von der Grenze M ab.

Um zu sehen, warum dies zutrifft, betrachten Sie den eingehenden Strom, der aus Gruppen von zwei identischen Token besteht:

T a1 a2 a3 ... a-M T b1 b2 b3 ... b-M ...

wobei die a und b alle gültigen Token sind, die nicht gleich T sind.

Beachten Sie, dass in diesem Stream das T zweimal für a-i und b-i erscheint. Es erscheint jedoch selten genug, um aus dem System gespült zu werden.

Beginnend mit einem leeren Speicher belegt das erste Token (T) einen Steckplatz im Speicher (durch M begrenzt). Dann verbraucht a1 einen Slot bis a- (M-1), wenn das M erschöpft ist.

Wenn a-M ankommt, muss der Algorithmus ein Symbol fallen lassen, also das T . Das nächste Symbol ist b-1, wodurch a-1 geleert wird usw.

Das T bleibt also nicht lange genug im Gedächtnis, um eine echte Zählung aufzubauen. Kurz gesagt: Jeder Algorithmus verfehlt ein Token mit einer ausreichend niedrigen lokalen Frequenz, aber einer hohen globalen Frequenz (über die Länge des Streams).

0
david marcus

Keine Ahnung, ob ich es richtig verstehe oder nicht. Meine Lösung verwendet Heap. Aufgrund von Top 10-Suchobjekten erzeuge ich einen Heap mit der Größe 10. Aktualisieren Sie diesen Heap dann mit einer neuen Suche. Wenn die Häufigkeit einer neuen Suche größer als der Heap-Wert (Max Heap) ist, aktualisieren Sie sie. Verzicht auf die mit der kleinsten Frequenz. 

Wie die Häufigkeit der spezifischen Suche berechnet wird, wird jedoch mit etwas anderem gezählt. Vielleicht, wie jeder gesagt hat, der Datenstrom-Algorithmus ... 

0
Chris

Verwenden Sie cm-sketch, um die Anzahl aller Suchvorgänge seit Beginn zu speichern, und halten Sie einen Min-Heap der Größe 10 für Top 10. .. Für ein monatliches Ergebnis behalten Sie 30 cm-sketch/hash-table und min-heap bei. Jeder einzelne zählt und zählt die letzten 30, 29, 1 Tage. Als Tagesticket löschen Sie das letzte und verwenden Sie es als Tag 1 . Für das stündliche Ergebnis gilt: Halten Sie 60 Hash-Tische und Min-Heap und beginnen Sie die letzten 60, 59, ... 1 Minute zu zählen. Löschen Sie als Minutentakt das letzte und verwenden Sie es als Minute 1.

Das monatliche Ergebnis ist im Bereich von 1 Tag genau, das stündliche Ergebnis im Bereich von 1 Minute

0
Jingyi Fang