<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Hi Jochen,</p>
<p>die Zählerei brauchte ich nur für das Beispiel, war
zugegebenermaßen nicht sonderlich geschickt von mir gewählt war.
Mir geht es wie gesagt um einen HTML Parse Tree. Der kann sowohl
Unicode Zeichen als auch Tags enthalten. Jedes Tag kann wiederum
Unicode Zeichen als auch Tags enthalten.</p>
<p>Viele Grüße Dirk<br>
</p>
<div class="moz-cite-prefix">On 6/25/19 9:29 PM, Jochen Tackenberg
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CANVr0YF+YH5k1Ryect77ZPwp_Ege9bBEANaHNrBut9VpZXZf8Q@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="auto">
<div>Hallo Dirk,
<div dir="auto"><br>
</div>
<div dir="auto">was mir noch nicht klar ist, ist warum die
Listen überhaupt gespeichert werden. Laut deiner
Beschreibung ist die Anzahl der Elemente und die Anzahl der
Schachteln von Interesse. Wofür muss die Liste aufgebaut
werden? Kann man nicht die Infos direkt beim Aufbau
mitzählen und dann den Inhalt jeweils direkt verwerfen? Oder
wofür wird die Struktur später noch benutzt?</div>
<div dir="auto"><br>
</div>
Grüße</div>
<div dir="auto">Jochen<br>
<br>
<div class="gmail_quote" dir="auto">
<div dir="ltr" class="gmail_attr">Dirk Hünniger via
python-users <<a
href="mailto:python-users@uni-koeln.de"
moz-do-not-send="true">python-users@uni-koeln.de</a>>
schrieb am Di., 25. Juni 2019, 19:31:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">Diese
Nachricht wurde eingewickelt um DMARC-kompatibel zu sein.
Die<br>
eigentliche Nachricht steht dadurch in einem Anhang.<br>
<br>
This message was wrapped to be DMARC compliant. The actual
message<br>
text is therefore in an attachment.<br>
<br>
<br>
---------- Forwarded message ----------<br>
From: "Dirk Hünniger" <<a
href="mailto:dirk.hunniger@googlemail.com"
target="_blank" rel="noreferrer" moz-do-not-send="true">dirk.hunniger@googlemail.com</a>><br>
To: "Dr. Mark Asbach" <<a
href="mailto:mark.asbach@pixolus.de" target="_blank"
rel="noreferrer" moz-do-not-send="true">mark.asbach@pixolus.de</a>><br>
Cc: pyCologne <<a
href="mailto:python-users@uni-koeln.de" target="_blank"
rel="noreferrer" moz-do-not-send="true">python-users@uni-koeln.de</a>><br>
Bcc: <br>
Date: Tue, 25 Jun 2019 19:31:19 +0200<br>
Subject: Re: [python-users] Geschachtelte Listen<br>
Hallo Mark,<br>
<br>
jetzt komme ich endlich mal dazu mir deine Lösung genauer
anzuschauen. <br>
In der Tat löst sie genau das von mir angegebene Beispiel
maximal <br>
speichereffizient. Mein Beispiel lautete ja:<br>
<br>
<br>
[1,2,3,4,[5,6,7,8,[9,10,11,12]]]<br>
<br>
ich brauche aber auch den Fall:<br>
<br>
[1,2,[3,4,5,6],7,[8,9,10,11],12]<br>
<br>
sprich die sublisten müssen an beliebiger Stelle und in
beliebiger Zahl <br>
sowie beliebiger Verschachtelung auftreten können. Das war
an meinem <br>
Beispiel in der Tat ungeschickt formuliert. Vielleicht hat
ja noch <br>
jemand eine Idee wie man diesen allgemeineren Fall
effizient lösen kann.<br>
<br>
Viele Grüße Dirk<br>
<br>
On 6/24/19 12:52 PM, Dr. Mark Asbach wrote:<br>
> Hallo Dirk,<br>
><br>
>> 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.<br>
> Unicode (4 byte pro Zeichen) oder UTF-8-Folgen?<br>
><br>
> 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.<br>
><br>
> 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.<br>
><br>
> /usr/bin/time -l python empty.py<br>
> 0.04 real 0.02 user 0.00 sys<br>
> 6782976 maximum resident set size<br>
><br>
> /usr/bin/time -l python test_1.py<br>
> 47.50 real 45.38 user 2.06 sys<br>
> 7222611968 maximum resident set size<br>
><br>
> /usr/bin/time -l python test_2.py<br>
> 49.91 real 49.78 user 0.07 sys<br>
> 76500992 maximum resident set size<br>
><br>
> /usr/bin/time -l ./test_1<br>
> 4.01 real 3.77 user 0.23 sys<br>
> 983851008 maximum resident set size<br>
><br>
> /usr/bin/time -l ./test_2<br>
> 1.63 real 1.61 user 0.00 sys<br>
> 43212800 maximum resident set size<br>
><br>
> Grüße,<br>
> Mark<br>
><br>
________________________________________<br>
<br>
Diese Mail erhalten Sie ueber die Mailingliste
python-users der Universitaet zu Koeln<br>
Nachrichten an: <a
href="mailto:python-users@uni-koeln.de" target="_blank"
rel="noreferrer" moz-do-not-send="true">python-users@uni-koeln.de</a><br>
Abonnement und Benutzereinstellungen: <a
href="https://lists.uni-koeln.de/mailman/listinfo/python-users"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">https://lists.uni-koeln.de/mailman/listinfo/python-users</a><br>
Listenarchiv: <a
href="https://lists.uni-koeln.de/pipermail/python-users/"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">https://lists.uni-koeln.de/pipermail/python-users/</a><br>
<br>
pyCologne Homepage: <a href="http://pycologne.de/"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">http://pycologne.de/</a><br>
</blockquote>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">________________________________________
Diese Mail erhalten Sie ueber die Mailingliste python-users der Universitaet zu Koeln
Nachrichten an: <a class="moz-txt-link-abbreviated" href="mailto:python-users@uni-koeln.de">python-users@uni-koeln.de</a>
Abonnement und Benutzereinstellungen: <a class="moz-txt-link-freetext" href="https://lists.uni-koeln.de/mailman/listinfo/python-users">https://lists.uni-koeln.de/mailman/listinfo/python-users</a>
Listenarchiv: <a class="moz-txt-link-freetext" href="https://lists.uni-koeln.de/pipermail/python-users/">https://lists.uni-koeln.de/pipermail/python-users/</a>
pyCologne Homepage: <a class="moz-txt-link-freetext" href="http://pycologne.de/">http://pycologne.de/</a>
</pre>
</blockquote>
</body>
</html>