[python-users] Geschachtelte Listen

[Dirk Hünniger]

Hi Mark,

habe mir dein Beispiel angeschaut und soweit verstanden. Es ist deutlich 
wartbarer als meine Lösung. In meiner Lösung hatte ich alles in einen 
vector gepackt und bin in diesem durch die Gegend gesprungen. Ich hätte 
da die Hoffnung, dass die Speicherfragmentierungseffekte dort kleiner 
sind. Dafür ist mein Code aber völlig unwartbar. Dafür denke ich kann 
man den vector mit einem fwrite auf die Platte befördern was mir gut 
auskäme. Ein weiterer Nachteil meiner Implementierung ist, dass man 
immer nur in das TopUmgebungsElement des UmgebungsStacks neue Elemente 
einfügen kann, was in meinem Falle aber reichen würde. Ich werde mir in 
den nächsten Tagen noch deine Hinweise zur Speicherverwaltung unter Unix 
näher anschauen und dabei sicherlich noch interessante Dinge erfahren.

Viele Grüße Dirk

On 6/25/19 10:55 PM, Dr. Mark Asbach wrote:
> 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
>