[python-users] Geschachtelte Listen

Mo Jun 24 14:13:27 CEST 2019

Hi Jochen,

> Glaube mit dem array Modul und einer eigenen Baumstruktur käme man in Python schon recht weit.

Definitiv! Ich hatte mich tatsächlich nur darum bemüht, einer Minimalvariante (in C++ vermutet) auf die Spur zu kommen (41 Mb -> schon ziemlich nah an den potenziell 40 Mb) und das dann testweise auch nach Python übertragen (~60 Mb). Und genau wie Du schreibst kommt man an die C++-Variante nur mit str (wie bei mir umgesetzt), array oder numpy.array auf 150% ran, weil dabei die Listenverkettung wegfällt aber eben leider ein Pointer auf die Methodentabelle notwendig ist. In C++ hatte ich den eliminiert, indem ich Klassen ohne virtuelle Methoden verwendet habe – da kommt man dann wegen statischer Typisierung ans Minimum heran.

Grüße,
Mark

-- 
Dr. Mark Asbach
pixolus GmbH
Große Brinkgasse 2b, 50672 Köln
https://pixolus.de, Tel +49 221 949992-20
Registergericht: Amtsgericht Köln, HRB 80243
Geschäftsführer: Dr. Mark Asbach, Dr. Stefan Krausz

> Am 24.06.2019 um 13:40 schrieb Jochen Wersdörfer <jochen at wersdoerfer.de>:
> 
> 
> 
>> Am 24.06.2019 um 12:52 schrieb Dr. Mark Asbach <mark.asbach at pixolus.de>:
>> 
>> Hallo Dirk,
>> 
>>> vielen Dank für deine Anwort. Die Sache mit den 8 Byte pro Pointer hatte ich schon so befürchtet. Als Lösung würde mir dann noch einfallen den Speicher sehr manuell zu verwalten und bei jedem Rose Element die Länge der Subliste mit anzugeben. Man braucht ein Bit um zwischen Rose und Leaf zu unterscheiden. Sowie 8 Byte für die Nutzdaten je Leaf und 8 Byte für die Länge je Rose. Wenn ich den bei mir auftrenden Spezialfall das die Nutzdaten Unicode Zeichen sind, sowie die Tatsache das immer weniger 1 ExaByte Ram vorhanden sind nutze, komme ich mit 8 Byte pro Rose bzw Leaf aus. Wäre dann halt nur ein sehr schlecht wartbarer prozduraler Ansatz. Daher werde ich wohl einfach weniger Daten in der Speicher laden müssen.
>> 
>> Unicode (4 byte pro Zeichen) oder UTF-8-Folgen?
>> 
>> Es bringt immer etwas, bei solchen Knobel-Fragen auch die Problemstellung zu beschreiben - manchmal liegen sinnvolle Lösungen eher auf der High-Level-Beschreibung eines Problems. Ich vermute aus Deinen Sätzen nun folgendes: Du parsed Text, der Sonderzeichen aus dem Unicode-Alphabet enthalten kann, und möchtest diesen Text zerlegen, so dass sich zwischendurch Substrings im Speicher ergeben. Mit dem Vorschlag von Klaus zusammen könnte man das so angehen, dass Du als Datenhalter eine Klasse definierst, die aus einem String plus einer folgenden Subliste besteht, ggf. auch aus einem Array aus solchen Paaren.
>> 
>> Deine Textbeschreibung aus der ursprünglichen Mail sieht aber eingeschränkter aus. Für Dein eingeschränktes Beispiel gibt es ausreichend speichersparende Möglichkeiten, bei denen ich ohne Aufwand mit Python an 150% des Speicherplatzes einer kompakten C++-Repräsentation rankomme. Ich habe Deine C++-Version noch um einen Aufruf von reserve() ergänzt, damit sie keinen überflüssigen Heap braucht und dann alle vier Varianten (Deine ist jeweils die _1) verglichen. Um den Fußabdruck eines nackten Pythons abzuziehen, habe noch ein „Leeres“ Skript entsprechend gemessen. Außerdem habe ich Dein Python-Beispiel so geändert, dass eine Referenz auf die Root-Liste behalten wird, damit Python nicht alles direkt ab dem „r=l“ verwirft da unreferenziert. Kompiliert mit clang++ auf einem 64bit mac.
>> 
>> /usr/bin/time -l python test_2.py 
>>      49.91 real        49.78 user         0.07 sys
>> 76500992  maximum resident set size
>> 
>> /usr/bin/time -l ./test_1
>>       4.01 real         3.77 user         0.23 sys
>> 983851008  maximum resident set size
>> 
>> /usr/bin/time -l ./test_2
>>       1.63 real         1.61 user         0.00 sys
>> 43212800  maximum resident set size
> 
> 
> Ah cool, time -l kannte ich noch gar nicht. Habe das mal ein bisschen
> umgeschrieben:
> 
> from itertools import islice
> 
> 
> def grouper(iterable, chunk_size):
>    iterator = iter(iterable)
>    while True:
>        chunk = list(reversed(list(islice(iterator, chunk_size))))
>        if not chunk:
>            return
>        yield chunk
> 
> 
> chunk_generator = grouper(reversed(range(40100100)), 1000)
> result = next(chunk_generator)
> for chunk in chunk_generator:
>    chunk.append(result)
>    result = chunk
> 
> ➜  ~ /usr/bin/time -l python rose_list.py
>        2.75 real         2.27 user         0.46 sys
> 1683931136  maximum resident set size
> 
> Also etwa 3 Sekunden und 1.57Gb Speicherverbrauch. Aber völlig umoptimiert.
> 
> Wenn man „yield chunk“ "yield list(c % 256 for c in chunk)“ sagt, braucht das
> Skript 3.8s und 343Mb.
> 
> Glaube mit dem array Modul und einer eigenen Baumstruktur käme man in
> Python schon recht weit.
> 
> Viele Grüße,
> Jochen
> ________________________________________
> 
> Diese Mail erhalten Sie ueber die Mailingliste python-users der Universitaet zu Koeln
> Nachrichten an: python-users at uni-koeln.de
> Abonnement und Benutzereinstellungen: https://lists.uni-koeln.de/mailman/listinfo/python-users
> Listenarchiv: https://lists.uni-koeln.de/pipermail/python-users/
> 
> pyCologne Homepage: http://pycologne.de/

-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : smime.p7s
Dateityp    : application/pkcs7-signature
Dateigröße  : 7763 bytes
Beschreibung: nicht verfügbar
URL         : <http://lists.uni-koeln.de/pipermail/python-users/attachments/20190624/d1e924c2/attachment.p7s>