Finden des Elements, das in einer sehr großen Datei am häufigsten vorkommt

Ich habe diese Interviewfrage oft gestellt bekommen und ich hatte gehofft, einige Meinungen darüber zu bekommen, was gute Antworten sein könnten: Sie haben eine große Datei mit mehr als 10 GB und möchten herausfinden, welches Element am häufigsten vorkommt, was ein guter Weg ist um dies zu tun?

Das Wiederholen und Verfolgen einer Map ist wahrscheinlich keine gute Idee, da Sie viel Speicher verwenden und das Verfolgen von eingehenden Einträgen nicht die beste Option ist, da die Datei in der Regel bereits vorhanden ist, wenn diese Frage gestellt wird.

Andere Überlegungen, die ich angestellt hatte, waren das Aufteilen der Datei, die von mehreren Threads durchlaufen und verarbeitet werden soll, und dann das Kombinieren dieser Ergebnisse, aber das Speicherproblem für die Maps ist immer noch vorhanden.

algorithms arrays Klopfen
quelle

Was sind die Elemente der Datei? Sind sie Saiten? Wenn Sie Zeichen für Elemente verwenden, weist die Karte kein Speicherproblem auf. Wenn Elemente Wörter sind, dann denke ich wieder, dass es kein Problem sein würde. Wenn Sie alle möglichen Teilzeichenfolgen haben, können Sie Probleme haben ...

Nejc

Wenn die Bedingung "ein Element, das mehr als die Hälfte aller Elemente enthält" war, gab es eine lineare Lösung.

st0le

Ich glaube, die Elemente sind normalerweise Saiten. Aber ich verstehe nicht, dass die Karte kein Problem darstellt. Haben Sie im schlimmsten Fall, in dem jedes Element einzigartig ist, Ihren Speicherbedarf nicht verdoppelt?

Pat

Wenn der Boyer-Moore-Mehrheitskandidatenalgorithmus anwendbar ist, wird er in linearer Zeit ausgeführt und ist vorhanden.

Juho

Antworten:

Wenn Sie eine haben wirklich große Datei und viele Elemente darin, aber das häufigste Element ist sehr häufig - tritt Bruchteil der Zeit - Sie können es in linearer Zeit mit Platz finden Worte (die Die Konstante in der Notation ist sehr klein (im Grunde genommen 2, wenn Sie den Speicher für Hilfssachen wie Hashing nicht mitzählen). Darüber hinaus funktioniert dies hervorragend mit externem Speicher, da die Datei elementweise nacheinander verarbeitet wird und der Algorithmus niemals "zurückschaut". Ein Weg, dies zu tun, ist über einen klassischen Algorithmus von Misra und Gries, siehe diese Vorlesungsunterlagen $> 1/k$ $O(k)$ $O()$ . Das Problem ist jetzt als das Problem der schweren Schläger bekannt (die häufigsten Elemente sind die schweren Schläger).

Die Annahme, dass das häufigste Element Bruchteil der Zeit für eine kleine Zahl erscheint, mag stark erscheinen, ist aber in gewisser Weise notwendig! Dh, wenn Sie sequentiellen Zugriff auf Ihre Datei haben (und wenn die Datei sehr umfangreich ist, ist der zufällige Zugriff zu teuer), verwendet jeder Algorithmus, der immer das häufigste Element in einer konstanten Anzahl von Durchläufen findet, linearen Raum in der Anzahl der Elemente . Wenn Sie also nichts von der Eingabe annehmen, können Sie eine Hash-Tabelle nicht schlagen. Die Annahme, dass das häufigste Element sehr häufig ist, ist möglicherweise der natürlichste Weg, um die negativen Ergebnisse zu umgehen. $> 1/k$ $k$

Hier ist eine Skizze für , dh wenn es ein einzelnes Element gibt, das mehr als die Hälfte der Zeit auftritt. Dieser Sonderfall ist als Mehrheitswahlalgorithmus bekannt und geht auf Boyer und Moore zurück. Wir behalten ein einzelnes Element und eine einzelne Zählung bei. Initialisieren Sie den Zähler auf 1 und speichern Sie das erste Element der Datei. Verarbeiten Sie dann die Datei in der folgenden Reihenfolge: $k = 2$

Wenn das aktuelle Element der Datei mit dem gespeicherten Element identisch ist, erhöhen Sie die Anzahl um eins
Wenn sich das aktuelle Element der Datei vom gespeicherten Element unterscheidet, verringern Sie die Anzahl um eins
Wenn der aktualisierte Zähler 0 ist, "schmeiße" das gespeicherte Element aus und speichere das aktuelle Element der Datei; Erhöhen Sie die Anzahl auf 1
Fahren Sie mit dem nächsten Element der Datei fort

Ein bisschen Nachdenken über diese Prozedur wird Sie davon überzeugen, dass, wenn ein "Majoritäts" -Element existiert, dh eines, das mehr als die Hälfte der Zeit auftritt, dieses Element das gespeicherte Element ist, nachdem die gesamte Datei verarbeitet wurde.

Für allgemeines behalten Sie Elemente und Zählwerte bei und initialisieren die Elemente mit den ersten verschiedenen Elementen der Datei und den Zählwerten, bis zu der Häufigkeit, mit der jedes dieser Elemente angezeigt wird, bevor Sie das sehen $k$ $k-1$ $k-1$ $k$ $k$

$k-1$ $1/k$ $O(k)$

$k$ $1/k$ $k-1$

Sasho Nikolov
quelle

Sie können den Boyer-Moore- oder den Misra-Gries-Demaine-Algorithmus nicht verwenden. Das Problem ist wie gesagt anders: Sie suchen nicht nach einem Mehrheitselement, sondern nach einem Element, dessen Vorkommen> = der Vorkommen aller Elemente sind. Hier ist ein einfaches Gegenbeispiel. Sei n die Gesamtzahl der Elemente, so dass n = 2k + 1 ist . Die ersten k Elemente seien 0, die nächsten k Elemente seien 1 und das letzte Element seien 2. Der Boyer-Moore-Algorithmus gibt das letzte Element 2 als potenziellen Mehrheitskandidaten an. In diesem speziellen Fall muss die Ausgabe entweder 0 oder 1 sein.

Massimo Cafaro,

O (1)

$O(1)$

Ω (n)

$\Omega(n)$

Ich habe gerade darauf hingewiesen, dass Sie möglicherweise falsche Ergebnisse erzielen, wenn Sie eine falsche Annahme treffen. Was ist besser, ein kleiner Speicherbedarf und ein möglicherweise falsches Ergebnis oder das richtige Ergebnis, obwohl es Sie mehr Speicher kostet? Wenn ich ein möglicherweise falsches Ergebnis wählen müsste, würde ich eher einen zufälligen Algorithmus wählen als Boyer-Moore, vorausgesetzt, etwas, von dem ich nicht weiß, dass es tatsächlich wahr ist.

Massimo Cafaro

@ MassimoCafaro, das ist kein Kompromiss, den Sie eingehen müssen. Wie ich schon sagte, ein einziger Durchgang über die Datei überprüft leicht, ob die Annahme erfüllt ist!

Sasho Nikolov

@ MassimoCafaro und das ist nur die triviale Lösung! Die Annahme kann mit hoher Wahrscheinlichkeit mit einer CM-Skizze ohne zusätzliche Durchgänge verifiziert werden.

Sasho Nikolov

Die naheliegende Antwort ist natürlich, eine Hash-Karte zu führen und einen Zähler für das Auftreten von Elementen zu speichern, während Sie sich durch die Datei bewegen, wie es Nejc bereits vorgeschlagen hat. Dies ist (in Bezug auf die zeitliche Komplexität) die optimale Lösung.

$\Theta(n\log{n}).$

Jernej
quelle

Könnten Sie den Huffman-Codierungsansatz genauer erläutern? Ich habe bereits einen Huffman-Encoder geschrieben, aber es ist schon eine Weile her, wie genau würden Sie ihn in diesem Fall verwenden?

Pat

@Pat Vergiss den Teil, es war zu früh am Morgen und irgendwie dachte ich, es wäre sinnvoll, die Eingabe zu komprimieren.

Jernej

Wenn das häufigste Element deutlich häufiger als das nächste gemeinsame Element ist und die Anzahl der verschiedenen Elemente im Vergleich zur Dateigröße gering ist, können Sie mehrere Elemente zufällig auswählen und das häufigste Element in Ihrem Beispiel zurückgeben.

adrianN
quelle

Darüber hinaus können Sie eine kleine Anzahl von Elementen, die häufig vorkommen, durch Stichproben finden und dann nur diese Elemente genau zählen.

Max