Ich bereite mich gerade auf ein Interview vor und es erinnerte mich an eine Frage, die mir einmal in einem früheren Interview gestellt wurde und ungefähr so ​​lautete:

"Sie wurden gebeten, eine Software zu entwickeln, mit der die Top-10-Suchbegriffe bei Google kontinuierlich angezeigt werden. Sie erhalten Zugriff auf einen Feed, der einen endlosen Echtzeitstrom von Suchbegriffen bietet, die derzeit bei Google gesucht werden. Beschreiben Sie, welcher Algorithmus und welche Datenstrukturen verwendet werden Sie würden dies verwenden, um dies zu implementieren. Sie müssen zwei Varianten entwerfen:

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

(ii) Zeigen Sie nur die 10 wichtigsten Suchbegriffe des letzten Monats an, die stündlich aktualisiert werden.

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

Im ersten Teil werden die 10 häufigsten Elemente in einer kontinuierlich wachsenden Teilsequenz einer unendlichen Liste abgefragt. Ich habe mich mit Auswahlalgorithmen befasst, konnte jedoch keine Online-Versionen finden, 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 Top-10-Liste ständig aktualisiert wird. Sie müssen also Ihre Top-10 über ein Schiebefenster berechnen.

Irgendwelche Ideen?

Nun, sieht aus wie eine Menge 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, betreten wir den Bereich der Datenstromalgorithmen .

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

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

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

Heh, nette Interviewfrage.

Übersicht über die Frequenzschätzung

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

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 nur dann eindeutig identifiziert werden kann, wenn es in mehr als 50% der Fälle auftritt. Füttere diesen Algorithmus mit einem Strom von N verschiedenen Elementen und füge dann weitere N - 1 Kopien eines Elements x für insgesamt 2N - 1 Elemente hinzu. Wenn der Algorithmus Ihnen sagt, dass x 50% der Gesamtmenge überschreitet, muss es sich im ersten Stream befunden haben. Wenn nicht, war x nicht im ursprünglichen Stream. Damit der Algorithmus diese Bestimmung vornehmen kann, muss er den anfänglichen Stream (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 liefern diese hier beschriebenen Frequenzalgorithmen eine Schätzung, die jedes Element identifiziert, das den Schwellenwert überschreitet, sowie einige Elemente, die um einen bestimmten Spielraum darunter liegen. Beispielsweise liefert der Mehrheitsalgorithmus unter Verwendung eines einzelnen Zählers immer ein Ergebnis. Wenn ein Element 50% des Streams überschreitet, wird es gefunden. Es kann aber auch einen Gegenstand geben, der nur einmal vorkommt. Sie würden es nicht wissen, ohne einen zweiten Durchgang über die Daten zu machen (wiederum mit einem einzigen Zähler, aber nur nach diesem Element suchen).

Der häufige Algorithmus

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

Geben Sie den Schwellenwert 1 / k an . 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 Karte vorhanden ist, erhöhen Sie den zugehörigen Zähler.
3. 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 aus 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 Suchvorgang und führen diesen Vorgang für die Daten dieser Stunde aus. Wenn Sie im Suchprotokoll dieser Stunde einen zweiten Durchgang 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 jeder Gegenstand, der dort sein sollte, enthalten ist, und alle Extras sind nur Geräusche, die in der nächsten Stunde verschwinden.

Alle Kandidaten, die die interessierende Schwelle tatsächlich überschreiten, werden als Zusammenfassung gespeichert. Behalten Sie diese Zusammenfassungen im Wert von einem Monat bei und werfen Sie jede Stunde die ältesten weg, und Sie hätten eine gute Annäherung an die häufigsten Suchbegriffe.

Dies ist eines der Forschungsprojekte, die ich derzeit durchlaufe. Die Anforderung entspricht fast genau Ihrer, und wir haben nette Algorithmen entwickelt, um das Problem zu lösen.

Die Eingabe

Die Eingabe ist ein endloser Strom englischer Wörter oder Phrasen (wir bezeichnen sie als tokens).

Die Ausgabe

1. Geben Sie die Top-N-Token aus, die wir bisher gesehen haben (von allen Token, die wir gesehen haben!).
2. Geben Sie die Top-N-Token in einem historischen Fenster aus, z. B. am letzten Tag oder in der letzten Woche.

Eine Anwendung dieser Forschung besteht darin, das aktuelle Thema oder die aktuellen Trends des Themas in Twitter oder Facebook zu finden. Wir haben einen Crawler, der auf der Website crawlt und einen Strom von Wörtern generiert, der in das System eingespeist wird. Das System gibt dann die Wörter oder Phrasen der höchsten Frequenz entweder insgesamt oder historisch aus. Stellen Sie sich vor, in den letzten Wochen würde der Satz "Weltmeisterschaft" in Twitter viele Male vorkommen. So auch "Paul der Tintenfisch". :) :)

String in Ganzzahlen

Das System hat für jedes Wort eine Ganzzahl-ID. Es gibt zwar fast unendlich viele mögliche Wörter im Internet, aber nach dem Sammeln 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 und benötigt ungefähr 300 MB Speicher. (Wir haben unsere eigene Hash-Tabelle implementiert. Die Implementierung von Java erfordert einen enormen Speicheraufwand.)

Jede Phrase kann dann als Array von ganzen Zahlen identifiziert werden.

Dies ist wichtig, da das Sortieren und Vergleichen von Ganzzahlen viel schneller ist als bei Zeichenfolgen.

Daten archivieren

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

Eingehende Streams verarbeiten

Das System absorbiert eingehende Sätze, bis der Speicher voll ausgelastet ist (Ja, wir benötigen einen MemoryManager). Nachdem Sie N Sätze genommen und im Speicher gespeichert haben, hält das System inne und beginnt, jeden Satz in Wörter und Phrasen zu unterteilen. Jeder Token (Wort oder Satz) wird gezählt.

Bei sehr häufigen Token werden sie immer gespeichert. 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.

(Da Sie jedoch nur Wörter zählen, können Sie für Ihr Problem nur alle Wortfrequenzkarten im Speicher ablegen. Eine sorgfältig entworfene Datenstruktur würde nur 300 MB Speicher für 4 Millionen verschiedene Wörter belegen. Einige Hinweise: Verwenden Sie ASCII-Zeichen für Strings darstellen), und dies ist sehr akzeptabel.

In der Zwischenzeit wird ein weiterer Prozess aktiviert, sobald eine vom System generierte Festplattendatei gefunden und zusammengeführt wird. Da die Datenträgerdatei sortiert ist, würde das Zusammenführen einen ähnlichen Vorgang wie das Zusammenführen von Sortierungen erfordern. Auch hier muss auf einige Designs geachtet werden, da wir zu viele zufällige Festplattensuchen vermeiden möchten. Die Idee ist, das gleichzeitige Lesen (Zusammenführungsprozess) / Schreiben (Systemausgabe) zu vermeiden und den Zusammenführungsprozess beim Schreiben auf eine andere Festplatte von einer Festplatte lesen zu lassen. Dies ähnelt der Implementierung einer Sperre.

Ende des Tages

Am Ende des Tages werden auf dem System viele häufige Token mit einer im Speicher gespeicherten Häufigkeit und viele andere weniger häufige Token in mehreren Datenträgerdateien gespeichert (und jede Datei wird sortiert).

Das System leert die In-Memory-Map in eine Festplattendatei (sortiert sie). Jetzt wird das Problem darin bestehen, eine Reihe sortierter Datenträgerdateien zusammenzuführen. Mit einem ähnlichen Verfahren würden wir am Ende eine sortierte Datenträgerdatei erhalten.

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 Aktualisieren ausgeführt. Und diese Aktualisierung wird nicht durch den Index bestraft.

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

Sie können eine Hash-Tabelle in Kombination mit einem binären Suchbaum verwenden . Implementieren Sie ein <search term, count>Wörterbuch, das angibt, wie oft nach jedem Suchbegriff gesucht wurde.

Offensichtlich ist es sehr schlecht, jede Stunde die gesamte Hash-Tabelle zu wiederholen, um die Top 10 zu erreichen . Aber es handelt sich um Google, also können Sie davon ausgehen, dass die Top Ten alle über 10 000 Treffer erzielen werden (wahrscheinlich ist es jedoch eine viel größere Zahl). Fügen Sie den Suchbegriff jedes Mal, wenn er 10 000 überschreitet, in die BST ein. Dann müssen Sie jede Stunde nur die ersten 10 von der BST erhalten, die relativ wenige Einträge enthalten sollte.

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

Der wirklich knifflige Teil besteht darin, dass ein Begriff den Platz eines anderen im Monatsbericht einnimmt (zum Beispiel könnte "Stapelüberlauf" in den letzten zwei Monaten 50.000 Treffer haben, im letzten Monat jedoch nur 10 000, während "Amazon" 40 Treffer 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 monatlichen Bericht vor "Stapelüberlauf" steht. Zu diesem Zweck würde ich für alle wichtigen Suchbegriffe (über 10 000 Suchanfragen aller Zeiten) eine 30-Tage-Liste speichern, in der angegeben ist, wie oft an jedem Tag nach diesem Begriff gesucht wurde. Die Liste würde wie eine FIFO-Warteschlange funktionieren: Sie entfernen den ersten Tag und fügen jeden Tag (oder jede Stunde) eine neue ein. Dann müssen Sie möglicherweise mehr Informationen speichern, was mehr Speicherplatz bedeutet. Wenn Speicher kein Problem darstellt, tun Sie dies es, sonst für diese "Annäherung" gehen

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

Fall i)

Pflegen Sie eine Hashtabelle für alle Suchbegriffe sowie eine sortierte Top-Ten-Liste, die von der Hashtabelle getrennt ist. Erhöhen Sie bei jeder Suche das entsprechende Element in der Hashtabelle und prüfen Sie, ob dieses Element jetzt durch das 10. Element in der Top-Ten-Liste ersetzt werden soll.

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

Fall ii) Anstatt eine große Hashtabelle und eine kleine Liste zu führen, führen wir eine Hashtabelle und eine sortierte Liste aller Elemente. Bei jeder Suche wird dieser Begriff in der Hashtabelle erhöht, und in der sortierten Liste kann der Begriff überprüft werden, um festzustellen, ob er mit dem Begriff danach wechseln soll. Ein selbstausgleichender Binärbaum könnte hierfür gut funktionieren, da wir ihn auch schnell abfragen müssen müssen (dazu später mehr).

Zusätzlich führen wir eine Liste von 'Stunden' in Form einer FIFO-Liste (Warteschlange). Jedes 'Stunde'-Element würde eine Liste aller Suchvorgänge enthalten, die innerhalb dieser bestimmten Stunde durchgeführt wurden. So könnte beispielsweise unsere Stundenliste folgendermaßen 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 (das ist die Anzahl der Stunden in 30 Tagen), sehen Sie sich das erste Element in der Liste an und dekrementieren Sie dieses Element in der Hashtabelle für jeden Suchbegriff um den entsprechenden Betrag . Löschen Sie anschließend das erste Stundenelement aus der Liste.

Nehmen wir also an, wir sind um 721 Uhr und wir sind bereit, uns die erste Stunde in unserer Liste (oben) anzusehen. Wir würden kostenlose Inhalte in der Hashtabelle um 56, lustige Bilder um 321 usw. verringern und dann 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 führen, die schnelle Abfragen ermöglicht, liegt darin, dass wir jede Stunde nach dem Durchsuchen der Suchbegriffe von vor 720 Stunden sicherstellen müssen, dass die Top-Ten-Liste sortiert bleibt. Wenn wir zum Beispiel '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ärbaum handelt, kann all dies in O (log (n)) Zeit gut erreicht werden.

Edit: Opfergenauigkeit für den Weltraum ...

Es kann nützlich sein, auch in der ersten eine große 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 außer den obersten x Elementen in der Liste zu entfernen . Dies würde den Platzbedarf niedrig halten (und dadurch Abfragen in der Liste beschleunigen). Natürlich würde dies zu einem ungefähren Ergebnis führen, aber dies ist zulässig. x kann vor der Bereitstellung der Anwendung basierend auf dem verfügbaren Speicher berechnet und dynamisch angepasst werden, wenn mehr Speicher verfügbar wird.

Grobes Denken ...

Für die Top 10 aller Zeiten

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

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

• Unter Verwendung eines Arrays, das nach der Anzahl der seit dem Start von Modulo 744 verstrichenen Stunden (der Anzahl der Stunden während eines Monats) indiziert ist, bestehen diese Array-Einträge aus einer Hash-Sammlung, in der eine Anzahl für jeden Begriff gespeichert wird, der während dieses Stundenfensters angetroffen wird. Ein Eintrag wird zurückgesetzt, wenn sich der Stundenschlitzzähler ändert
• Die Statistiken im Array, die auf dem Stundenschlitz indiziert sind, müssen erfasst werden, wenn sich der aktuelle Stundenschlitzzähler ändert (höchstens einmal pro Stunde), indem der Inhalt dieses Arrays, der auf Stundenschlitzen indiziert ist, kopiert und reduziert wird

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

Ah ja, vergessen zu erwähnen, dass das stündliche "Kopieren / Reduzieren", das für die monatlichen Statistiken erforderlich ist, tatsächlich denselben Code wiederverwenden kann, der für die Top 10 aller Zeiten verwendet wurde, ein netter Nebeneffekt.

Genaue Lösung

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

"Allzeit" -Variante

Pflegen Sie eine Hash-Map mit Abfragen als Schlüssel und deren Anzahl als Werte. Führen Sie außerdem eine Liste mit den 10 häufigsten Abfragen und der Anzahl der 10. häufigsten Abfragen (einem Schwellenwert).

Aktualisieren Sie die Karte ständig, während der Abfragestream gelesen wird. Gehen Sie wie folgt vor, wenn eine Zählung 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 "Letzter Monat"

Behalten Sie die gleiche "Top 10" -Liste bei und aktualisieren Sie sie auf die gleiche Weise wie oben. Behalten Sie auch eine ähnliche Karte bei, aber dieses Mal zählen Vektoren von 30 * 24 = 720 (einer 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 (auf 0 initialisierten) hinzu. Entfernen Sie den Schlüssel von der Karte, wenn der Vektor Null ist. Außerdem müssen Sie jede Stunde die "Top 10" -Liste von Grund auf neu berechnen.

Hinweis: Ja, diesmal speichern wir 720 Ganzzahlen anstelle von einer, aber es gibt viel weniger Schlüssel (die Allzeitvariante 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 Allzeitvarianten) Behalten Sie höchstens M Schlüssel-Wert-Paare in der Karte (M sollte so groß sein, wie Sie es sich leisten können). Es ist eine Art LRU-Cache: Entfernen Sie jedes Mal, wenn Sie eine Abfrage lesen, die nicht in der Karte enthalten ist, die zuletzt verwendete Abfrage mit der Anzahl 1 und ersetzen Sie sie durch die aktuell verarbeitete Abfrage.

Top 10 Suchbegriffe für den letzten Monat

Die Verwendung einer speichereffizienten Indizierung / Datenstruktur, wie z. B. dicht gepackte Versuche (aus Wikipedia-Einträgen zu Versuchen ), definiert ungefähr eine Beziehung zwischen Speicherbedarf und n - Anzahl von Begriffen.

Falls der erforderliche Speicher verfügbar ist ( Annahme 1 ), können Sie die genaue monatliche Statistik beibehalten und jeden Monat zu einer Zeitstatistik zusammenfassen.

Hier gibt es auch 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 Verschieben kann mit festen Fenstern einer bestimmten Größe angenähert werden).

Dies erinnert mich an eine Round-Robin-Datenbank mit der Ausnahme, dass einige Statistiken für "alle Zeiten" berechnet werden (in dem Sinne, dass nicht alle Daten erhalten bleiben; rrd konsolidiert Zeiträume ohne Berücksichtigung von Details durch Mittelung, Summierung oder Auswahl von Max / Min-Werten). Bei einer bestimmten Aufgabe gehen Details zu niederfrequenten Elementen verloren, die zu Fehlern führen können.

Annahme 1

Wenn wir nicht den ganzen Monat über perfekte Statistiken halten können, sollten wir in der Lage sein, einen bestimmten Zeitraum P zu finden, für den wir perfekte Statistiken halten können. Angenommen, wir haben perfekte Statistiken für einen Zeitraum P, der n-mal in den Monat geht.
Perfekte Statistiken definieren die Funktion f(search_term) -> search_term_occurance.

Wenn wir alle nperfekten Stat-Tabellen im Speicher behalten können, können gleitende monatliche Statistiken wie folgt berechnet werden:

• füge Statistiken für den neuesten Zeitraum hinzu
• Entfernen Sie die Statistiken für den ältesten Zeitraum (daher müssen wir nperfekte Stat-Tabellen führen).

Wenn wir jedoch nur die Top 10 auf aggregierter Ebene (monatlich) behalten, können wir viele Daten aus den vollständigen Statistiken des festgelegten Zeitraums verwerfen. Dies ergibt bereits eine Arbeitsprozedur, die Speicheranforderungen festgelegt hat (unter der Annahme einer Obergrenze für die perfekte Stat-Tabelle für Periode P).

Das Problem mit dem obigen Verfahren besteht darin, dass, wenn wir nur Informationen zu den Top-10-Begriffen für ein Schiebefenster behalten (ähnlich für alle Zeiten), die Statistiken für Suchbegriffe korrekt sind, die in einem bestimmten Zeitraum ihren Höhepunkt erreichen, die jedoch möglicherweise nicht angezeigt werden Statistiken für Suchbegriffe, die im Laufe der Zeit ständig einfließen.

Dies kann ausgeglichen werden, indem Informationen zu mehr als den Top-10-Begriffen gespeichert werden, z. B. zu den Top-100-Begriffen, in der Hoffnung, dass die Top-10 korrekt sind.

Ich denke, dass eine weitere Analyse die minimale Anzahl von Ereignissen in Beziehung setzen könnte, die erforderlich sind, damit ein Eintrag Teil der Statistiken wird (was sich auf den maximalen Fehler bezieht).

(Bei der Entscheidung, welche Einträge Teil der Statistiken werden sollen, kann man auch die Trends überwachen und verfolgen. Wenn beispielsweise eine lineare Extrapolation der Vorkommen in jeder Periode P für jeden Begriff besagt, dass der Begriff in ein oder zwei Monaten von Bedeutung sein wird Möglicherweise wird bereits mit der Verfolgung begonnen. Ein ähnliches Prinzip gilt für das Entfernen des Suchbegriffs aus dem verfolgten Pool.)

Der schlimmste Fall für die oben genannten Fälle ist, wenn Sie viele fast gleich häufige Begriffe haben und diese sich ständig ändern (z. B. wenn Sie nur 100 Begriffe verfolgen, wenn die Top 150-Begriffe gleich häufig vorkommen, die Top 50 jedoch häufiger im ersten Monat und Damit die Statistiken nicht oft einige Zeit später nicht korrekt gespeichert werden.

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

Was ist mit einer Anpassung des "Algorithmus zum Ersetzen von Uhrenseiten" (auch als "zweite Chance" bekannt)? Ich kann mir vorstellen, dass es sehr gut funktioniert, wenn die Suchanfragen gleichmäßig verteilt sind (das heißt, die meisten gesuchten Begriffe erscheinen regelmäßig und nicht 5 Millionen Mal hintereinander und dann nie wieder).

Hier ist eine visuelle Darstellung des Algorithmus:

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 die Top 20 der Suchbegriffe im Auge. Wenn das Element auf Platz 11 erhöht wird, prüfen Sie, ob es Positionen mit # 10 * tauschen muss (es ist nicht erforderlich, die Top 10 sortiert zu halten; alles, was Sie interessiert, ist die Unterscheidung zwischen Platz 10 und 11).

* _{Ähnliche Überprüfungen müssen durchgeführt werden, um festzustellen, ob ein neuer Suchbegriff an 11. Stelle steht. Daher wird dieser Algorithmus auch auf andere Suchbegriffe übertragen - daher vereinfache ich dies ein wenig.}

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

Ich werde einen tieferen Stich machen. Mein erster Instinkt wäre, die Ergebnisse in ein Q einzuspeisen. Ein Prozess würde kontinuierlich Elemente verarbeiten, die in das Q kommen. Der Prozess würde eine Karte von führen

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.

Überprüfen Sie für den aktuell implementierten Eintrag, ob seine Anzahl größer ist als die Anzahl der Anzahl der kleinsten Einträge in den Top 10. (falls nicht bereits in der Liste enthalten). Wenn dies der Fall ist, 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 Zählkarte zu verwalten. aber das sollte gut genug für eine Interviewantwort sein.

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

Eine Möglichkeit besteht darin, dass Sie für jede Suche diesen Suchbegriff und seinen Zeitstempel speichern. Auf diese Weise müssen Sie nur die Top Ten für einen bestimmten Zeitraum finden, indem Sie alle Suchbegriffe innerhalb des angegebenen Zeitraums vergleichen.

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

Was ist mit einem Splay Tree mit 10 Knoten? Jedes Mal, wenn Sie versuchen, auf einen Wert (Suchbegriff) zuzugreifen, der nicht im Baum enthalten ist, werfen Sie ein Blatt weg, fügen Sie stattdessen den Wert ein und greifen Sie darauf zu.

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

bearbeiten

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

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

Wie die Häufigkeit der spezifischen Suche berechnet wird, hängt jedoch von etwas anderem ab. Vielleicht, wie alle sagten, der Datenstrom-Algorithmus ....

Verwenden Sie die cm-Skizze, um die Anzahl aller Suchvorgänge seit Beginn zu speichern. Behalten Sie einen Min-Heap der Größe 10 für die Top 10 bei. Für ein monatliches Ergebnis behalten Sie jeweils 30 cm-Skizze / Hash-Tabelle und den Min-Heap bei Zählen und Aktualisieren von den letzten 30, 29 .., 1 Tag. Löschen Sie als Tageskarte die letzte und verwenden Sie sie als Tag 1. Behalten Sie für das Stundenergebnis 60 Hash-Tabellen und Min-Heap bei und beginnen Sie mit der Zählung für die letzten 60, 59, ... 1 Minute. Löschen Sie als Minutenpass den letzten und verwenden Sie ihn als Minute 1.

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

Das Problem ist nicht allgemein lösbar, wenn Sie eine feste Speichermenge und einen "unendlichen" (denken Sie sehr, sehr großen) Strom von Token haben.

Eine grobe Erklärung ...

Um zu sehen, warum, betrachten Sie einen Token-Stream, der ein bestimmtes Token (dh ein Wort) T alle N Token im Eingabestream enthält.

Nehmen Sie außerdem an, dass der Speicher Verweise (Wort-ID und Anzahl) auf höchstens M Token enthalten kann.

Unter diesen Bedingungen ist es möglich, einen Eingabestream zu erstellen, bei dem das Token T niemals erkannt wird, wenn das N groß genug ist, so dass der Stream verschiedene M Token zwischen den T's enthält.

Dies ist unabhängig von den Details des Top-N-Algorithmus. Es kommt nur auf die Grenze M an.

Um zu sehen, warum dies der Fall ist, betrachten Sie den eingehenden Stream, 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ültige Token sind, die nicht gleich T sind.

Beachten Sie, dass in diesem Stream das T für jedes ai und bi zweimal erscheint. Es scheint jedoch selten genug zu sein, um aus dem System gespült zu werden.

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

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

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