Speicher Management

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Anna96
User
Beiträge: 4
Registriert: Sonntag 10. Dezember 2017, 12:22

Hallo,
Nach langer Fehlersuche habe ich rausgefunden, dass manche Speicheradresse doppelt vergeben werden. wie kann das verhindert werden?

Genauer: Für mein Problem habe ich einen Graphen gebaut, der aus Knoten Objekten. Unteranderem führen diese Knoten Objekte ein Atribut eine Liste, die die Färbung der inzidenten Kanten enthält. Leider gibt zwei unterschiedliche Knoten, bei dem diese Liste auf den gleichen Speicheradressen liegen. Was natürlich Fehler im Output produziert.

Das hier ( https://docs.python.org/2/c-api/memory.html ) Speichermanagement in Python verstehe ich nicht ganz.
Müsste ich für jedes Atribut im Knotenobjekt Speicher allokiieren oder für das gesamte Knotenobjekt? Ich kann die Größe der Knoten Objekte am Anfang nur nach oben Abschätzen, aber nicht genau bestimmen.

Vielen Dank für eure Hilfe
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Anna96 hat geschrieben:Leider gibt zwei unterschiedliche Knoten, bei dem diese Liste auf den gleichen Speicheradressen liegen.
Dann handelt es sich mit hoher Wahrscheinlichkeit um die selbe Liste, d.h. es ist ein Programmierfehler, der nicht bei Python liegt, sondern bei dir oder ggf bei einer von dir verwendeten Bibliothek. Deine Frage zielt auch auf einen Bereich ab, der nicht von der Python-Spezifikation definiert wird. Mit anderen Worten: Das Speichermanagement kann zwischen einzelnen Python-Implementierungen völlig unterschiedlich gehandhabt werden. Darauf gibt es also keine Antwort, die für Python generell gelten kann. Allgemeint lässt sich nur festhalten: Gleiche Speicheradresse = gleiches Objekt.
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

Moin,

Python legt generell nie zwei unterschiedliche Objekte zur selben Zeit an die selbe Adresse. Dein Link beschreibt die C-API von Python. Das ist nur relevant, wenn du ein Modul in C schreibst.

Wenn du keine C-Erweiterung schreibst, wäre meine Vermutung eher, dass du zwei Knoten die selbe Liste zuweist. Python macht keine impliziten Kopien beim Zuweisen. Die Lösung wäre, nicht die gleiche Liste in zwei Knoten zu verwenden. Damit man genaueres sagen könnte, müsstest du ein lauffähiges Minimalbeispiel zeigen.
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Mit der C-API hat das eher nix zu tun. Sondern irgendwo reichst du in zwei Knotenobjekte die gleiche Liste rein.

Du kannst damit aucf verschiedene Weisen umgehen, aber ohne Code kann man schwer beurteilen, was die geeignetste Variante ist. Zur Not hilft ein copy.deepcopy, aber eigentlich geht man eher hin & reicht eigene Listen rein.
Anna96
User
Beiträge: 4
Registriert: Sonntag 10. Dezember 2017, 12:22

Hallo, danke für die schnellen Antworten. Darüber, dass ich zwei Pointern das gleiche Objekt zuweise habe ich natürlich auch schon nachgedacht, habs aber auch noch mal überprüft. Allerdings habe ich dabei gemerkt, dass ich mich ein wenig falsch ausgedrückt habe. Es sieht wie folgt aus:

Angenommen ich habe die Knoten 1 und 2 (bei denen dieser fehler entsteht) und beie haben als Atribut eine Liste färbung. Dann ist
id(1.färbung) verschieden von id(2.färbung),
aber z.B. der 3. Listeneintrag von der ersten Liste hat die gleiche Speicheradresse wie der 2. Listeneintrag von der 2. Liste. , also
id(1.färbung[3])=id(2.färbung[2])

Da kann es ja nicht sein, dass ich einfach nur die gleiche färbungsliste zwei unterschiedlichen Knoten zugewiesen habe, oder?
Für ein Minimalbeispiel bräuchte ich wohl ein wenig Zeit. Besten Dank
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Naja, das Prinzip geteilter Referenzen gilt ja für alles. Wenn du ein Objekt in zwei Listen steckst, ist das immer noch ein Objekt. Und wenn es veränderlich ist, “sehen” auch beide Listen die Veränderung.
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

Wie gesagt: Python kopiert beim Zuweisen nicht. Wenn du also das selbe Objekt in zwei Listen steckst, dann steckt das Objekt danach in zwei Listen und kann über beide gleichberechtigt benutzt und verändert werden.

In Python gibt es keine Pointer. Es gibt Objekte und Namen für Objekte (z. B. Variablennamen, aber auch Listeneinträge o. Ä.), wobei ein Objekt beliebig viele Namen haben kann.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Welchen Typ haben die Listenelemente denn? Strings werden wiederverwendet, wenn sie einmal erstellt wurden. Zahlen im kleineren Bereich werden ebenfalls im Speicher gehalten und somit nicht jedes Mal neu erstellt. Das sind schon zwei Punkte, wo interne Cache-Mechanismen durchaus zur selben Speicheradresse führen können, obwohl man das als Python-Programmierer nicht explizit so angewiesen hat. Daher sollte man sich um solche Dinge auch nicht allzu viele Gedanken machen, denn es sind Interna, die wie gesagt bei anderen Implementierung (PyPy, Jython, ...) sowieso ganz anders sein können. Du solltest halt deine wie auch immer gearteten Prüfungen nicht von einer konkreten Speicheradresse abhängig machen.
Anna96
User
Beiträge: 4
Registriert: Sonntag 10. Dezember 2017, 12:22

Hmm, tatsächlich habe ich in meinen Test bis jetzt nur kleine Werte von 0 bis 2 und None drin stehen. Das erklärt die gleichen id(). Leider habe ich den Fehler immer noch nicht beheben können :( Ich werde jetzt mal das Minimal BSP hochladen. Ist leider imme rnoch ziemlich groß und vielleicht verwirrend. Ich baue hier rekursiv den Graphen des n-dim Hypercubes auf, wobei die Knoten durch die Namen von 0 bis 2^n gekennzeichnet sind.

Zuerst meine abgespickte Node Klasse

Code: Alles auswählen

class Node:
    def __init__(self,binary,n=5,c=3):
        """
        @Input: int(binary): value of Node, int(n): dim of cube, int(c): #colours
        """
        self.name=binary            
        self.children=[]            #list with list elemnets [child,color]
        self.visit=0
und jetzt die Funktion die den Cube baut.

Code: Alles auswählen

    def build(n=5,c=3):
        """
        built rekursiv a n-Cube using a Brightsearch, where every Node get a number. the n-cube is rooted by 2^n 
        @param: int(n), dim of Q
        @return: Node(), its the highest Node 111..1 in Q
        """
        ####Initialisation of Q=Q(1)        
        root=Node(1)
        zero=Node(0)
        root.children.append([zero,None])


    #### n malige Verdopplung of Q: build a "deep" copy of Q by using brithsearch and connect carfully the nodes setting the right childrens
        for i in range(n-1):       #in every loop we make a copy of k-dim cube Q and multiply the name of the copy with 2 and the name of the original node of each node is multiplied with 2 and increment. the copy node is a child of its original

            copy=Node(root.name*2)
            root.name=root.name*2 +1
            root.children.append([copy,None]) 
            root.visit+=1
            copy.visit=root.visit
            
            q=deque([root]) 

            while q:
                first=q.popleft()
                for child in first.children[:-1]:     #the last child is the aktual copy                                                  
                    if (i%2==0 and child[0].visit %2==0) or (i%2==1 and child[0].visit %2 ==1):         #for next Iteration  of the for-loop the nodes have to be unvisited. 
                        child[0].visit+=1
                        copy=Node(child[0].name*2)
                        copy.visit=child[0].visit
                        child[0].name=child[0].name*2+1
                        child[0].children.append([copy,None])
                        first.children[-1][0].children.append([copy,None])
                        q.append(child[0])
                        
                    
                    else:
                        first.children[-1][0].children.append(child[0].children[-1])
                
        return(root)
Was mir Problme macht, ist die liste children. Diese siet ja nach der build Funktion etwa so aus [[knoten 1,None],...,[knoten k ,None]. Wenn ich nun wenn ich nun den Qube Q=bulit(3,2) erstelle und dann im Knoten mit dem Namen 4 der Liste children die None durch 1 ersetzt, dann wird auch in der liste children vom Knoten mit Namen 1 etwas verändert. Hier die Ausgabe für die Knoten, nachdem für Knoten 4 das None durch 1 ersetzt habe:
[codebox=text file=Unbenannt.txt]
#####2.Iteration durch Q
7 : children: [(3, None), (5, None), (6, None)]
3 : children: [(1, None), (2, None)]
5 : children: [(1, None), (4, None)]
6 : children: [(2, None), (4, None)]
1 : children: [(0, 1)]
2 : children: [(0, None)]
4 : children: [(0, 1)]
0 : children: []
[/code]
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Mindestens ein Problem hast du denke ich hier:

Code: Alles auswählen

 first.children[-1][0].children.append(child[0].children[-1])
Haengst du keine *Kopie*, sondern die originale 2-elementige Liste child[0].children[-1] in first.children. Jede subsequente Veraenderung von eben dieser Liste zeigt sich dann in beider children-Listen.

Ich wuerde dir nachdruecklich raten auf das viele rumgeliste zu verzichten, und stattdessen ein namedtuple zu verwenden, welches Knoten und Farbe bezeichnet.

Code: Alles auswählen

from collections import namedtuple
T = namedtuple("T", "knoten farbe")
child = T(None, "rot")
child.farbe = "blau" #kracht!
Da kann dir das nicht mehr passieren, und du bist gezwungen, ein neues Exemplar von T (in meinem Test) zu erstellen, mit dem alten Knoten, und einer neuen Farbe, und das an der entsprechenden Stelle einzufuegen.
Anna96
User
Beiträge: 4
Registriert: Sonntag 10. Dezember 2017, 12:22

Vielen, vielen Dank. Genau nach so einer Dummheit habe ich nach den ersten Antworten auf meiner Frage gesucht. Dann aber wohl einfach ein Brett vorm Kopf gehabt. Die Namedtuple kannte ich nicht. Auch dafür vielen Dank. Das wird jetzt eingearbeitet.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Schön dass sich das letztlich geklärt hat. Eine Sprache wie Python abstrahiert halt viel mehr als C und bringt seine eigenen Optimierungen mit. Man sollte immer im Rahmen der verwendeten Sprache denken. Und daher gelten gewisse Annahmen manchmal eben nicht. ;)
Antworten