[python-users] Geschachtelte Listen

[Dr. Mark Asbach]

Hallo Dirk,

Dein Problem ist, dass die Listen Elemente haben, die entweder ein Integer oder aber eine Klasseninstanz einer Subliste darstellen. Damit sind in der Liste zwangsläufig Objekte vorhanden, d.h. jeder Listeneintrag selbst ist ein Pointer. Eine einfach verkettete Liste braucht jeweils zusätzlich einen Pointer zur Herstellung der Verkettung. Darüber hinaus muss jeder Eintrag unterschieden werden können zwischen Subliste und Eintrag. Das passiert über einen weiteren Pointer (in C++ auf die Virtual Method Table der jeweiligen Klasse). Damit kannst Du als Abschätzung der Größenordnung 3 Pointer pro Element annehmen. Auf einem 64-Bit-System also 3*8 = 24 Bytes. Unter 40 Mio * 24 = 0.96 Gb kannst Du also auf einem 64-Bit-System niemals landen, selbst wenn der restliche Speicher-Overhead der Listen und Klassen 0 ist. Andere Programmiersprachen haben das ähnlich.

Grüße,
Mark

-- 
Dr. Mark Asbach
pixolus GmbH
Große Brinkgasse 2b, 50672 Köln
https://pixolus.de, Tel +49 221 949992-20
Registergericht: Amtsgericht Köln, HRB 80243
Geschäftsführer: Dr. Mark Asbach, Dr. Stefan Krausz

> 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.
> Von: Dirk Hünniger <dirk.hunniger at googlemail.com>
> Betreff: Geschachtelte Listen
> Datum: 23. Juni 2019 um 21:43:02 MESZ
> An: python-users at uni-koeln.de
> 
> 
> 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;
> }
> 
> 
> 
> 
> ________________________________________
> 
> 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/

-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : smime.p7s
Dateityp    : application/pkcs7-signature
Dateigröße  : 7763 bytes
Beschreibung: nicht verfügbar
URL         : <http://lists.uni-koeln.de/pipermail/python-users/attachments/20190624/1461a9c1/attachment.p7s>