Designentscheidung für nicht-rekursives Backtracking

[few]

Hallo!

Zuerst die abstrakte Formulierung meines Problems:

Gegeben ist ein bereits existierende Klasse, die einen Algorithmus ausführt. In diesem Algorithmus werden an verschiedenen Stellen Entscheidungen getroffen. Ist eine Entscheidung getroffen werden verschiedene Variablen der Klasse entsprechend geändert. Sind alle Entscheidungen getroffen wird eine Lösung ausgegeben. Meistens führt dieses Vorgehen zu einer Lösung. Aber nicht immer. Und da kommt das Problem: Es gibt keinen Weg zurück. Um zurück zu kommen müsste man alle Änderungen an den Variablen der Klasse protokollieren und ggf. Rückgängig machen können.

Die Frage ist jetzt wie ändere ich die Klasse am besten ab? Meine erste Idee war alle Variablen in eine eigene Klasse zu packen und getter und setter zu schreiben. Aber das wird sehr schnell sehr mühsam und unübersichtlich, da es sehr viele Variablen (~50) sind und es viele verschiedene Datentypen gibt (lists, dicts, dicts of dics, benutzerdefinierte Klassen). Hat jemand eine bessere Idee wie man das machen könnte?

Vielen Dank für eure Hilfe.

PS: Ich hätte fast die nicht abstrakte Formulierung vergessen: Es geht um Portage, den Paketmanager von Gentoo Linux und dessen dependency resolution. Der Sourcecode ist unter [1] zu finden.

[1] http://sources.gentoo.org/viewcvs.py/portage/main/ in trunk/pym/_emerge/depgraph.py

[Leonidas]

Hi few, willkommen im Forum,

Du könntest sowas wie Copy-on-write implementieren, dass bei jeder Änderung der Klasse, die Klasse kopiert wird und ganz oben auf einen Stack getan wird. Dann kannst du ziemlich trivial den Stack wieder zerlegen, falls du auf die alten Zustände der Klasse zugreifen willst.

[few]

Danke für deine Antwort.

Du könntest sowas wie Copy-on-write implementieren, dass bei jeder Änderung der Klasse, die Klasse kopiert wird und ganz oben auf einen Stack getan wird.

Ich habe die Befürchtung, dass dabei der Speicherverbrauch zu groß wird. Für gewöhnlich gibts zig tausend Änderungen. Portage muss auf vielen Platformen laufen, zum Teil auch welchen wo ein gewöhnliches System sehr wenig RAM hat.

[HerrHagen]

Meine erste Idee war alle Variablen in eine eigene Klasse zu packen und getter und setter zu schreiben. Aber das wird sehr schnell sehr mühsam und unübersichtlich, da es sehr viele Variablen (~50) sind und es viele verschiedene Datentypen gibt (lists, dicts, dicts of dics, benutzerdefinierte Klassen).

Du brauchst doch nicht für jede Variable einen einzelnen Setter schreiben. Mit __setattr__ könntest du einen allgemeinen Setter für alle möglichen Datentypen schreiben.

Code: Alles auswählen

>>> class problem:
	def __setattr__(self, name, value):
		print "Setting: %s, %s" % (name, value)

>>> x = problem()
>>> x.test = 3
Setting: test, 3
>>> x.test2 = []
Setting: test2, []

Du musst bloß aufpassen das du keine Endlosschleifen reinkriegst (passiert mit __setattr__ schnell mal...)

[Leonidas]

Ich habe die Befürchtung, dass dabei der Speicherverbrauch zu groß wird. Für gewöhnlich gibts zig tausend Änderungen. Portage muss auf vielen Platformen laufen, zum Teil auch welchen wo ein gewöhnliches System sehr wenig RAM hat.

Ansonsten könntest du sowas natürlich auch für einzelne Attribute durchführen und eventuell nur die letzen, hmm, 10 Änderungen oder wie viele du brauchst vorhalten.

Der Nachteil ist, dass das immer nur der Zustand der Variablen ist, kein Snapshot der ganzen Klasse.

[jerch]

Hätte einen Lösungsansatz mit einer Art Revisions-Dictionary anzubieten:

Code: Alles auswählen

class RevisionDict(dict):
    def __init__(self, *args, **kwargs):
        dict.__init__(self, *args, **kwargs)
        self.head_revision = 0

    def __setitem__(self, key, value):
        if not self.get(key):
            dict.__setitem__(self, key, {self.head_revision: value})
            self.head_revision += 1
        elif self[key][max(self[key])] != value: # besser mit is?
            self[key][self.head_revision] = value
            self.head_revision += 1

class Revision(object):
    def __init__(self):
        object.__setattr__(self, '_rev_dict', RevisionDict())

    def __getattr__(self, name):
        if name in self.__getattribute__('_rev_dict'):
            return self.__getattribute__('_rev_dict')[name] # hier deepcopy?
        return self.__getattribute__(name)

    def __setattr__(self, name, value):
            self._rev_dict.__setitem__(name, value)

class Testklasse(Revision):
    def __init__(self):
        Revision.__init__(self)
        self.pansen = "voll"
        self.pansen = "leer"

t = Testklasse()
t.kkk = "kkk"
t.kkk = "jjj"
t.kkk = 'jjj'
t.kkk = "kkk"
print t._rev_dict #{'pansen': {0: 'voll', 1: 'leer'}, 'kkk': {2: 'kkk', 3: 'jjj', 4: 'kkk'}}

Ich weiß nicht, obs für Dein Problem überhaupt praktikabel ist, das Speicherproblem dürfte immernoch evident sein. Auch war ich zu faul, Deinen Code durchzusehen, bei mehr als 5 Verschachtelungsebenen fängt mein Kopf an zu brummen
Das Bsp. ist nicht weiter durchdacht, aber vllt. hilft Dir der Ansatz weiter.

Edit: Race-Condition behoben.

[CM]

Hoi,

vielleicht wäre __slots__ ein Weg das Speicherproblem bei Leonidas ersten Ansatz etwas zu verringern - zumindest, wenn die Attribute sich in ihrer Zahl und ihrem Namen nicht verändern (der Code ist mir viel zu komplex, um da eben mal so durchzusteigen). Allerdings würde ich raten, dass Du die Zahl der Klassen(zustände) im Speicher immer noch limitieren wirst müssen.

HTH
Christian