Tausch-Algorithmus

Fireball89 · 20. August 2012

Hallo,

ich habe folgendes Problem. Gegeben sei eine Menge von Tupeln (x,y) wobei x und y natürliche Zahlen sind.
Diese Tupel beschreiben eine Index-Änderung in einer SQL-Datenbank.

Bsp: {(4,2),(1,4),(2,1)}
Heisst: Tabelle-Eintrag mit Index 4 soll nun Index 2 sein und, Index 1 wird jetzt Index 4 und Index 2 wird Index 1.

Logischerweise kann man die Änderungen nicht nacheinander ausführen, da nach der ersten Änderung der Index 2 nicht mehr eindeutig wäre.

Gibt es für so ein Problem bereits einen bekannten Algorithmus oder muss ich mir selber einen überlegen? Googlen hat mich nicht weitergebracht.

Smagjus · 20. August 2012

Bei "normaler" Proammierung muss man einen der Werte irgendwo zwischenspeichern, wenn man tauschen möchte. Ist vielleicht unschön, aber du könntest den Index von 2 zuerst auf z.b. 999999 und danach den Index von 4 nach 2 ändern. Dann änderst du den Index bei 1 auf 1000000 und machst so weiter. Eine andere Lösung ist mir nicht bekannt.

xxMuahdibxx · 20. August 2012

Nun ich geh mal aus der Antiprogramierersicht ran .

Tasche 4 zu 999 tausche 1 zu 998 tausche 2 zu 997
tausche 999 zu 2 tausche 998 zu 4 tausche 997 zu 1
Den Zwischenschritt wirst brauchen weil sonst wie du sagst ja die Daten weg sind .

Madman1209 · 20. August 2012

Hi,

klingt nach "Dreiertausch aufgebohrt"

1. Speichere "Index 2" zwischen.
2. Index 4 überschreibt nun Index 2 und Index 1 dann Index 4
3. Jetzt holst du den zwischengespeicherten Wert von Index 2 wieder und überschreibst damit 1.
4. Zwischenspeicher löschen.

Willst du das direkt in SQL machen (also Stored Procedure) oder mit einer Abfrage oder mit einer zusätlichen Programmiersprache? Wäre wichtig zu wissen...die Lösungen unterscheiden sich nämlich frappierend.

VG,
Mad

Fireball89 · 20. August 2012

Es geht um einen allgemeinen Algorithmus. Das Beispiel alleine reicht nicht^^

Da ich mit PHP auf die DB zugreife, wäre es kein Problem, alle betroffenen Einträge zwischen zu speichern und aus der DB zu löschen. Dann kann ich in PHP problemlos den Index ändern und dann die Einträge wieder neu in der DB anlegen.

Denke mal, dass das so klappt. Aber ein direkter Weg wäre auch interessant.

Ich habe noch einen sehr wichtigen Fakt vergessen: Sei n die Anzahl der Einträge in der Tabelle. Dann sind alle Indizes von 1 bis n vergeben.

Smagjus · 20. August 2012

Wenn deine Tabelle voll ist, dann wirst du wohl oder übel den Umweg nehmen, dass du nicht die Indizes tauschst, sondern die Inhalte der Spalten. Das musst du dann in PHP programmieren.

Fireball89 · 20. August 2012

Nein, das meinte ich nicht. Obwohl die Indizes 1-n vergeben sind, sind natürlich temporäre Indizes > n erlaubt. Nachdem der Algorithmus fertig ist, müssen alle Indizes wieder <= n sein.
Also die Lösung in PHP mit Löschen und dann wieder Einfügen geht schon mal.

Falls noch jemand eine Idee für den direkten Weg hat, wär ich trotzdem interessiert.

Daaron · 20. August 2012

Ich würde rotzfrech ne temporäre Tabelle anlegen und dann jeweils durch gehen: lies Index X von Quelle, schreibe nach Index Y ins Temp. Danach, wenn alles durch ist und nix fehlt einfach die Quelle löschen udn durch Temp ersetzen.

Fireball89 · 20. August 2012

So, mir ist doch etwas eingefallen. Sei M das Array der Index-Tupel.
Hier mal in Pseudocode:

Code:

n = count(tabelle);
foreach (M as oldkey => newkey) {
	temp_index = newkey+n;
	SQL-execute(UPDATE tabelle SET index=temp_index WHERE index=oldkey);
}
foreach (M as oldkey => newkey) {
	temp_index = newkey+n;
	SQL-execute(UPDATE tabelle SET index=newkey WHERE index=temp_index);
}

Hab noch nicht getestet, aber sollte gehen.

Suche

Tausch-Algorithmus

Fireball89

Captain

Smagjus

Vice Admiral

xxMuahdibxx

Fleet Admiral

Madman1209

Fleet Admiral

Fireball89

Captain

Smagjus

Vice Admiral

Fireball89

Captain

Daaron

Fleet Admiral

Fireball89

Captain

Ähnliche Themen