Große Datei einlesen und Wörterbuch erstellen

Wenn du das Ding willst, das du im Kommentar gesagt hast, dann kannst du es leicht in Pandas machen: Nehmen wir an, Sie haben eine Datei mit demselben Layout, aber die Einträge werden dupliziert, da Sie in Ihrem Beispiel alle Duplikate zu einer Liste hinzufügen:

Dann können Sie die Daten lesen und bearbeiten:

Pandas speichert alles in DataFrames und Series-Objekten, die indiziert sind, also kümmern Sie sich nicht viel um die Ausgabe, die erste Spalte ist der Index und die zweite Spalte ist die wichtige und gibt Ihnen die Zahlen, die Sie brauchen / p>

Sie können jedoch viel mehr mit Pandas machen ... Zum Beispiel können Sie nach der ersten Spalte in Ihrer Datei gruppieren und Aggregationen durchführen:

Ich weiß, dass dies nicht die Antwort darauf ist, wie man das Dictionary-Ding beschleunigt, aber nach dem, was Sie im Kommentar erwähnt haben, könnte dies eine alternative Lösung sein.

Bearbeiten - Zeit hinzugefügt

Verglichen mit der schnellsten Wörterbuchlösung und dem Laden von Daten in Pandas DataFrame:

test_dict.py

test_pandas.py

Zeitlich auf einem Linux-Rechner:

Bearbeiten: für die neue Beispieldatei

Hier sind ein paar schnelle Leistungsverbesserungen, die ich bekommen habe:

Wenn Sie eine einfache dict anstelle von defaultdict verwenden und d[parts[0]].append(parts[1]) in d[parts[0]] = d.get(parts[0], []) + [parts[1]] ändern, verringern Sie die Zeit um 10%. Ich weiß nicht, ob es alle Aufrufe an eine Python __missing__ -Funktion beseitigt, nicht die Listen an Ort und Stelle mutiert oder etwas anderes, das den Kredit verdient.

Wenn Sie setdefault in einem einfachen dict anstelle von defaultdict verwenden, wird die Zeit um 8% verkürzt. Dies bedeutet, dass es sich um das Extra-Diktat und nicht um das In-Place-Anhängen handelt.

Inzwischen ersetzt das Ersetzen von split() durch split(None, 1) um 9%.

Das Ausführen von PyPy 1.9.0 anstelle von CPython 2.7.2 verkürzt die Zeit um 52%; PyPy 2.0b um 55%.

Wenn Sie PyPy nicht verwenden können, verkürzt CPython 3.3.0 die Zeit um 9%.

Das Ausführen im 32-Bit-Modus anstelle von 64-Bit hat die Zeit um 170% erhöht, was bedeutet, dass Sie bei Verwendung von 32-Bit möglicherweise wechseln möchten.

Die Tatsache, dass das Diktat mehr als 2 GB Speicherplatz benötigt (etwas weniger in 32-Bit), ist wahrscheinlich ein großer Teil des Problems. Die einzige wirkliche Alternative ist, alles auf der Festplatte zu speichern. (In einer echten App möchten Sie wahrscheinlich einen In-Memory-Cache verwalten, aber hier erzeugen Sie nur die Daten und das Beenden, was die Dinge vereinfacht.) Ob dies hilft, hängt von einer Reihe von Faktoren ab. Ich vermute, dass auf einem System mit einer SSD und nicht viel RAM, es die Dinge beschleunigen wird, während auf einem System mit einer 5400rpm Festplatte und 16 GB RAM (wie der Laptop, den ich im Moment verwende) es nicht ... Aber abhängig vom Festplatten-Cache Ihres Systems usw., wer weiß, ohne zu testen.

Es gibt keine schnelle und unreine Möglichkeit, Listen von Strings in disk-basiertem Speicher zu speichern ( shelve wird vermutlich mehr Zeit mit dem Ein- und Auspacken als das Speichern verschwenden), aber es stattdessen so ändern, dass nur Zeichenfolgen verkettet werden und% co_de verwendet wird % hat die Speicherauslastung unter 200 MB gehalten und ungefähr zur gleichen Zeit beendet. Sie hat den schönen Nebeneffekt, dass Sie die Daten mehr als einmal gespeichert haben, wenn Sie sie dauerhaft speichern möchten. Leider funktioniert das einfache alte gdbm nicht, da die Standardseitengröße für diese vielen Einträge zu klein ist und die Python-Schnittstelle keine Möglichkeit bietet, den Standard zu überschreiben.

Der Wechsel zu einer einfachen sqlite3-Datenbank, die nicht eindeutige Key- und Value-Spalten hat und sie in dbm ausführt, dauerte etwa 80% länger, während sie auf der Festplatte 85% länger dauerte. Ich vermute, dass das Denormalisieren von Dingen, um mehrere Werte mit jedem Schlüssel zu speichern, nicht helfen würde und die Dinge sogar verschlimmern würde. (Für viele Anwendungen im wirklichen Leben kann dies jedoch eine bessere Lösung sein.)

Wickeln Sie dabei :memory: um Ihre Hauptschleife:

Also, das ist ein Drittel Ihrer Zeit in cProfile , 10% in string.split , und der Rest gibt Code aus, den append nicht sehen konnte, was sowohl die Datei als auch die% iteriert. co_de% Methodenaufrufe.

Der Wechsel zu einem normalen cProfile mit defaultdict (was, denke ich, war etwas schneller) zeigt 3.774 Sekunden in dict , also etwa 15% der Zeit, oder vermutlich etwa 20% für setdefault version. Vorher wird die setdefault -Methode nicht schlechter sein als die defaultdict oder __setitem__ .

Allerdings sehen wir hier möglicherweise nicht die Zeit, die malloc-Anrufe verlangen, und sie können ein großer Teil der Leistung sein. Um dies zu testen, benötigen Sie einen C-Level-Profiler. Lasst uns darauf zurückkommen.

In der Zwischenzeit wird zumindest ein Teil der verbleibenden Zeit wahrscheinlich auch von der Linienaufteilung belegt, da diese in der gleichen Größenordnung wie die Raumaufteilung kosten muss, nicht wahr? Aber ich weiß nicht, wie ich das deutlich verbessern könnte.

Schließlich wird ein C-Level-Profiler hier helfen, aber ein Lauf auf meinem System hilft möglicherweise nicht viel für Ihr System, also überlasse ich es Ihnen.

Die schnellste Version auf meinem System hängt davon ab, welches Python ich ausführe, aber es ist entweder folgendes:

Oder das:

... Und sie sind beide ziemlich nah beieinander.

Die gdbm-Lösung, die ungefähr die gleiche Geschwindigkeit hatte und offensichtliche Vor- und Nachteile hat, sieht so aus:

(Wenn Sie dies wiederholt ausführen möchten, müssen Sie natürlich eine Zeile hinzufügen, um eine vorhandene Datenbank zu löschen - oder besser, wenn es zu Ihrem Anwendungsfall passt), um den Zeitstempel mit der Eingabedatei zu vergleichen und überspringen Sie die ganze Schleife, wenn sie bereits auf dem neuesten Stand ist.)

Hier ist eine schnelle C-Version für jeden, der daran interessiert ist. Headline-Zeiten auf meiner Maschine:

Python (& gt; 5 GB Speicher)

C (~ 1,9 GB Speicher)

Also ungefähr 7,8x schneller in C.:)

Und ich sollte hinzufügen, dass meine Version von seq keine brauchbare Liste erstellen würde, ohne den Befehl in:

Code unten, Kredit muss an Vijay Mathew gehen, der das Diktat aus Abschnitt 6.6 der Programmiersprache C in sein Beispiel kopiert hat (und ich kopierte in meine Antwort unten): Schnelle Möglichkeit, das Wörterbuch in C zu implementieren

====== Bearbeiten ====== (13/08/2013)

Nach Kommentar 2 zu meiner Antwort habe ich den Code auf den in Code Listing 2 aktualisiert, um mehrere Werte für einen einzelnen Schlüssel zuzulassen, und ich habe auch begonnen, den aktualisierten Perl-Code zu verwenden, um die Testdatei zu generieren die Größe also die ungefähr halbe Ausführungszeit).

Überschriften sind:

Python (& gt; 5 GB Speicher)

C (~ 1,9 GB Speicher)

Also etwa 7,4x schneller in C, obwohl Panda wahrscheinlich in der Nähe ist.

Allerdings ist der Punkt über die Größe wichtig. Ich könnte "schummeln", indem ich die Hash-Größe auf eine sehr kleine Zahl herabsetze, die bei einem mehrwertigen Wörterbuch die Einfügegeschwindigkeit auf Kosten der Suche erhöhen würde. Um wirklich eine dieser Implementierungen zu testen, müssen Sie die Suchgeschwindigkeit wirklich testen.

Code 2 (mehrwertiges Wörterbuch)

Code 1 (Einzelwertwörterbuch)

Sie können weiterhin eine zusätzliche Optimierung über die anderen hinzufügen:

Da Ihre Schlüssel Zeichenfolgen von "fast" aufeinanderfolgenden Ganzzahlen sind, können Sie die Erstellung des Diktats beschleunigen, indem Sie die Elemente in der Reihenfolge in das Diktat einfügen. Es reduziert die Kollisionen. Siehe Kommentare zur Implementierung von python dict

  

Wichtige Feinheiten voraus: Die meisten Hash-Schemata hängen davon ab, ein "gut" zu haben   Hash-Funktion, im Sinne der Simulation von Zufälligkeit. Python nicht:   seine wichtigsten Hash-Funktionen (für Strings und Ints) sind sehr   regelmäßig in häufigen Fällen:

     

    

      

        

map (Hash, (0, 1, 2, 3)) [0, 1, 2, 3]         Karte (Hash, ("namea", "nameb", "namec", "benannt")) [-1658398457, -1658398460, -1658398459, -1658398462]

      

    

  

     

Das ist nicht unbedingt schlecht! Im Gegenteil, in einer Tabelle der Größe 2 ** i,   Nehmen Sie die I-Bits niedriger Ordnung als den anfänglichen Tabellenindex ist extrem   schnell, und es gibt überhaupt keine Kollisionen für dicts, die durch a indiziert sind   zusammenhängender Bereich von Ints. Das gleiche gilt ungefähr, wenn Schlüssel vorhanden sind   "aufeinanderfolgende" Zeichenfolgen Dies ergibt ein besseres als zufälliges Verhalten in   häufige Fälle, und das ist sehr wünschenswert.

Wenn Sie also die Datei vorverarbeiten können, um sie zu sortieren, kann die Python-Ausführung viel schneller sein.