Parallele Umbenennung

Angenommen ich habe eine Menge von benamsten Objekten, und möchte mehrere in einem Schritt umbenennen. Die Benennung muss aber immer eindeutig sein. Dann kann es natürlich zu Überschneidungen kommen (wie bei A->B, B->A), oder ich muss auf die Reihenfolge achten (wie bei A->B, B->C).

Einfachste Lösung ist natürlich, die Umbenennung in zwei Phasen durchzuführen, wobei in der ersten Phase alle betroffenen Objekte eindeutige temporäre Namen bekommen, und in der zweiten Phase diese in die eigentlich gewünschten Namen geändert werden, also z.B. für A->B, B->A Phase 1 A->Temp1, B->Temp2 und Phase 2 Temp1->B, Temp2->A. Damit vermeidet man alle Schwierigkeiten mit Überschneidungen oder Reihenfolge, für den Preis von doppelt so vielen Umbenennungen wie eigentlich nötig (im worst case).

Meine Frage ist, ob es einen einfachen Algorithmus gibt, der das ohne überflüssige Umbenennungen hinbekommt.

Ich denke schon, dass es einen Algorithmus gibt, der müsste nur intern Zustände speichern können und ein paar Checks durchführen bevor der die Umbenennung durchführt.

Ich kenne mich in der Algorithmentheorie nicht so aus - ich meine die Frage: ist ein Verfahren mit internen Zuständen noch ein Algorithmus?

Werden die Objekte denn alleinig durch ihren Namen Identifiziert? Name muss ja nicht unbedingt Identität sein.

Nein, ich könnte sie auch über einen Index identifizieren. Nützt mir nur nichts, da bei der Umbenennung auf Namenseindeutigkeit geprüft wird, und ich diesen Code nicht ändern kann.

nur die Umbenennung an sich ist eine teurere oder sonstwie problematische Aktion,
aber ansonsten besteht die Möglichkeit für ein umfassendes Programm,
welches alle Eingaben (Liste der Dinge, bisherige Namen, jeweils gewünschte Namen) kennt
und beliebig im Speicher hantierten kann, Listen, Maps, temporäre Hilfsobjekte je Umbenennung anlegen,
und die nötigen Umbenennungen in beliebiger Reihenfolge aufrufen kann?

was naheliegt kann man sich doch recht schnell denken:
alle Eingaben in Hilfsobjekte ‘Ding’ verarbeiten, eine Map X alter Name auf Dinge + eine Map Y neuer Name auf Dinge

in einem Durchlauf bestimmen welche neuen Namen frei sind, Map X hilft,
die Dinge dazu direkt umbenennen,

gleichzeitig für diese bereits umbenannten Dinge noch den alten Namen in die Programmierhand nehmen
und nachschauen, ob andere Dinge diesen Namen wünschen (Map Y),
diese dann auch zur möglichen Umbenennung vormerken,
im Anschluss an die erste Menge an Namen oder auch jeweils gleich durchführen (und wieder alten Namen prüfen usw., rekursiv)

wenn mit ersten Durchlauf fertig und auch Folgebearbeitung durch freigewordene Namen,
und immer noch Dinge nicht umbenannt sind, dann heißt das dass es Zyklen gibt, kein Name frei (eben etwa A->B, B->A),

hier ist dann unumgänglich, einmal temporär umzubenennen (welches Ding dürfte egal sein), und schauen ob es mit dem freien Namen (rekursiv) weitergeht,
etwas muss auf jeden Fall gehen, aber nicht unbedingt alles, es können ja mehrere unabhängige Zyklen bestehen

soweit schon zu kompliziert um als ‘einfacher Algorithmus’ zu gelten?

[QUOTE=SlaterB]

soweit schon zu kompliziert um als ‘einfacher Algorithmus’ zu gelten?[/QUOTE]

Nein, nach etwas überlegen bin ich zu einer ähnlichen Vorgehensweise gekommen. Erst mal schauen, welche “neuen” Namen nicht unter den “alten” Namen auftauchen, und diese Umbenennungen ausführen und aus der Liste (oder Map) streichen. Wiederholen, bis nichts mehr geht. Ist noch was da, sind das die Zyklen, für die man temporäre Variablen braucht.

Es gibt ja Tools, um Code unleserlich zu machen - alle Namen werden durch zufällige Zeichenketten ersetzt.

Wenn man nachschaut, ob diese Tools irgendwelche Bibliotheken benutzen, könnte man vielleicht schnell zur Lösung kommen.

wo Zufall besteht kann man ja einfach nochmal Zufall nehmen, wenn ein Konflikt auftritt :wink:
kein kompliziertes Regelwerk nötig

ich habe irgendwie nicht ganz verstanden worum es geht :smiley:

wo ist das problem einfach eindeutige neue namen zu vergeben sodass überschneidungen nicht möglich sind?

Das ist nicht das Problem. Das Problem ist: Es sei eine Menge von Umbenennungen gegeben, und es sei sichergestellt, dass am Ende auch kein Name doppelt vergeben ist. Nun muss aber auch sichergestellt werden, dass sich während der verschiedenen Umbenennungen keine Dopplungen ergeben. So wie man nicht

a = b;
b = a;

schreiben kann, sondern eine temporäre Zwischenvariable braucht. Hier trivial, kann bei vielen Umbenennungen ziemlich unübersichtlich werden.

Aber ich habe ja jetzt schon einen Ansatz, ich mache das Thema mal zu.

Ohne deine Autorität zum Schließen untergraben zu wollen (wolltest du vielleicht einfach nur auf “gelöst” setzen?) : Das ganze erinnert mich irgendwie an https://theinfosphere.org/Futurama_theorem - in dem Sinne, dass man dann mit zwei temporären Variablen auskommen sollte - aber vielleicht täuscht das gerade (habe noch nicht sooo intensiv über das Problem nachgedacht)