[python-users] Geschachtelte Listen
Dirk Hünniger
dirk.hunniger at googlemail.com
Mo Jun 24 10:25:02 CEST 2019
Hallo Klaus,
geht bei mir leider nicht. Da ich einen Parse Tree habe. Der ist leider
nicht linear sondern ein echter Baum. Deine Lösung kann ich aber in
anderen bei mir autrenden Problemen nutzen. Die Lösung wird sein, dass
ich immer nur einen Quelltext als Baum in den Speicher lade und nicht
alle Quelltext zusammen in einem Baum.
Viele Grüße Dirk
On 6/24/19 10:13 AM, Klaus Bremer wrote:
> Hallo Dirk,
>
> Du verwendest eine ungünstige Datenstruktur. Speichere die Listen in Python nicht geschachtelt, sondern linear, so dass pro Liste ein einheitlicher (numerischer) Datentyp enthalten ist. Dann kannst Du bei großen Datenmengen durch die Verwendung von arrays (Modul aus der Standard-Library) statt Listen einiges an Speicher einsparen. Bei arrays musst Du ggf. auf einen numerischen Überlauf achten.
>
> Wenn Du später über die von Dir ursprünglich gewünschte geschachtelte Datenstruktur iterieren möchtest, so schreibe Dir dann einfach einen passenden Iterator.
>
> Gruß
> Klaus
>
>
> ——
> Beispiel: lineare Listen:
>
>
> import sys
>
> base = 1
> amount = 1000
> depth = 3
> list_memory_usage = 0
> item_memory_usage = 0
>
> root = list()
>
> for p in range(depth):
> a = list()
> for q in range(base, base + amount):
> a.append(q)
> item_memory_usage += sys.getsizeof(q)
> root.append(a)
> base = q + 1
>
> list_memory_usage = sys.getsizeof(root)
>
> #print(root)
> print(list_memory_usage)
> print(item_memory_usage)
> print(item_memory_usage + list_memory_usage)
>
>
> ——
> Beispiel: Sublisten als arrays:
>
> import array
> import sys
>
> base = 1
> amount = 1000
> depth = 3
> list_memory_usage = 0
> item_memory_usage = 0
>
> root = list()
>
> for p in range(depth):
> a = array.array('i')
> for q in range(base, base + amount):
> a.append(q)
> root.append(a)
> item_memory_usage += a.itemsize * len(a)
> base = q + 1
>
> list_memory_usage = sys.getsizeof(root)
>
> #print(root)
> print(list_memory_usage)
> print(item_memory_usage)
> print(item_memory_usage + list_memory_usage)
>
>
>
>> Am 23.06.2019 um 21:43 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.
>>
>> ich betrachte geschachtelte Listen folgender Form.
>>
>> [1,2,3,4,[5,6,7,8,[9,10,11,12]]]
>>
>> Die Liste hat zwei Parameter die für mich interessant sind. Erstens die
>> Elementzahl, sie ist hier 12. Zweitens die Sublistenlänge, sie ist hier
>> 4. Ich betrachte nun eine Liste mit der Elementzahl 40 Millionen und der
>> Sublistenlänge 1000. Alle Versuche diese in Haskell oder C++ oder Java
>> oder Python im Speicher zu erzeugen führten jeweils zu einem
>> Speicherbedarf von mehr als 1 GByte manchmal gar zu einigen. Am besten
>> schlug sich C++. Dennoch wundert es mich, dass der Speicherbedarf mehr
>> als 20 mal so groß wird wie die Elementzahl. Ich freue mich aus eure
>> Hinweise, wie man diese Dinge mit weniger Speicherbedarf verarbeiten kann.
>>
>> Viele Grüße Dirk
>>
>>
>> PS: Hier noch der Python 3 Quellcode, gefolgt vom C++ Quellcode
>>
>> class Rose:
>> def __init__(self):
>> self.v = []
>>
>> def push(self, n):
>> self.v.append(n)
>>
>> def pr(self):
>> print("[", end = "")
>> for x in self.v:
>> x.pr()
>> print(",", end = "")
>> print("]", end = "")
>>
>> class Leaf:
>> def __init__(self, x):
>> self.x = x
>>
>> def pr(self):
>> print(self.x, end= "" )
>>
>>
>> r=Rose()
>> for i in range(40100100):
>> if (i % 1000) != 0:
>> l = Leaf(i % 256)
>> r.push(l)
>> else:
>> l = Rose()
>> r.push(l)
>> r=l
>> input("Press Enter to continue...")
>>
>>
>> und nun der C++ Quellcode
>>
>>
>> #include <iostream>
>> #include <vector>
>> #include <iostream>
>> using namespace std;
>> class Node {
>> public:
>> virtual void push(Node *n) {};
>> virtual void print() {};
>> };
>>
>> class Rose : public Node {
>> public:
>> vector<Node*> *v;
>> Rose () {
>> v = new vector<Node*>();
>> }
>> void push(Node * n) {v->push_back(n);};
>> void print() {
>> cout << "[";
>> for (Node *x : *v) {
>> x->print();
>> cout << ",";
>>
>> }
>> cout << "]";
>>
>> };
>>
>> };
>>
>>
>> class Leaf : public Node {
>> public: char x;
>> void print() {
>> cout << x;
>> };
>> };
>> int main()
>> {
>> Rose rr;
>> Rose* r=&rr;
>> Rose* rx=&rr;
>>
>> for (long i=0;i<40100100; i++) {
>> if ((i%1000)!=0) {
>> Leaf *l=new Leaf();
>> l->x=i%256;
>> r->push(l);
>> }
>> else {
>> Rose* l= new Rose();
>> r->v->push_back(l);
>> r=l;
>> }
>> }
>> //rx->print();
>> //cout << "Hello, World!";
>> cin.get();
>> return 0;
>> }
>>
>>
>> ich betrachte geschachtelte Listen folgender Form.
>>
>> [1,2,3,4,[5,6,7,8,[9,10,11,12]]]
>>
>> Die Liste hat zwei Parameter die für mich interessant sind. Erstens die
>> Elementzahl, sie ist hier 12. Zweitens die Sublistenlänge, sie ist hier
>> 4. Ich betrachte nun eine Liste mit der Elementzahl 40 Millionen und der
>> Sublistenlänge 1000. Alle Versuche diese in Haskell oder C++ oder Java
>> oder Python im Speicher zu erzeugen führten jeweils zu einem
>> Speicherbedarf von mehr als 1 GByte manchmal gar zu einigen. Am besten
>> schlug sich C++. Dennoch wundert es mich, dass der Speicherbedarf mehr
>> als 20 mal so groß wird wie die Elementzahl. Ich freue mich aus eure
>> Hinweise, wie man diese Dinge mit weniger Speicherbedarf verarbeiten kann.
>>
>> Viele Grüße Dirk
>>
>>
>> PS: Hier noch der Python 3 Quellcode, gefolgt vom C++ Quellcode
>>
>> class Rose:
>> def __init__(self):
>> self.v = []
>>
>> def push(self, n):
>> self.v.append(n)
>>
>> def pr(self):
>> print("[", end = "")
>> for x in self.v:
>> x.pr()
>> print(",", end = "")
>> print("]", end = "")
>>
>> class Leaf:
>> def __init__(self, x):
>> self.x = x
>>
>> def pr(self):
>> print(self.x, end= "" )
>>
>>
>> r=Rose()
>> for i in range(40100100):
>> if (i % 1000) != 0:
>> l = Leaf(i % 256)
>> r.push(l)
>> else:
>> l = Rose()
>> r.push(l)
>> r=l
>> input("Press Enter to continue...")
>>
>>
>> und nun der C++ Quellcode
>>
>>
>> #include <iostream>
>> #include <vector>
>> #include <iostream>
>> using namespace std;
>> class Node {
>> public:
>> virtual void push(Node *n) {};
>> virtual void print() {};
>> };
>>
>> class Rose : public Node {
>> public:
>> vector<Node*> *v;
>> Rose () {
>> v = new vector<Node*>();
>> }
>> void push(Node * n) {v->push_back(n);};
>> void print() {
>> cout << "[";
>> for (Node *x : *v) {
>> x->print();
>> cout << ",";
>>
>> }
>> cout << "]";
>>
>> };
>>
>> };
>>
>>
>> class Leaf : public Node {
>> public: char x;
>> void print() {
>> cout << x;
>> };
>> };
>> int main()
>> {
>> Rose rr;
>> Rose* r=&rr;
>> Rose* rx=&rr;
>>
>> for (long i=0;i<40100100; i++) {
>> if ((i%1000)!=0) {
>> Leaf *l=new Leaf();
>> l->x=i%256;
>> r->push(l);
>> }
>> else {
>> Rose* l= new Rose();
>> r->v->push_back(l);
>> r=l;
>> }
>> }
>> //rx->print();
>> //cout << "Hello, World!";
>> cin.get();
>> return 0;
>> }
>>
>>
>>
>>
>> ________________________________________
>>
>> 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