Frage

(Dies ist ab sofort ziemlich hypothetisch, daher habe ich nicht zu viele Details zu bieten.)

Ich habe eine flache Datei mit zufälligen (englischen) Wörtern, eine in jeder Zeile. Ich muss ein effizientes Programm schreiben, um die Anzahl der Vorkommen jedes Wortes zu zählen. Die Datei ist groß (vielleicht ca. 1 GB), aber ich habe viel RAM für alles. Sie werden in dauerhaften Medien gespeichert, also sind die Lesegeschwindigkeiten langsam, also muss ich es einfach einmal linear durchlesen.

Meine beiden Ideen für meine Kopf-Kopf-Ideen waren, einen Hash mit Wörtern zu verwenden => nein. von Ereignissen oder ein Trie mit der Nr. Vorkommen am Endknoten. Ich habe genug RAM für ein Hash -Array, aber ich denke, dass ein Trie so schnell oder schneller nachgedacht hätte.

Welcher Ansatz wäre am besten?

War es hilfreich?

Lösung

Ich denke ein Trie mit der Anzahl der Blätter könnte sei schneller.

Jede anständige Hash-Tabellen-Implementierung erfordert das vollständige Lesen des Wortes, verarbeitet es mithilfe einer Hash-Funktion und schließlich eine Nachschlage in der Tabelle.

Ein Trie kann so implementiert werden, dass die Suche beim Lesen des Wortes auftritt. Auf diese Weise können Sie oft die Charaktere überspringen, wenn Sie das einzigartige Wortpräfix festgelegt haben, anstatt das Wort auszudenken.

Wenn Sie beispielsweise die Charaktere gelesen haben: "Torto", würde ein Trie wissen, dass das einzige mögliche Wort, das auf diese Weise beginnt, Schildkröte ist.

Wenn Sie diese Inline -Suche schneller auf einem Wort schneller ausführen können als der Hashing -Algorithmus, sollten Sie schneller sein.

Jedoch, Dies ist total Overkill. Ich streifte weiter, da Sie gesagt haben, es sei rein hypothetisch, ich dachte, Sie möchten einen hypothetischen Typ der Antwort. Gehen Sie mit der am stärksten pflegenden Lösung, die die Aufgabe in angemessener Zeit ausführt. Mikrooptimierungen verschwenden in der Regel mehr Zeit in Mannstunden als in CPU-Stunden.

Andere Tipps

Ich würde ein Wörterbuchobjekt verwenden, bei dem der Schlüssel zum niedrigeren Fall mit dem Wort konvertiert ist und der Wert die Anzahl ist. Wenn das Wörterbuch das Wort nicht enthält, fügen Sie es mit einem Wert von 1 hinzu. Wenn es das Wort enthält, erhöhen Sie den Wert.

Angesichts einer langsamen Lektüre wird es wahrscheinlich keinen spürbaren Unterschied machen. Die Gesamtzeit wird bis zur Zeit vollständig dominiert werden lesen Die Daten trotzdem, also sollten Sie bei der Optimierung arbeiten. Verwenden Sie für den Algorithmus (hauptsächlich Datenstruktur) im Speicher einfach alles, was in der Sprache am bequemsten ist, die Sie am bequemsten finden.

Eine Hash -Tabelle ist (falls richtig gemacht, und Sie sagten, Sie hätten viel Ram) o (1), um ein bestimmtes Wort zu zählen, während ein Trie o (n) sein wird, wo n die Länge des Wortes ist.

Mit einem ausreichend großen Hash -Raum erhalten Sie viel bessere Leistung an einem Hash -Tisch als aus einem Trie.

Ich denke, ein Trie ist übertrieben für Ihren Anwendungsfall. Ein Hash of Word => # von Ereignissen ist genau das, was ich verwenden würde. Selbst wenn Sie eine langsam interpretierte Sprache wie Perl verwenden, können Sie in nur wenigen Minuten eine 1 -GB -Datei auf diese Weise treffen. (Ich habe das schon einmal gemacht.)

Ich habe genug RAM für ein Hash -Array, aber ich denke, dass ein Trie so schnell oder schneller nachgedacht hätte.

Wie oft wird dieser Code ausgeführt? Wenn Sie es nur einmal tun, würde ich sagen, dass sie für Ihre Zeit und nicht für die Zeit Ihrer CPU optimieren und einfach das schnellste tun, um zu implementieren (innerhalb von Grund). Wenn Sie eine Standardbibliotheksfunktion haben, die eine Schlüsselwertschnittstelle implementiert, verwenden Sie diese einfach.

Wenn Sie es oft tun, holen Sie sich eine Teilmenge (oder mehrere Teilmengen) der Datendatei und beachten Sie Ihre Optionen. Ohne mehr über Ihren Datensatz zu wissen, wäre es zweifelhaft, einen über einen anderen zu empfehlen.

Verwenden Sie Python!

Fügen Sie diese Elemente zu einem festgelegten Datentyp hinzu, während Sie Zeile nach Zeile gehen, bevor Sie sich in der Hash -Tabelle befinden. Nachdem Sie gewusst haben, dass es sich im Set befindet, fügen Sie einen Wörterbuchwert von 2 hinzu, da Sie ihn bereits einmal dem Satz hinzugefügt haben.

Dadurch wird ein Teil des Speichers und der Berechnung davon abgehalten, das Wörterbuch jedes Mal zu fragen und stattdessen besser bewertete Wörter mit einzigartigen geschätzten Wörtern zu behandeln, am Ende des Anruf Wert von 1. (schneiden Sie die beiden Sammlungen in Bezug auf den Satz)

In hohem Maße hängt es davon ab, was Sie mit den Daten tun möchten, sobald Sie sie erfasst haben. Sehen Warum einen Hash -Tisch über einem Trie (Präfixbaum) verwenden?

Ein einfaches Python -Skript:

import collections
f = file('words.txt')
counts = collections.defaultdict(int)
for line in f:
    counts[line.strip()] +=1

print "\n".join("%s: %d" % (word, count) for (word, count) in counts.iteritems())
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top