Schleife mit Abfrage beschleunigen

[Dami123]

Such eine Möglichkeit meinen Code zu beschleunigen, er läuft relativ langsam.

Code: Alles auswählen

users = []
with open('result.txt', 'r') as results:
    for i in results.readlines():
        userid = json.loads(i.split('\n').pop(0))['Userid']
        users.append(userid)
print('collected')

remaining = []
num = 1000000
for i in xrange(300000, 6150000):
    if i > num:
        print(i)
        num = num + 1000000
    
    if str(i) not in users:
        remaining.append(str(i))


with open('remain.txt', 'w') as remain:
    for i in remaining:
        remain.write('{}\n'.format(i))

Code ist quick and dirty.
'users' enthält ca. 4 Millionen Einträge. Das auslesen der userids ist alles schnell genug. Der Teil, der überprüft ob die jeweilige Userid vorhanden ist, muss beschleunigt werden, da diesen sehr langsam läuft.

Jemand einen Vorschlag?

[Hyperion]

Auch wenn ich den Sinn hinter dem Code nicht sehe, ist Zeile 15 natürlich das Problem! Eine Suche in einer Liste ist erst einmal linear (O(n)). D.h. Du musst sie im schlimmsten Falle komplett durchlaufen, bevor Du weisst, dass das gesuchte Element nicht darin enthalten ist. Ergo ist diese Datenstruktur für solche Lookup-Prozesse suboptimal. Eine "ID" legt ja nahe, dass das etwas eindeutiges ist. Also könntest Du ein Set oder ein Dictionary nutzen. Damit geht der Lookup in konstanter Zeit von statten (O(1)). Das sollte das ganze massiv beschleunigen.

[BlackJack]

@Dami123: Ernsthaft: ``i.split('\n').pop(0)``!? Erkläre mal bitte wie `i` aussieht und was der Code bewirken soll.

`num` wird nirgends verwendet.

Statt die User-IDs erst alle in eine Liste einzulesen um dann jede ID zwischen 300000 (inklusive) und 6150000 (exclusive) einzeln zu testen ob die irgendwo in der Liste mit den 4 Mio. IDs vorkommt, könntest Du doch beim einlesen schon testen ob die ID in dem entsprechenden bereich liegt. Und zwar *ohne* jede ID einzeln zu testen. ``<`` und ``>`` existiert.

Das ist nicht nur schneller, sondern kommt auch noch mit weniger Speicher aus, weil maximal ein Datensatz zur gleichen Zeit im Speicher sein muss und nicht alle 4 Millionen. Da ist das `readlines()` übrigens auch unsinnig. Warum liest Du an der Stelle alle Zeilen komplett in den Speicher statt eine Schleife über `results` zu machen die jeweils nur eine Zeile liest die dann verarbeitet wird!?

[Dami123]

@Hyperion
Genau. Danke, hab die Überprüfung der ganzen Liste unterbunden.

@BlackJack
`i.split('\n').pop(0)` entfernt die neue Zeile am ende vom jeden Eintrag und gibt das erste Element der gespliteten Liste zurück. Wie gesagt schnell niedergeschrieben. Hab auch nicht getestet ob json.loads beim einlesen die neue Zeile ignoriert.

Hab ein paar Sachen ausprobiert und erstmal eine Liste zu erzeugen mit allen Einträgen und anschließen beim einließen der results die vorhandenen Stellen zu entfernen mittels 'remove()' oder 'del' ist auch sehr langsam, da auch hier linear vorgegangen wird.
Hab eure Vorschläge berücksichtigt und das hier zusammengestellt. Brauche es nur 1-2x wird also nicht optimiert und verschönert. Läuft nun wesentlich schneller als jeder Vorgang mit Listen.

Code: Alles auswählen

remaining = []
users = {}
with open('result.txt', 'r') as results:
    for i in results:
        userid = json.loads(i)['Userid']
        users[userid] = ''
        
for i in xrange(300000, 6150000):
    try:
        users[str(i)]
    except:
        remaining.append(i)

Der Sinn dahinter ist übrigens die Überprüfung der fehlenden Felder im Bereich. Wieder ein großen Dank für eure Hilfe.

edit:
Tolle Sache! Das Script ist in 3min durchgelaufen, nachdem ich das vorherige min. 1h laufen lassen hatte und dabei nicht einmal eine Million erreicht worden ist.

[EyDu]

Du soltest dir wirklich noch einmal die Beitrag von BlackJack ansehen. Da könntest du noch etwas lernen Egal ob du es bei deinem Programm noch korrigierst oder nicht.

[BlackJack]

@Dami123: Welche neue Zeile? `readlines()` liest Zeilen ein, jedes `i` ist nur eine Zeile, die in mehrere Zeilen zu splitten macht keinen Sinn. `i` ist übrigens ein sehr schlechter Name für alles was keine ganze Zahl ist, insbesondere wenn es sich auch noch um die Laufvariable der Schleife handelt.

Ein Wörterbuch bei dem einen nur die Schlüssel, aber nie die Werte dazu interessieren ist übrigens ein `set()`. Da gibt es extra einen Datentyp für.

[Sirius3]

Das ganze dann in 3 Zeilen:

Code: Alles auswählen

with open('result.txt', 'r') as results:
    users = set(json.loads(line)['Userid'] for line in results)

remaining = [i for i in xrange(300000, 6150000) if str(i) not in users]

[Dami123]

@BlackJack
Das mit dem 'set' schau ich mir an sieht nützlich aus. Wie gesagt das Script wird nicht nach dem PEP-8 angepasst und 'i' ist eine schlechte Bezeichnung dafür.
Wenn ich eine Textdatei mit Zeilen hab und diese einlese ob mit 'readlines' oder nicht, bleibt am ende vom String das Kürzel '\n' hängen. Da ich damit gelegentlich Fehler erzeuge, hab ich es intuitiv direkt beim einlesen entfernt.

@Sirius3
Ein Beispiel mit 'set' vielen Dank dafür. Läuft auch sehr schnell, werde ich in Zukunft mehr Gebrauch von machen.