[python-users] Geschachtelte Listen
Dirk Hünniger
dirk.hunniger at googlemail.com
Mi Jun 26 00:47:16 CEST 2019
So jetzt noch mal ein Quelltext. Der jetzt auch in den kompliziertesten
Fällen die mir einfallen funktioniert.
und jetzt gehe ich endlich schlafen und weiß auch warum ich besser keine
Pointerarithmetik veranstalte.
Viele Grüße Dirk
#include <iostream>
#include <vector>
#include <iostream>
using namespace std;
union NodeUnion
{
public:
int32_t n;
int32_t c;
};
class Node {
public:
bool isLeaf;
NodeUnion u;
};
class Rose {
public:
vector<Node> *v;
vector<int> current;
Rose() {
v=new vector<Node>();
Node n;
n.isLeaf=false;
v->push_back(n);
current.push_back(&(v->back())-&(v->front()));
(current.back()+&(v->front()))->u.n=current.back();
}
void pushChar(int c) {
cout << c << endl;
Node n;
n.isLeaf=true;
n.u.c=c;
v->push_back(n);
for (int i : current) {
(i+&(v->front()))->u.n++;
}
}
void pushNode() {
Node n;
n.isLeaf=false;
v->push_back(n);
for (int i : current) {
(i+&(v->front()))->u.n++;
}
current.push_back(&(v->back())-&(v->front()));
(current.back()+&(v->front()))->u.n=&(v->back())-&(v->front());
}
int print(int current_print) {
cout << "[";
int current_iter=current_print;
int offset=0;
while ((current_iter-1)!=(current_print+&(v->front()))->u.n) {
if (current_iter!=current_print) {
Node *n=current_iter+&(v->front());
if (n->isLeaf) {
cout << n->u.c;
}
else {
current_iter=print(current_iter)-1;
}
cout << ",";
}
current_iter++;
}
cout << "]";
return current_iter;
};
};
int main()
{
Rose rr;
rr.pushChar(1);
rr.pushNode();
rr.pushChar(2);
rr.current.pop_back();
rr.pushChar(3);
rr.pushNode();
rr.pushChar(6);
rr.pushChar(7);
rr.pushChar(8);
rr.current.pop_back();
rr.pushChar(9);
rr.pushChar(10);
rr.pushNode();
rr.pushChar(11);
rr.pushNode();
rr.pushChar(12);
rr.current.pop_back();
rr.pushChar(13);
rr.print(rr.current.front());
cout << endl;
/*
Rose r;
for (long i=0;i<100; i++) {
if ((i%10)!=0) {
r.pushChar(i%256);
}
else {
r.pushNode();
}
}
r.print(r.current.front());
//cout << "Hello, World!";
Rose rx;
for (long i=0;i<40100100; i++) {
if ((i%1000)!=0) {
rx.pushChar(i%256);
}
else {
rx.pushNode();
}
}
*/
cin.get();
return 0;
}
On 6/25/19 9:04 PM, Klaus Bremer wrote:
> Hallo Dirk,
>
> ich fürchte, diese Anforderung lässt sich mit statischer Typisierung nicht so einfach umsetzten. Du könntest in C ein struct aus einem Byte und einer union anlegen. Das Byte fungiert als Flag, ob die union einen Integer oder einen Pointer auf eine Subliste enthält. Das macht Datenstruktur und Algorithmus nicht gerade einfacher, und auch der Speicherbedarf steigt um ein Byte (oder ein Bit, falls Du das so hinbekommst – mein C ist schon etwas her) pro Listeneintrag.
> Wenn es noch allgemeiner sein soll, läuft es eigentlich auf folgendes hinaus: pro Element ein Pointer, und Typ und Wert befinden sich im verwiesenen Object. Dann könntest Da aber auch gleich Python nehmen ;)
>
> Gruß
> Klaus
>
>
>> Am 25.06.2019 um 19:31 schrieb Dirk Hünniger via python-users <python-users at uni-koeln.de>:
>>
>> Diese Nachricht wurde eingewickelt um DMARC-kompatibel zu sein. Die
>> eigentliche Nachricht steht dadurch in einem Anhang.
>>
>> This message was wrapped to be DMARC compliant. The actual message
>> text is therefore in an attachment.
>>
>> jetzt komme ich endlich mal dazu mir deine Lösung genauer anzuschauen.
>> In der Tat löst sie genau das von mir angegebene Beispiel maximal
>> speichereffizient. Mein Beispiel lautete ja:
>>
>>
>> [1,2,3,4,[5,6,7,8,[9,10,11,12]]]
>>
>> 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.
>>
>> Viele Grüße Dirk
>>
>> On 6/24/19 12:52 PM, Dr. Mark Asbach wrote:
>>> 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 empty.py
>>> 0.04 real 0.02 user 0.00 sys
>>> 6782976 maximum resident set size
>>>
>>> /usr/bin/time -l python test_1.py
>>> 47.50 real 45.38 user 2.06 sys
>>> 7222611968 maximum resident set size
>>>
>>> /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
>>>
>>> Grüße,
>>> Mark
>>>
>> jetzt komme ich endlich mal dazu mir deine Lösung genauer anzuschauen.
>> In der Tat löst sie genau das von mir angegebene Beispiel maximal
>> speichereffizient. Mein Beispiel lautete ja:
>>
>>
>> [1,2,3,4,[5,6,7,8,[9,10,11,12]]]
>>
>> 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.
>>
>> Viele Grüße Dirk
>>
>> On 6/24/19 12:52 PM, Dr. Mark Asbach wrote:
>>> 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 empty.py
>>> 0.04 real 0.02 user 0.00 sys
>>> 6782976 maximum resident set size
>>>
>>> /usr/bin/time -l python test_1.py
>>> 47.50 real 45.38 user 2.06 sys
>>> 7222611968 maximum resident set size
>>>
>>> /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
>>>
>>> Grüße,
>>> Mark
>>>
>>
>> ________________________________________
>>
>> 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/
> ________________________________________
>
> 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/
Mehr Informationen über die Mailingliste python-users