[python-users] Geschachtelte Listen

[Dr. Mark Asbach]

Hallo Dirk,

> ich brauche aber auch den Fall:
> 
> [1,2,[3,4,5,6],7,[8,9,10,11],12]
> 
> sprich die sublisten müssen an beliebiger Stelle und in beliebiger Zahl sowie beliebiger Verschachtelung auftreten können. Das war an meinem Beispiel in der Tat ungeschickt formuliert. Vielleicht hat ja  noch jemand eine Idee wie man diesen allgemeineren Fall effizient lösen kann.

Leider ist Dein Problem in der Praxis deswegen kaum optimal zu lösen, weil Du alternierend neue Elemente im Speicher ablegen und dann alte Elemente in der Größe ändern musst. Das ist grundsätzlich problematisch, weil es Löcher im Heap erzeugt oder belässt (je nach Strategie).

Konkretes Beispiel:

1) Du beginnst mit dem ersten „Rose“-Element. Da Du die Menge der insgesamt abzuspeichernden Kinder-Knoten und die Länger der Buchstabenfolgen nicht kennst, musst Du eine Annahme treffen und zumindest vorläufig einen Speicherbereich reservieren. Der Heap-Pointer verschiebt sich auf die freie Speicherstelle hinter diesem Speicherbereich.
2) Sobald der erste Kind-Knoten vom Typ „Rose“ kommt, musst Du für diesen Knoten einen Speicherbereich reservieren. Der Heap-Pointer verschiebt sich auf die freie Speicherstelle hinter diesem Speicherbereich.
3) Nun willst Du weitere Buchstabenfolgen zum ursprünglichen Knoten aus (1) hinzufügen. Wenn Du einen zu kleinen Speicherbereich reserviert hattest, wird jetzt ein neuer reserviert und der Inhalt umkopiert. Der alte Bereich bleibt „für immer verbraucht“.

Du musst Dir am Ende Deine Speicherstruktur selbst bauen, damit das funktioniert, ohne beim Parsen riesig Speicher zu fressen. Das ist schon eher aufwändig.

Einfach weil’s Spaß macht und ich viel zu selten zu C++ komme, habe ich das mal in einer hacky Minimalvariante auf Basis von meinem ursprünglichen Vorschlag gemacht. Die modifizierte Lösung braucht knapp 1.4% mehr Speicher beim Nutzungsmuster wie in Deinem ursprünglichen Beispiel, kann aber auch die geforderte Struktur mit beliebig vielen Kind-Knoten an beliebiger Position abbilden. Nachteil: Daten Anhängen ist langsam (außer im Fall Deines ursprünglichen Beispiels), weil ich jetzt eine horizontal verkettete Liste daraus gemacht habe. Kann man aber schneller machen, indem man sich beim Parsen jeweils den aktuellen next-Knoten merkt - dazu hätte ich das Hauptprogramm aber umbauen müssen.

In der Praxis musst Du darauf achten, dass beim Parsen auf keinen Fall Objekte auf dem Heap angelegt werden (außer der Ziel-Datenstruktur natürlich), sonst ist der ganze Spaß dahin.

> /usr/bin/time -l ./test_3
>         1.86 real         1.84 user         0.01 sys
>   43835392  maximum resident set size


In Python geht das ziemlich genau so auch mit einem array oder String. Das Beispiel 2 hast Du ja.

Wenn Du’s nicht hacky machen willst, kannst Du Dir unter C++ vielleicht die Boost Graph Library anschauen: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/table_of_contents.html . Ich persönlich mag aber Boost gar nicht und habe den Eindruck, dass das oft mit Kanonen auf Spatzen geschossen ist. Es ist nicht viel Code nötig, um aus dem hacky Beispiel ein sauberes zu machen und unter Python ist diese Sorte Baum ähnlich kompakt mit Bordmitteln zu erstellen. Das Verständnis von Speicherallokationsreihenfolge in einem Unix-System wird Dir aber leider nicht erspart, wenn Du das richtig lösen willst, egal mit welcher Programmiersprache.

Grüße,
Mark

-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : test_3.cxx
Dateityp    : application/octet-stream
Dateigröße  : 1634 bytes
Beschreibung: nicht verfügbar
URL         : <http://lists.uni-koeln.de/pipermail/python-users/attachments/20190625/b4d31a34/attachment-0001.obj>
-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : smime.p7s
Dateityp    : application/pkcs7-signature
Dateigröße  : 4693 bytes
Beschreibung: nicht verfügbar
URL         : <http://lists.uni-koeln.de/pipermail/python-users/attachments/20190625/b4d31a34/attachment-0001.p7s>