2009-08-20 16 views
3

Ein einfaches Problem, wirklich: Sie haben eine Milliarde (1e + 9) vorzeichenlose 32-Bit-Integer als dezimale ASCII-Strings in einer TSV (Tab-getrennte Werte) -Datei gespeichert. Die Konvertierung mit int() ist schrecklich langsam im Vergleich zu anderen Tools, die an demselben Datensatz arbeiten. Warum? Und noch wichtiger: Wie kann ich es schneller machen?Schnelle Umwandlung von String in Integer in Python

Daher die Frage: Was ist der schnellste Weg, um eine Zeichenfolge in eine Ganzzahl in Python zu konvertieren?

Worüber ich wirklich nachdenke, ist eine halb verborgene Python-Funktionalität, die (ab) für diesen Zweck verwendet werden könnte, nicht anders als Guidos Verwendung von array.array in seinem "Optimization Anecdote".

Probendaten (mit Tabs zu Räumen erweitert)

38262904  "pfv"    2002-11-15T00:37:20+00:00 
12311231  "tnealzref"  2008-01-21T20:46:51+00:00 
26783384  "hayb"    2004-02-14T20:43:45+00:00 
812874   "qevzasdfvnp"  2005-01-11T00:29:46+00:00 
22312733  "bdumtddyasb"  2009-01-17T20:41:04+00:00 

Die Zeit, die die Daten zu lesen braucht hier nicht relevant ist, wird die Datenverarbeitung der Engpass.

Microbenchmarks

alle der folgenden Sprachen interpretiert. Auf dem Hostcomputer wird 64-Bit-Linux ausgeführt.

Python 2.6.2 mit IPython 0.9.1, ~ 214K Umwandlungen pro Sekunde (100%):

In [1]: strings = map(str, range(int(1e7))) 

In [2]: %timeit map(int, strings); 
10 loops, best of 3: 4.68 s per loop 

REBOL 3.0 Version 2.100.76.4.2, ~ 231kcps (108%):

>> strings: array n: to-integer 1e7 repeat i n [poke strings i mold (i - 1)] 
== "9999999" 

>> delta-time [map str strings [to integer! str]] 
== 0:00:04.328675 

REBOL 2.7.6.4.2 (15-Mar-2008), ~ 523kcps (261%):

Als John in den Kommentaren erwähnt, diese Version hat keine Liste der konvertierten Zahlen bauen, so die Geschwindigkeit- Verhältnis gegeben ist relativ zu Pythons 4.99s Laufzeit von for str in strings: int(str).

>> delta-time: func [c /local t] [t: now/time/precise do c now/time/precise - t] 

>> strings: array n: to-integer 1e7 repeat i n [poke strings i mold (i - 1)] 
== "9999999" 

>> delta-time [foreach str strings [to integer! str]] 
== 0:00:01.913193 

KDB + 2.6T 2009.04.15, ~ 2016kcps (944%):

q)strings:string til "i"$1e7 

q)\t "I"$strings 
496 
+4

Versuchen Sie 'numpy.fromfile', um 'eine Milliarde positive ganze Zahlen' zu laden (was meinen Sie mit 'Milliarden' (es ist '10 ** 9 'in den USA, es könnte' 10 ** 12 'sein) Großbritannien)? – jfs

+0

Guter Fang über die Milliarde, auch wenn letzteres in den 1970er Jahren in Großbritannien aus der Mode kam. – earl

+1

Haben Sie versucht, den Code zu kompilieren? –

Antwort

3

Die folgende meisten verein C-Erweiterung verbessert die bereits stark auf die builtin, mehr als dreimal so viele Strings pro Sekunde konvertieren Verwaltung (650kcps vs 214kcps):

static PyObject *fastint_int(PyObject *self, PyObject *args) { 
    char *s; unsigned r = 0; 
    if (!PyArg_ParseTuple(args, "s", &s)) return NULL; 
    for (r = 0; *s; r = r * 10 + *s++ - '0'); 
    return Py_BuildValue("i", r); 
} 

offensichtlich nicht für ganze Zahlen von willkürlicher dies tut gerecht Länge und verschiedene andere Sonderfälle, aber das ist in unserem Szenario kein Problem.

+1

Gibt es einen Grund, die Funktionen von C standard lib nicht zu verwenden, z. B. 'strtoul()'? – jfs

4

Ich könnte darauf hindeuten, dass für rohe Geschwindigkeit, Python nicht das richtige Werkzeug für diese Aufgabe ist. Eine handcodierte C-Implementierung wird Python einfach schlagen.

+2

stimme ich völlig zu, aber das ist nicht wirklich der Punkt meiner Frage. Ich fügte einen Absatz hinzu, wonach ich suche. Eine benutzerdefinierte Python-Erweiterung wäre jedoch eine Option. – earl

1

Stimmen Sie mit Greg überein; Python ist als interpretierte Sprache im Allgemeinen langsam. Sie könnten versuchen, den Quellcode on-the-fly mit dem Psyco library kompilieren oder die App in einer niedrigeren Sprache wie C/C++ zu kodieren.

+1

-1 auf der interpretierten ==> langsamen Folge. Eine C-Implementierung wird in diesem Fall schneller sein, aber Ihre Verallgemeinerung ist einfach falsch. –

+0

Eine interpretierte Sprache muss zum Zeitpunkt der Ausführung in Maschinencode übersetzt werden, und das ist einfach langsamer als die Ausführung eines kompilierten Objektcodes. Versteh immer noch nicht deinen Downvote.Bitte erklären Sie, warum denken Sie, dass "meine Verallgemeinerung" falsch ist. – ramosg

+0

Interpretierte Sprachen können während der Laufzeit Optimierungen am Bytecode vornehmen, was manchmal zu einer besseren Leistung führt als der native Maschinencode. Schaut es euch an, es wurde zu Tode diskutiert. –

0

Es ist möglicherweise keine Option für Sie, aber ich würde wirklich hart auf die Verwendung einer Binärdatei statt Text. Ändert es sich oft? Wenn nicht, könnten Sie es vorverarbeiten.

3

Sie erhalten einen Prozentsatz der Geschwindigkeit, indem Sie sicherstellen, dass nur "lokale" Variablen in Ihren engsten Schleifen verwendet werden. Die int Funktion ist eine globale, so dass es teurer wird als ein lokaler.

Benötigen Sie wirklich alle Milliardenzahlen im Speicher zu jeder Zeit? Erwägen Sie, einige Iteratoren zu verwenden, um nur wenige Werte gleichzeitig zu erhalten. Eine Milliarde Zahlen benötigen ein wenig Speicherplatz. Wenn Sie diese nacheinander in eine Liste einfügen, müssen Sie mehrere große Neuzuweisungen vornehmen.

Erhalten Sie Ihre Schleife von Python vollständig wenn möglich. Die Kartenfunktion hier kann dein Freund sein. Ich bin mir nicht sicher, wie Ihre Daten gespeichert sind. Wenn es sich um eine einzelne Zahl pro Zeile ist, könnten Sie den Code

values = map(int, open("numberfile.txt")) 

reduzieren Wenn mehrere Werte pro Zeile sind, die Leerraum getrennt sind, graben sich in den itertools aus Python den Looping-Code zu halten. Diese Version hat den zusätzlichen Vorteil, dass Sie einen Zahleniterator erstellen, so dass Sie nur eine oder mehrere Zahlen gleichzeitig aus der Datei ausgeben können, anstatt eine Milliarde auf einmal.

numfile = open("numberfile.txt") 
valIter = itertools.imap(int, itertools.chain(itertools.imap(str.split, numfile))) 
1

Wie andere gesagt haben, könnten Sie Ihr eigenes C-Modul codieren, um die Analyse/Konvertierung für Sie durchzuführen. Dann könntest du das einfach importieren und aufrufen. Sie können möglicherweise Pyrex oder sein Cython-Derivat verwenden, um Ihr C aus Ihrem Python zu generieren (indem Sie dem Python ein paar einschränkende Hinweise hinzufügen).

Sie können mehr über Cython lesen und sehen, ob das hilft.

Eine andere Frage, die Ihnen in den Sinn kommt ... was werden Sie mit diesen Milliarden ganzen Zahlen machen? Ist es möglich, dass Sie sie als Zeichenfolgen laden, nach ihnen als Zeichenfolgen suchen und bei Bedarf eine faule Konvertierung durchführen? Oder könnten Sie die Konvertierung und die anderen Berechnungen mit threading oder multiprocessing Modulen und Warteschlangen parallelisieren? (Lassen Sie einen oder mehrere Threads/Prozesse die Konvertierung durchführen und eine Warteschlange einspeisen, von der Ihre Verarbeitungs-Engine sie abruft). Mit anderen Worten, würde ein Hersteller/Verbraucher-Design das Problem lindern?