Geschachtelte Listen
Dirk Hünniger
dirk.hunniger at googlemail.com
So Jun 23 21:43:02 CEST 2019
Hallo,
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;
}
Mehr Informationen über die Mailingliste python-users