[python-users] Geschachtelte Listen
Klaus Bremer
klaus.bremer at bmcct.de
Mo Jun 24 10:13:25 CEST 2019
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/
Mehr Informationen über die Mailingliste python-users