Geschachtelte Listen

[Dirk Hünniger]

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;
}