Hallo Leute,
ich zermartere mir grad das Gehirn, komm aber nicht weiter, bin aber
überzeugt davon dass es eine ganz einfache, uralte, effiziente, coole,
vermutlich rekursive und allgemein bekannte Lösung gibt.
Meine Aufgabe ist es, in einer Datenbank einen Bereich von Sätzen mit
einem "Sortierschlüssel" zu belegen bzw. zu aktualisieren, und das mit
so wenigen Updates wie möglich. Ich nenne den Sortierschlüssel mal
"Positionsnummer", ist ein integer, und nach diesem Schlüssel erfolgt
dann die (sortierte) Anzeige. Sie Sortierung selbst ergibt sich nach
einigen anderen, hier irrelevanten Kriterien (und wer vermutet, es
handelt sich um eine Stückliste, liegt richtig :-)
nehmen wir an ich habe 5 Sätze, ich liste sie bereits richtig sortiert
auf, mit der noch falschen Positionsnummer:
1: 10
2: 20
3: 30
4: 400
5: 500
6: 60
Die "brachiale" Methode wäre, alle Sätze neu in 100er Schritten
druchzunumerieren, das sind aber 4 (teure) Updates auf die Tabelle (1:
10=>100, 2:20>200 usw)
Schon besser ist aber, nur Satz 4 und 5 zu aktualisieren, nämlich auf
Positionsnummer 40 und 50 (nur mehr zwei Updates)
ideal ist aber die Variante, nur Nummer 6 auf irgendwas größer 500 zu
aktualisieren (1 Update)
Nur - wie finde ich diese Variante?
Nebenbei: wie "groß" die Positionsnummer wirklich ist, ist irrelevant,
da diese selbst nicht sichtbar ist. Die Liste ist aber idR vorsortiert
in 100er Schritten, damit zwischen den Positionen genügend Platz ist, um
neue einzufügen (diese Vorsortierung erledigt ein Nachtlauf)
Eine schöne Analogie, die mir eingefallen ist: Ich habe einen Zug mit
vielen Waggons, möchte diese nach Länge sortieren, mit möglichst wenig
"an- und Abkuppeln"
Ich vermute mal, es läuft irgendwie darauf hinaus, die Liste in
"Gruppen" zu unterteilen, die in sich schon richtig sortiert sind, und
dann die kleinste Gruppe zu verschieben... aber ich bin leider hirntot
:-)
Wäre nett wenn mich jemand in die richtige Richtung stubsen könnte!
lg Michi
c.m. schrieb:> warum überhaupt eine position updaten/inserten, wenn man "order by"> selects machen kann?
weil ich keinen Einfluss auf die Applikation habe, und diese nun mal
"order by posnr" macht
Michael R. schrieb:> Die "brachiale" Methode wäre, alle Sätze neu in 100er Schritten> druchzunumerieren, das sind aber 4 (teure) Updates auf die Tabelle (1:> 10=>100, 2:20>200 usw)
teuer?!
Sowas lässt man über Nacht laufen und nach Datenbankzugriffen wird
sicher nicht mehr abgerechnet werden. Das war höchstens noch zu
Lochkartenzeiten üblich!
Schreiber schrieb:> Michael R. schrieb:>> Die "brachiale" Methode wäre, alle Sätze neu in 100er Schritten>> druchzunumerieren, das sind aber 4 (teure) Updates auf die Tabelle (1:>> 10=>100, 2:20>200 usw)>> teuer?!> Sowas lässt man über Nacht laufen und nach Datenbankzugriffen wird> sicher nicht mehr abgerechnet werden. Das war höchstens noch zu> Lochkartenzeiten üblich!
Menno, ich weiss schon warum ich "teuer" schreibe... die Sortierung muss
tagsüber schnell korrigiert werden, und jedes Update zieht einen
Rattenschwanz an Triggern etc nach sich, auf die ich keinen Einfluss
habe, deswegen muss ich updates sparen. nebenbei geht es nicht um 6
Sätze wie in meinem Beispiel, sondern ~10k. 10.000 Updates gegen 2 oder
3 ist ein bisschen Kleinvieh...
Ich möchte aber nicht darüber diskutieren, sondern einen Hinweis auf
einen (sicherlich existenten) Algoritmus. Danke!
Michael R. schrieb:> Ich möchte aber nicht darüber diskutieren, sondern einen Hinweis auf> einen (sicherlich existenten) Algoritmus.
Ich schlage folgendes vor:
1. Hinreichend großen Abstand zwischen den Index-Nummern. Wertebereich
konsequent ausnutzen
2. Neue Einträge immer in der Mitte zwischen dieen benachbarten einfügen
3. Im Bedarfsfall angrenzende Einträge um den halben Abstand zum
nächsten hin verschieben
Zusätzlich: Jede Nacht aufräumen.
Hallo,
wenn ich dein Problem richtig verstanden habe, dann kannst du einfach
die Zahlen in Strings wandeln und die Strings sortieren (und die
Verschiebung dann mit den Zahlen machen). Wenn die Updates beim
Umbenennen kritisch sind musst du im Sortieralgorithmus vorher die
verschiedenen Umbenennungsvarianten auf die Zugriffsanzahl prüfen und
dann die "günstigste" Variante auswählen.
Gruß Kai
Michael R. schrieb:> Nur - wie finde ich diese Variante?
Gar nicht, da deine Liste
SELECT * FROM Stückliste ORDER BY posnr
dir
10
20
30
60
400
500
liefert und du ÜBERHAUPT KEINE AHNUNG HAST
wie die Sortierung richtig wäre.
Du müsstest erst mal aus den Datensatzinhalten eine Sortierreihenfolge
bestimmen, im Hauptspeicher, damit diese Liste überhaupt entsteht. Wie
willst du das anstellen ?
1: 10
2: 20
3: 30
4: 400
5: 500
6: 60
Dann gibt es eigentlich nur die Strategie
FOR i = 2 TO max IF posnr[i]<=posnr[i-1] THEN posnr[i]=posnr[i-1]+1
und
FOR i = max DOWNTO 2 IF posnr[i-1]>=posnr[i] THEN posnr[i-1]=posnr[i]-1
und die nehmen, die weniger updates erfordert.
Alles andere (10er Schritte) führt nur zu mehr updates.
Schreiber schrieb:> Michael R. schrieb:>> Ich möchte aber nicht darüber diskutieren, sondern einen Hinweis auf>> einen (sicherlich existenten) Algoritmus.>> 2. Neue Einträge immer in der Mitte zwischen diesen benachbarten einfügen
Problem: nicht ich füge die Einträge ein. Außerdem gehts nicht nur um
Einfügen, auch ändert sich die für die Sortierung relevanten
Spalteninhalte. Ich krieg nur mit, dass eine liste neu sortiert werden
müsste.
> Zusätzlich: Jede Nacht aufräumen.
mach ich sowieso, die teuren Updates unter Tag sind mein Problem.
(und bevor du dich wieder über "teuer" beschwerst: "Kosten" im
Datenbank-Umfeld werden üblicherweise nciht in € gemessen :-)
Michael B. schrieb:> Michael R. schrieb:>> Nur - wie finde ich diese Variante?>> Gar nicht, da deine Liste> SELECT * FROM Stückliste ORDER BY posnr> liefert und du ÜBERHAUPT KEINE AHNUNG HAST> wie die Sortierung richtig wäre.
Doch, die hab ich.
> Du müsstest erst mal aus den Datensatzinhalten eine Sortierreihenfolge> bestimmen, im Hauptspeicher, damit diese Liste überhaupt entsteht. Wie> willst du das anstellen ?
Das kann ich, und das Ergebnis ist eben:
> 1: 10> 2: 20> 3: 30> 4: 400> 5: 500> 6: 60
und nun muss ich meine Positionsnummer möglichst billig so ändern, dass
das gewünschte ergebnis rauskommt.
> Dann gibt es eigentlich nur die Strategie> FOR i = 2 TO max IF posnr[i]<=posnr[i-1] THEN posnr[i]=posnr[i-1]+1> und> FOR i = max DOWNTO 2 IF posnr[i-1]>=posnr[i] THEN posnr[i-1]=posnr[i]-1> und die nehmen, die weniger updates erfordert.
Nö. Es gibt signifikant effizientere Strategien, die ich "im Kopf" auch
finde, nur an der Umwandlung in einen Algorithmus scheitere ich.
Michael R. schrieb:> Nö. Es gibt signifikant effizientere Strategien, die ich "im Kopf" auch> finde, nur an der Umwandlung in einen Algorithmus scheitere ich.
Ja. Das Falsch einsortierte suchen und nur dessen Positionsnummer ändern
und in die Mitte zwischen den benachbarten einsortieren.
Michael R. schrieb:>> 1: 10>> 2: 20>> 3: 30>> 4: 400>> 5: 500>> 6: 60>> und nun muss ich meine Positionsnummer möglichst billig so ändern, dass> das gewünschte ergebnis rauskommt.
Hier sind die Elemente 4+5 Falsch einsortiert. Hierzu einfach die 4 auf
7 und die 5 auf 8 ändern.
Noch einfacher wäre folgendes:
>> 10: 10>> 20: 20>> 30: 30>> 40: 400>> 50: 500>> 60: 60
Jetzt ist element 60 Falsch einsortiert und gehört auf Platz 35
Schreiber schrieb:> Ja. Das Falsch einsortierte suchen und nur dessen Positionsnummer ändern> und in die Mitte zwischen den benachbarten einsortieren.
Es gibt nicht "das falsch einsortierte", das können viele (im Extremfall
alle) sein
>>> 1: 10>>> 2: 20>>> 3: 30>>> 4: 400>>> 5: 500>>> 6: 60>>>> und nun muss ich meine Positionsnummer möglichst billig so ändern, dass>> das gewünschte ergebnis rauskommt.>> Hier sind die Elemente 4+5 Falsch einsortiert. Hierzu einfach die 4 auf> 7 und die 5 auf 8 ändern.
Eben nicht. 6 auf 600 ändern ist billiger
Michael R. schrieb:> Nö. Es gibt signifikant effizientere Strategien, die ich "im Kopf" auch> finde, nur an der Umwandlung in einen Algorithmus scheitere ich.
:anfang
Für (i=1...i=i_max)
Wenn (Element i an falschem Platz)
Dann
Suche benachbarte Elemente
füge Element in der Mitte dazwischen ein
Wenn (Liste jetzt richtig sortiert)
Dann END
Sonst GOTO :anfang
Den Fehlerfall "kein Platz an der richtigen Stelle" muss man natürlich
noch abfangen
sicher das du kein konsistenzproblem bekommen kannst, wenn ein prozess
die ID's umordnet während evtl. ein anderer grade welche selektiert hat
und sich drauf verlässt das hinter ID(x) datensatz(y) steckt?
Bei der trivialen Lösung war ich schon. Sie liefert zwar ein richtiges
Ergebnis, aber ein (manchmal extrem) suboptimales ergebnis.
Spiel das mal mit dem Fall "10.000 Elemente, Element 9.999 gehört auf 1"
durch: du verschiebst 9.999 Elemente, statt eines.
c.m. schrieb:> sicher das du kein konsistenzproblem bekommen kannst, wenn ein prozess> die ID's umordnet während evtl. ein anderer grade welche selektiert hat> und sich drauf verlässt das hinter ID(x) datensatz(y) steckt?
Ja. D Die posNr ist keine Id, nur ein Display-Sort-Hint.
Könnts ihr euch bitte vom DB-Hintergrund lösen, und versuchen das
problem an sich zu abstrahieren? :-)
Linear durchlaufen, Teilketten zählen und Kosten vergleichen:
10
20
30
400
500
60
Bruch zwischen 500 und 60
Behältst Du die 500, musst Du lediglich die 60 umbenennen => Kosten=1
behältst Du die 60, must Du die 400 und 500 umbenennen => Kosten=2
=> 60 umbenennen.
-------------------------------------
100
150
200 => danach kommt Bruch! (B)
30
400
500
60 (B)
Wenn Du am ersten Bruch bist, hast Du die Wahl, die 200 oder die 30
beizubehalten.
beibehalten der 200 kostet Dich die Umbenennung der 30 und 60, Kosten=2
beibehalten der 30 kostet Dich die Umbenennung der 100,150 und 200 und
die 400 und 500 => K=5!
Schlimmstenfalls hast Du n Teilketten, wenn die Positionsnummern alle um
1 fallen.
Berechne für jede Teilkette die Annahme, dass Du sie festhältst, dann
muss alles davor und dahinter angepasst werden.
Die Umnummerierung vor und hinter der statischen Teilkette ist ein
Teilproblem, da Teilmenge des Ausgangsproblems.
Dieses Teilproblem hat nur eine Nebenbedingung: den Wert des ersten bzw
letzten Elements Deiner statischen Teilkette.
Das ganze ist nur so eine unausgegorene Idee von mir.
Suchst du einen Insertionsort? Für dein Problem müsstest du beim Insert
dann halt nicht verschieben, sondern nur einen freie Zwischennummer
finden (worst case musst du halt noch was verschieben, wenn keine frei
ist).
Gruß Kai
Peter M., herzlichen Dank dafür, dass du mein problem verstanden hast
:-)
Aber das ist vermutlich meine Schuld, ich habs unklar formuliert (ist
aber nicht ganz einfach das klar zu formulieren)
nehmen wir an ich hab eine Tabelle von Positionen, die einen Namen
haben, die Applikation schert sich aber nicht um den namen, sondern
zeigt die Positionen in der Reihenfoilge einer (internen, unsichtbaren)
Positionsnummer an. Ein kluger Nachtlauf hat das dann entsprechend
sortiert (Schrittweite 100)
100 "aa"
200 "bb"
300 "cc"
400 "dd"
500 "ee"
600 "ff"
jetzt kommt ein böster User und ändert den namen von "dd" auf "xx" und
"ee" auf "yy". Das angezeigte Ergebnis ist natürlich falsch:
100 "aa"
200 "bb"
300 "cc"
400 "xx"
500 "yy"
600 "ff"
aber ich werde angetriggert "hey, am Stücklistenkopf 4711 hat sich was
getan"
ich habe nun mehrere Möglichkeiten:
a) stures umnumerieren:
100 => 100 "aa"
200 => 200 "bb"
300 => 300 "cc"
600 => 400 "ff"
400 => 500 "xx"
500 => 600 "yy"
3 updates, Kosten = 3
b) 400 und 500 verschieben:
100 => 100 "aa"
200 => 100 "bb"
300 => 300 "cc"
600 => 600 "ff"
400 => 700 "xx"
500 => 800 "yy"
2 updates, Kosten = 2
6) 600 verschieben (WICHTIG! An 600 hat sich der Name NICHT geändert!!!)
100 => 100 "aa"
200 => 100 "bb"
300 => 300 "cc"
600 => 350 "ff"
400 => 400 "xx"
500 => 500 "yy"
1 update, Kosten = 1, billigste Variante
Kai,
bei Michael wird gar nichts sortiert.
Die Aufgabenstellung lässt sich verkürzen auf:
Gegeben sei ein Feld von n Zahlen.
Minimiere die Anzahl k<=n von Umbenennungen, so daß die neuen n Zahlen
aufsteigend sortiert sind.
Die naive Lösung lautet k=n, aber es kann bessere geben.
Wenn alle Zahlen absteigend verlaufen, ist k=n-1.
Jeweils rückwärts laufen lassen (im Beispiel von 60 nach 100):
MaxPos = z.B. 999
LOOP (pro StüLi rückwärts)
IF actual <= next
IF previous = 0
previous= max
actual = actual + INT(previous - next)/2
IF INT(previous - next)/2 <= 1
actual = next
next = actual - 1 (hier kann man beliebig optimieren, indem man
weiter
nach "vorne" schaut)
(UPDATE next) oder merken und ggf. "updaten"
UPDATE act
ENDLOOP
Peter M. schrieb:> Die Aufgabenstellung lässt sich verkürzen auf:>> Gegeben sei ein Feld von n Zahlen.>> Minimiere die Anzahl k<=n von Umbenennungen, so daß die neuen n Zahlen> aufsteigend sortiert sind.>> Die naive Lösung lautet k=n, aber es kann bessere geben.>> Wenn alle Zahlen absteigend verlaufen, ist k=n-1.
Danke :-) Wieso kann ich mich nicht so ausdrücken? (meine Ausrede ist:
Als wir das gelernt haben, war ich leider krank)
Michael,
Du verwirrst die Foristen, weil Du jetzt ein zusätzliches Problem
beschreibst, was Du ganz oben in Deinem Ausgangsbeitrag schon gelöst
hast.
Da hattest Du die Liste schon sortiert und das Problem bestand darin,
den Sortierschlüssel des Systems, die Positionsnummern anzupassen.
Jetzt schilderst Du auch noch das Vorproblem, aber das hast Du doch
schon gelöst?!
Zum Thema "ausdrücken":
Mein Studiengang wurde damals geschaffen, um von der einen "Sprache" in
die andere zu übersetzen und rückwärts. :)
Peter M. schrieb:> Da hattest Du die Liste schon sortiert und das Problem bestand darin,> den Sortierschlüssel des Systems, die Positionsnummern anzupassen.
Das ist immer noch so - unverändert, nur anders dargestellt.
Er hat zur Verdeutlichung lediglich einen dahinterliegenden
Sortierschlüssel angedeutet.
Peter M. schrieb:> Mein Studiengang wurde damals geschaffen, um von der einen "Sprache" in> die andere zu übersetzen und rückwärts. :)
Damm muss man beide Sprachen auch beherrschen ... :-)
Die relevanten Daten ins Memory. Dann dort sortieren, zB per Quicksort,
und dann einen algorithmus drueberlassen, der die minimal noetigen
Zugriffe rausfindet.
Und die dann auf der Datenbank ausfuehren.
Dieter F. schrieb:> Peter M. schrieb:>> Da hattest Du die Liste schon sortiert und das Problem bestand darin,>> den Sortierschlüssel des Systems, die Positionsnummern anzupassen.>> Das ist immer noch so - unverändert, nur anders dargestellt.> Er hat zur Verdeutlichung lediglich einen dahinterliegenden> Sortierschlüssel angedeutet.
Den Weg der Entstehung der Unordnung zu kennen ist bei der Beseitigung
dieser Unordnung nicht hilfreich, meine ich.
> Peter M. schrieb:>> Mein Studiengang wurde damals geschaffen, um von der einen "Sprache" in>> die andere zu übersetzen und rückwärts. :)>> Damm muss man beide Sprachen auch beherrschen ... :-)
Tue ich das nicht? Schade.
Trampel schrieb:> und dann einen algorithmus drueberlassen, der die minimal noetigen> Zugriffe rausfindet.
Loriot: Ach? :)
Und wie lautet der Algorithmus?
@Dieter:
Da beginnt die Verwirrung schon. Da fokussiert jemand auf das
Vorproblem.
Deswegen sollte man das Vorproblem aus didaktischen Gründen weglassen.
Und nein, ich bin kein Lehrer.
Peter M. schrieb:> Linear durchlaufen, Teilketten zählen und Kosten vergleichen:
[...]
> Die Umnummerierung vor und hinter der statischen Teilkette ist ein> Teilproblem, da Teilmenge des Ausgangsproblems.> Dieses Teilproblem hat nur eine Nebenbedingung: den Wert des ersten bzw> letzten Elements Deiner statischen Teilkette.>> Das ganze ist nur so eine unausgegorene Idee von mir.
Die Idee ist nicht übel, hat aber im Worst-Case auch unangenehme Kosten,
die man zumindest mal prüfen sollte: Die Teilaufgaben sind z.B. durch
Rekursion zu lösen. Bei Teilketten der Größe 1 (worst case) landen wir
dann bei O(n²) - und das ist bei Stücklisten der Größenordnung 10000
schon nicht mehr unbedingt zu vernachlässigen (sonst wären ja auch die
einsparbaren Update-Kosten irrelevant).
Michael R. schrieb:> Meine Aufgabe ist es, in einer Datenbank einen Bereich von Sätzen mit> einem "Sortierschlüssel" zu belegen bzw. zu aktualisieren, und das mit> so wenigen Updates wie möglich.
Früher (tm) hätte man einen Index zu dem Sortierfeld angelegt.
Heutzutage macht man sich das Leben lieber durch mangelnden Zugriff auf
die Applikation schwer - Denken in Systemen ohne Nachdenken.
Peter M. schrieb:> Tue ich das nicht? Schade.
Nur mein Eindruck :-)
Peter M. schrieb:> @Dieter:> Da beginnt die Verwirrung schon. Da fokussiert jemand auf das> Vorproblem.> Deswegen sollte man das Vorproblem aus didaktischen Gründen weglassen.> Und nein, ich bin kein Lehrer.
Was hat das hier mit Didaktik zu tun? Es geht um eine Problemlösung.
Ich habe eine aus meiner Sicht optimale Lösung gepostet - ohne
großartige Update-Kosten-Berechnungen etc.
Trampel schrieb:> und dann einen algorithmus drueberlassen, der die minimal noetigen> Zugriffe rausfindet.
Und genau dieser Algorithmus ist seit dem ersten Post gesucht, denke
ich.
Sorry, hab auch grad keinen zur Hand.
Meine erste Idee wäre in Richtung "Edit distance" zu suchen, da könnte
es relevante Optimierungsstrategien geben.
Evtl. per Backtracking, Liste von vorne durchgehen, und bei jeder Stelle
mit falscher Sortierung probieren, den aktuellen wert, den
Vorgänger-wert oder den Nachfolge-Wert anzupassen.
Ralf D. schrieb:> Die Idee ist nicht übel, hat aber im Worst-Case auch unangenehme Kosten,> die man zumindest mal prüfen sollte: Die Teilaufgaben sind z.B. durch> Rekursion zu lösen. Bei Teilketten der Größe 1 (worst case) landen wir> dann bei O(n²) - und das ist bei Stücklisten der Größenordnung 10000> schon nicht mehr unbedingt zu vernachlässigen (sonst wären ja auch die> einsparbaren Update-Kosten irrelevant).
Ja, leider!
Ich sehe aber nicht, dass man das Problem real halbieren könnte um z.B.
auf O(n*log(n)) zu kommen, weil die optimalen Ketten in die andere
Hälfte hineinragen könnten.
Hast Du denn eine Idee, die n^2 zu drücken?
Aber für Lesen der Positionsnummern aus der Datenbank, was man ja
einmalig in O(n) bewältigen kann und rechnen gibt es bisher keine
Kosten.
DB schrieb:> Früher (tm) hätte man einen Index zu dem Sortierfeld angelegt.
Der half aber auch nicht früher (tm) wie heute dabei, die möglichen
Updatens zur Neu-Numerierung zu minimieren.
Peter M. schrieb:> Michael,>> Du verwirrst die Foristen...
Ja, vermutlich, und vermutlich deswegen weil ich seit tagen darüber
grüble, und wie oben schon geschrieben etwas "hirntot" bin :-)
aber zurück zu deiner klaren Darstellung:
> Gegeben sei ein Feld von n Zahlen.> Minimiere die Anzahl k<=n von Umbenennungen, so daß die neuen n Zahlen> aufsteigend sortiert sind.
und um deine Idee zu verfeinern:
- unterteile die n Zahlen in m Gruppen, die in sich bereits korrekt
sortiert sind
- ist m=1 dann sind wir fertig
- suche die kleinste Gruppe (mit den wenigsten Elementen; wenn es
mehrere davon gibt, nimm irgendeine)
- verschiebe diese Gruppe an die richtige Position
- beginne von vorne
klingt für mich nach einem Plan :-)
Dieter F. schrieb:> Ich habe eine aus meiner Sicht optimale Lösung gepostet - ohne> großartige Update-Kosten-Berechnungen etc.
Ja aber die Update-Kosten-Berechnung bzw. Minimierung ist doch der Kern?
... sagt der Forist mit den Übersetzungsproblemen. :)
Peter M. schrieb:> Aber für Lesen der Positionsnummern aus der Datenbank, was man ja> einmalig in O(n) bewältigen kann und rechnen gibt es bisher keine> Kosten.
beides ist vernachlässigbar.
Die Fälle wo alle 10.000 Sätze aktualisiert werden müssen (weil alle mit
PosNr null kommen) sind äußerst rar bis nicht existent.
Kritisch sind wirklich nur Updates, weil die (tlw rekursiv) trigger
auslösen.
Aber vergessen wir die Datenbank, Peter M hat das Problem wunderbar
abstrahiert, wofür ich ihm schon unendlich dankbar bin!
Peter M. schrieb:> Ja aber die Update-Kosten-Berechnung bzw. Minimierung ist doch der Kern?>> ... sagt der Forist mit den Übersetzungsproblemen. :)
Minimieren tue ich ohne die Kosten zu berechnen - wozu auch?
Dieter F. schrieb:> Michael R. schrieb:>> - ist m=1 dann sind wir fertig>> Falsch - "ist m=n wäre" korrekt :-)
Nö - m=n hieße absteigend sortiert - es gibt m gruppen mit je einem
Element
m = 1 heisst es gibt nur eine Gruppe, die korrekt sortiert ist => habe
fertig
Michael R. schrieb:> und um deine Idee zu verfeinern:>> - unterteile die n Zahlen in m Gruppen, die in sich bereits korrekt> sortiert sind>> - ist m=1 dann sind wir fertig>> - suche die kleinste Gruppe (mit den wenigsten Elementen; wenn es> mehrere davon gibt, nimm irgendeine)>> - verschiebe diese Gruppe an die richtige Position>> - beginne von vorne>> klingt für mich nach einem Plan :-)
So findest Du eine Lösung, aber nicht die kostenminimale.
Du baust auf diese Art längere Ketten um sie hinterher doch noch alle
eventuell umbenennen zu müssen.
Beispiel:
451 400 453 499 457 498 201 202 203 204 205 206 207 208 209 210 211
Oder hat Deine Liste eine typische Struktur, die man ausnutzen kann?
Reicht dann eine Heuristik?
Dieter F. schrieb:> Minimieren tue ich ohne die Kosten zu berechnen - wozu auch?
Es gibt doch verschiedene Möglichkeiten, die unterschiedliche Kosten
verursachen und die billigste ist gesucht.
Was Du machst, ist wie ein Schachprogramm schreiben, nur ohne
Stellungsbewertung.
Michael R. schrieb:> - unterteile die n Zahlen in m Gruppen, die in sich bereits korrekt> sortiert sind>> - ist m=1 dann sind wir fertig
Ja, Du hast Recht - dann mach das mal so.
Wenn Du jetzt wieder nach Zahlen (Positionsnummern) sortierst, wie sieht
denn Dein Ergebnis dann aus?
100 => 100 "aa"
200 => 100 "bb"
300 => 300 "cc"
400 => 400 "xx"
500 => 500 "yy"
600 => 350 "ff"
So? Das wären dann 0 Updates - gratuliere - oder auch nicht.
Peter M. schrieb:> So findest Du eine Lösung, aber nicht die kostenminimale.
Hmmm... ich bin auch mit einem "lokalen Minimum" zufrieden. Alles ist
besser wie das was ich jetzt habe :-)
> Du baust auf diese Art längere Ketten um sie hinterher doch noch alle> eventuell umbenennen zu müssen.>> Beispiel:> 451 400 453 499 457 498 201 202 203 204 205 206 207 208 209 210 211>> Oder hat Deine Liste eine typische Struktur, die man ausnutzen kann?> Reicht dann eine Heuristik?
Nein, leider nicht.
mal nachdenken:
> 451 400 453 499 457 498 201 202 203 204 205 206 207 208 209 210 211
451
400
453 499
457 498
201 202 203 204 205 206 207 208 209 210 211
nimm 451
400 451 453 499 457 498 201 202 203 204 205 206 207 208 209 210 211
400 451 453 499
457 498
201 202 203 204 205 206 207 208 209 210 211
nimm 457 498
ah ja :-(
Peter M. schrieb:> Was Du machst, ist wie ein Schachprogramm schreiben, nur ohne> Stellungsbewertung.
Nö, was ich mache ist sortieren und "updaten" ohne "Humbug" :-)
Schach und Sortieren unterscheiden sich geringfügig - in etwa so wie
Deutsch und Finnisch :-)
Peter M. schrieb:> 451 400 453 499 457 498 201 202 203 204 205 206 207 208 209 210 211
Praxisnah ...
Michael R. schrieb:> Die Liste ist aber idR vorsortiert> in 100er Schritten, damit zwischen den Positionen genügend Platz ist, um> neue einzufügen (diese Vorsortierung erledigt ein Nachtlauf)
Ralf Döblitz wies oben auf die Komplexität meines Algorithmus hin.
Daher stellt sich die Frage: Wie groß ist Dein n?
Dann ist da auch die Frage der "Auslastung" des Zahlenraums:
Wie verhält sich n zur maximalen Größe Deines Integer-Schlüssels?
Nutzt die Ausgangsnumerierung vor "Störung" die Breite des
Integer-Schlüssels aus?
Im schlimmsten Fall läst sich ein Teilproblem nicht lösen, weil Du keine
60 Positionen mit eindeutigen positiven Nummern <50 versehen kannst.
Dann musst Du doch Zahlen umbenennen, nur um Platz zu schaffen!
Peter M. schrieb:> Ralf Döblitz wies oben auf die Komplexität meines Algorithmus hin.>> Daher stellt sich die Frage: Wie groß ist Dein n?
zwischen 1 und etwa 10.000
> Dann ist da auch die Frage der "Auslastung" des Zahlenraums:>> Wie verhält sich n zur maximalen Größe Deines Integer-Schlüssels?
10.000 zu 2^32
> Nutzt die Ausgangsnumerierung vor "Störung" die Breite des> Integer-Schlüssels aus?
(noch) nicht wirklich
> Im schlimmsten Fall läst sich ein Teilproblem nicht lösen, weil Du keine> 60 Positionen mit eindeutigen positiven Nummern <50 versehen kannst.> Dann musst Du doch Zahlen umbenennen, nur um Platz zu schaffen!
Ja, das ist mir klar. Das kann ich aber durch (fast beliebiges)
vergrößern der Vorsortierung steuern (wobei Schrittweite 100 ausreichend
sein sollte), die wenigen Fälle wo das nicht mehr ausreicht, verkrafte
ich.
Sobald ich mal eine konkrete Idee vom Algorithmus habe, kann ich
Randbedingungen schaffen, bzw. durch Beobachtung anpassen.
Schlimmer als O(n) kanns ja nicht werden :-)
Peter M. schrieb:> Ralf D. schrieb:>>> Die Idee ist nicht übel, hat aber im Worst-Case auch unangenehme Kosten,>> die man zumindest mal prüfen sollte: Die Teilaufgaben sind z.B. durch>> Rekursion zu lösen. Bei Teilketten der Größe 1 (worst case) landen wir>> dann bei O(n²) - und das ist bei Stücklisten der Größenordnung 10000>> schon nicht mehr unbedingt zu vernachlässigen (sonst wären ja auch die>> einsparbaren Update-Kosten irrelevant).>> Ja, leider!> Ich sehe aber nicht, dass man das Problem real halbieren könnte um z.B.> auf O(n*log(n)) zu kommen, weil die optimalen Ketten in die andere> Hälfte hineinragen könnten.> Hast Du denn eine Idee, die n^2 zu drücken?
Nein, leider nicht. Evtl. gibt es da irgendwo min der Literatur ganz
tolle Algorithmen, aber auch da muß man immer genau hinsehen, wie sie
sich im worst case verhalten (was ja auch bei Quicksort dann O(n²) ist).
> Aber für Lesen der Positionsnummern aus der Datenbank, was man ja> einmalig in O(n) bewältigen kann und rechnen gibt es bisher keine> Kosten.
IMHO muß man das einfach mal praktisch ausprobieren. Vermutlich wird das
auch noch kein Problem darstellen, die Trigger und evtl. daraus
resultierende Subqueries oder Updates (I/O kostet halt) dürften deutlich
teurer sein.
Alternativ würde ich die Tabelle splitten, so daß die Updates nur eine
kleine Sortier-Hilfstabelle mit PKey und Sortkey treffen, die
eigentliche Tabelle (die dann keinen Sortkey mehr hat) aber unberührt
läßt. Wenn man die iegentliche App nicht anpassen kann, dann würde ich
der einen passenden View gegen und die "normalen" Updates über einen
Trigger laufen lassen. Das gibt zwar auch Overhead, die Kosten müßte man
halt abwägen. Das einfachste (wenn man denn ran kommt bzw. darf) wäre
aber einfach die Trigger-Bedingungen anzupassen, so daß die nicht
unnötig feuern, wenn man nur den Sortkey ändert.
Aber man sollte halt die quadratische Abhängigkeit dokumentieren, damit
niemand später böse reinfällt, wenn die Liste doch mal um Faktor 10
wächst.
BTST: ein Kollege hat immer schön mit kleinem Testdatensatz entwickelt,
die realen Daten waren Faktor 30 größer, das Programm war zäh, aber noch
gerade erträglich. Weiteres Wachstum um Faktor 4 und es es gab großes
Fluchen - O(n³) war da richtig schmerzhaft ... Und es dürfen ja auch
andere Leute aus unseren Fehlern lernen. ;-)
OK,
ich glaube ich habe einen Algorithmus der dem Vorschlag von Peter M.
entspricht, aber keine explizite Kostenmetrik erfordert.
Der Algorithmus geht davon aus, dass die komplette "Sortierung" im
Speicher stattfinden kann.
Gegeben ist die bisherige (richtig sortierte) Folge:
1: 10
2: 20
3: 30
4: 400
5: 500
6: 60
bestehend aus "Postition" und "Positionsnummer". Lade die in den
Speicher.
So, wir brauchen mehrere Schritte.
1. Suche nach dem längsten RUN.
Ein RUN ist eine Teilfolge mit streng monoton steigenden
Positionsnummern.
Du hattest ja selbst schon erkannt, dass du die schon richtig sortierten
Teilfolgen irgendwie berücksichtigen musst.
Interressant ist aber eigentlich nur die längste. Sollte es mehrere
gleich lange geben, nimm die erste.
Die Datensätze innerhalb dieses RUNs sind fertig und müssen nicht
verändert werden.
Neu nummeriert werden müssen alle Datensätze vor und nach diesem Run.
2. neu durchnummerieren der Datensätze vor dem RUN.
An Positionsnummern hast du den Zahlenraum zwischen 1 und der
Positionsnummer vom Start deines RUNs (=A) zur Verfügung und du musst n
Datensätze umnummerieren. Wenn n>A-1 geht das natürlich nicht -->
komplett neu sortieren.
Verteile die neuen Positionsnummern gleichmäßig im Abstand (A-1) /
(n+1), damit zukünftige Sortierläufe vielleicht noch Luft finden.
3. neu durchnummerieren der Datensätze nach dem RUN.
Das ist jetz mit den Positionsnummern einfach, du kannst das ja wie
bisher in hunderter-Schritten (beginnend am Ende deines Runs) machen.
Den Zahlenraum ganz auszunutzen wurde ja schon vorgeschlagen.
Bis auf den Fall der vollständigen Neusortierung (der deiner Meinung
nach ja tragbar ist, weil er selten vorkommt) ist dieser Algorithmus
meiner Meinung nach optimal, da er eben mit dem Minimum
Schreiboperationen auskommt.
Michael R. schrieb:> c.m. schrieb:>> sicher das du kein konsistenzproblem bekommen kannst, wenn ein prozess>> die ID's umordnet während evtl. ein anderer grade welche selektiert hat>> und sich drauf verlässt das hinter ID(x) datensatz(y) steckt?>> Ja. D Die posNr ist keine Id, nur ein Display-Sort-Hint.>> Könnts ihr euch bitte vom DB-Hintergrund lösen, und versuchen das> problem an sich zu abstrahieren? :-)
es ist doch aber ein DB spezifisches problem.
du willst einfach nicht tausende rows updaten bei einem insert. willst
du nicht.
wie wärs wenn du die applikation auf eine view zugreifen lässt anstatt
auf die tabelle? in der view wäre dann der passende order-by select, und
ideralerweise auf der quelltabelle ein passender index.
wenn du es nicht ideal, also in der abfragen applikation, machen kannst,
musst du krücken bauen - und das kostet an irgend einer stelle.
rechenzeit, IO, speicher, whatever.
Michael R. schrieb:>> Wie verhält sich n zur maximalen Größe Deines Integer-Schlüssels?>> 10.000 zu 2^32
Naja, vermutlich hast du als maxint eher 2^31 zur Verfügung.
>> Nutzt die Ausgangsnumerierung vor "Störung" die Breite des>> Integer-Schlüssels aus?>> (noch) nicht wirklich
16384 wäre 2^14, das wäre eine Abschätzung nach oben für n
>> Im schlimmsten Fall läst sich ein Teilproblem nicht lösen, weil Du keine>> 60 Positionen mit eindeutigen positiven Nummern <50 versehen kannst.>> Dann musst Du doch Zahlen umbenennen, nur um Platz zu schaffen!>> Ja, das ist mir klar. Das kann ich aber durch (fast beliebiges)> vergrößern der Vorsortierung steuern (wobei Schrittweite 100 ausreichend> sein sollte), die wenigen Fälle wo das nicht mehr ausreicht, verkrafte> ich.
Wenn du die Vorsortierung mit Abstand 2^15 machst (32768), dann solltest
du immer in der Lage sein, alle Elemente zwischen zwei beliebige zu
verschieben. Selbst wenn deine Listen noch um Faktor 3 anwachsen.
> Sobald ich mal eine konkrete Idee vom Algorithmus habe, kann ich> Randbedingungen schaffen, bzw. durch Beobachtung anpassen.
Einfach mal ausprobieren (mit künstlich erzeugten Testdatensätzen),
dabei dann das Kostenverhältnis Update vs. Aufwandsberechnung bestimmen.
Dann kannst du auch für die Optimierung einen Grenzwert setzen, bei dem
du einfach die Suche abbrichst und die bis dahin beste gefundene Lösung
nimmst (geht dann in Richtung Evolutionsstrategien/genetische
Algorithmen). Ist ein wenig aufwändiger zu programmieren, erlaubt dir
aber, den worst case des rekursiven Algorithmus zu ignorieren.
Tilo R. schrieb:> Du hattest ja selbst schon erkannt, dass du die schon richtig sortierten> Teilfolgen irgendwie berücksichtigen musst.> Interressant ist aber eigentlich nur die längste. Sollte es mehrere> gleich lange geben, nimm die erste.
Interessant ... in der Tat
Michael R. schrieb:> - unterteile die n Zahlen in m Gruppen, die in sich bereits korrekt> sortiert sind> - suche die kleinste Gruppe (mit den wenigsten Elementen; wenn es> mehrere davon gibt, nimm irgendeine)
Was denn nun?
Tilo R. schrieb:> 2. neu durchnummerieren der Datensätze vor dem RUN.
Hmm, das bedeutet wohl heftige (unberechnete!) Updates ...
Tilo R. schrieb:> 3. neu durchnummerieren der Datensätze nach dem RUN.
Uiuiui ... dto.
Tilo R. schrieb:> is auf den Fall der vollständigen Neusortierung (der deiner Meinung> nach ja tragbar ist, weil er selten vorkommt) ist dieser Algorithmus> meiner Meinung nach optimal, da er eben mit dem Minimum> Schreiboperationen auskommt.
Vielleicht findet Peter ja eine geeignete Formel dazu? Irgendwie sollte
das zu Übersetzen sein.
c.m. schrieb:> wie wärs wenn du die applikation auf eine view zugreifen lässt anstatt> auf die tabelle? in der view wäre dann der passende order-by select, und> ideralerweise auf der quelltabelle ein passender index.>> wenn du es nicht ideal, also in der abfragen applikation, machen kannst,> musst du krücken bauen - und das kostet an irgend einer stelle.> rechenzeit, IO, speicher, whatever.
Wie wärs, wenn Du mal nachdenkst, bevor Du irgendetwas von Dir gibst?
:-)
Ralf D. schrieb:> Einfach mal ausprobieren (mit künstlich erzeugten Testdatensätzen),> dabei dann das Kostenverhältnis Update vs. Aufwandsberechnung bestimmen.> Dann kannst du auch für die Optimierung einen Grenzwert setzen, bei dem> du einfach die Suche abbrichst und die bis dahin beste gefundene Lösung> nimmst (geht dann in Richtung Evolutionsstrategien/genetische> Algorithmen). Ist ein wenig aufwändiger zu programmieren, erlaubt dir> aber, den worst case des rekursiven Algorithmus zu ignorieren.
Ja, Sortierung - das ist ein klassischer Ansatz für KI. Warum bin ich
denn nicht darauf gekommen?
Ich bin müde und gebe auf. Wenn ich so wie die "Profis" hier an meine
täglichen Probleme herangehen würde wäre ich heute wahrscheinlich
"Hoffürst" und würde für die Sauberkeit im Innenhof und den Lagerhallen
sorgen.
GsD ist es anders und ich widme mich täglich neuen, spannenden Aufgaben
(fast immer ...).
Dieter F. schrieb:> Ralf D. schrieb:>> Einfach mal ausprobieren (mit künstlich erzeugten Testdatensätzen),>> dabei dann das Kostenverhältnis Update vs. Aufwandsberechnung bestimmen.>> Dann kannst du auch für die Optimierung einen Grenzwert setzen, bei dem>> du einfach die Suche abbrichst und die bis dahin beste gefundene Lösung>> nimmst (geht dann in Richtung Evolutionsstrategien/genetische>> Algorithmen). Ist ein wenig aufwändiger zu programmieren, erlaubt dir>> aber, den worst case des rekursiven Algorithmus zu ignorieren.>> Ja, Sortierung - das ist ein klassischer Ansatz für KI. Warum bin ich> denn nicht darauf gekommen?
Ich weiß nicht, wieso du da jetzt KI reinbringst. Evolutionsstrategien
und genetische Algorithmen sind übliche Methoden für
Optimierungsprobleme, die nicht (einfach genug) analytisch lösbar sind.
Kannst du mir ruhig glauben, ich habe darüber meine Studienarbeit
geschrieben. ;-)
Ok, das ist ein spannendes Problem.
Darf ich die Frage neu formulieren, um sicher zu gehen, dass ich da
nichts übersehen habe?
Fragestellung:
Gegeben ist ein Array aus Positionsnummern.
Die Reihenfolge ist so, dass zu den Positionsnummern dazugehörige
Datensätze einer vorgegebenen (unbekannten) Ordnung entsprechen.
Beispiel:
10
20
30
400
500
60
I.d. Regel ist zwischen den Positionsnummern "Luft" (100, 200, 300,...)
Die Anzahl der Datensätze ist fünfstellig (~10k).
Die Positionsnummern der Datensätze können geändert werden.
Gesucht ist ein Algorithmus, der die Positionsnummern so ändert, dass
die natürliche Ordnung der Positionsnummern der vorgegebenen Ordnung der
Datensätze entspricht.
Dabei sollen so wenig Positionsnummern geändert werden wie möglich.
Eine Lösung für das oben gegebene Array wäre:
10
20
30
400
500
60 --> 600
Ich melde mich morgen abend nochmal.
ps. für alle die solche Probleme spannend finden:
https://projecteuler.net
Ich habe dafür leider nicht mehr so viel Zeit und dümple seit Ewigkeiten
auf Level 4.
Dieter F. schrieb:> c.m. schrieb:>> wie wärs wenn du die applikation auf eine view zugreifen lässt anstatt>> auf die tabelle? in der view wäre dann der passende order-by select, und>> ideralerweise auf der quelltabelle ein passender index.>>>> wenn du es nicht ideal, also in der abfragen applikation, machen kannst,>> musst du krücken bauen - und das kostet an irgend einer stelle.>> rechenzeit, IO, speicher, whatever.>> Wie wärs, wenn Du mal nachdenkst, bevor Du irgendetwas von Dir gibst?> :-)
erläutere.
Michael R. schrieb:> Schlimmer als O(n) kanns ja nicht werden :-)
O(n) reicht gerade mal zum Angucken.
Das wird teurer!
Auf jeden Fall solltest Du die Vornumerierung nach Abschätzung von Ralf
vornehmen um zusätzliche Kosten für Umnumerierung zu vermeiden.
Ich würde folgendes erst einmal "den Wald lichten" und das Problem im
Umfang reduzieren.
Bau Dir ein dynamische Feld von Trippeln, die die erste Zahl eines Runs,
die letzte Zahl eines Runs und die Anzahl Elemente dieses RUNs angibt.
Der Aufbau kostet Dich schlimmstenfalls n RUNs der Länge 1 die Du in ein
dynamisches wachsendes Feld einsortieren musst, kostet dann O(nlog(n)).
Dann zeig' uns im nächsten Schritt mal ein Verteildiagramm das zu jeder
RUNlänge die Häufigkeit angibt.
Die Intervalle für die Häufigkeiten kannst Du folgendermaßen wählen:
1. Intervall: Run's mit maximaler Länge 2^0
2. Intervall: Run's mit maximaler Länge 2^1
3. Intervall: Run's mit maximaler Länge 2^2
log2(n). Intervall: Run's mit maximaler Länge 2^(log2(n))
Vielleicht zeigt uns das irgendwas schickes?
Allen Datenbankfreaks sei gesagt, dass es für den Algorithmus egal ist,
ob der Inhalt von Schuhkartons verändert wird, Flugzeuge in andere
Hangars gesteckt werden oder einmal Anfassen einen Mondflug bedeutet.
Alle drei Beispiele kosten Geld, egal wie sehr man die teuren Vorgänge
auch optimiert, bzw. verbilligt.
Das ändert nichts an der Tatsache, dass man kostenträchtige
Elementaroperation betreiben muss, deren Anzahl man aber minimieren
will.
@Tilo:
Den längsten RUN beibehalten zu wollen, gefällt mir als heuristischen
Ansatz am besten. Deswegen habe ich Michael auch nach der obigen Tabelle
bzw. dem Verteilungsdiagramm gefragt. Wenn es da richtig lange
Bandwürmer gibt, muss nicht mehr so viel verändert werden.
Ich finde die Namensgebung RUN richtig gut wegen der Analogie zur
Clusterdarstellung beim Wechsel vom Dateisystem ext3 auf ext4.
Michael R. schrieb:>> Daher stellt sich die Frage: Wie groß ist Dein n?> zwischen 1 und etwa 10.000
Und wie lange darf der Algorithmus auf einem üblichen PC maximal laufen?
Da n nach oben beschränkt ist, spielt die Komplexität des Algorithmus
(in O(...) ausgedrückt) keine Rolle, solange die maximal erlaubte
Laufzeit nicht überschritten wird. Somit kann selbst ein Algorithmus mit
O(n²) durchaus akzeptabel sein, und vielleicht ist sogar einer mit O(n³)
noch schneller.
Dieter F. schrieb:> Wenn Du jetzt wieder nach Zahlen (Positionsnummern) sortierst, wie sieht> denn Dein Ergebnis dann aus?>> 100 => 100 "aa"> 200 => 200 "bb"> 300 => 300 "cc"> 400 => 400 "xx"> 500 => 500 "yy"> 600 => 350 "ff">> So? Das wären dann 0 Updates - gratuliere - oder auch nicht.
Genau das habe ich gemeint.
Zusätzlich in Zeiten geringer Auslastung einen Cronjob laufen lassen,
der für gleichmäßige Abstände sorgt. Der Sorgt dann dafür, dass man
genug Lücken zum Einsortieren hat.
Guten Morgen allerseits!
erstmal herzlichen Dank an alle hier, ihr habts mir schon super
weitergeholfen! ich freue mich, ein offensichtlich wirklich spannendes
Problem auf den Tisch gelegt zu haben (wenn auch mit
Startschwierigkeiten :-)
zur Häufigkeitsverteilung: wie die "gestörten" Listen aussehen, kann ich
schwer sagen, da ich ja (durch den Nachtlauf) immer vorsortierte,
saubere Listen habe. Aber zur Länge der Listen kann ich was sagen:
1-9 2244
10-99 829
100-999 265
>=1000 26
die längste Liste hat ~3.000 Elemente, mein "10.000" war wohl etwas zu
hoch gegriffen. Man darf sich aber nicht täuschen lassen: Die langen
listen sind auch die aktiveren, dort erfolgen auch gehäuft Änderungen!
Die Idee mit den RUNs gefällt mir ausgezeichnet! Allerdings ist es nicht
ganz trivial...
den "längsten" RUN zu finden und unverändert zu lassen, führt nicht zum
optimalen Ergebnis:
10 20 30 400 50 60: längster RUN 10-20-30-400, allerdings ist 400 der
"Störer"
außerdem kann es passieren, dass durch einen Störer in der Mitte zwei
(fast) gleich lange RUNs entstehen, der zweite sollte natürlich auch
berücksichtigt werden. Wobei ich wieder bei "arbeite mit dem kürzesten"
wäre...
Momentan habe ich einen Prototyp am laufen, der erstmal gar nicht so
schlecht aussieht, auch wenn er ziemlich mit "brute force" arbeitet.
es funktioniert in etwa so:
- ersetze alle mittigen Elemente, die links ein kleineres und rechts ein
größeres Element haben, durch "dont care"
10 20 30 400 50 60 => 10 xx xx 400 50 60
(kann man auch so sehen, dass ich Gruppen bilde, und innere Elemente der
Gruppe nicht betrachte)
- ersetze reihum jedes Element durch "dont care" und prüfe ob die Liste
dann sortiert ist:
yy xx xx 400 50 60 => falsch
10 xx xx yyy 50 60 => richtig!
10 xx xx 400 yy 60 => falsch
10 xx xx 400 50 yy => falsch
Wenn eine "richtige" Lösung dabei ist, merke dir diese, zusammen mit der
Suchtiefe
andernfalls führe obige Schritte rekursiv auf; allerdings nicht tiefer
als mit der bisherigen "besten Suchtiefe"
das sollte ein brauchbares Ergebnis liefern, unter Ausnützung der
Tatsache dass die Listen weitgehend vorsortiert sind, und es nur wenige
"Störer" gibt.
Aber ich muss das natürlich noch intensiver testen...
Michael R. schrieb:> Die Idee mit den RUNs gefällt mir ausgezeichnet! Allerdings> ist es nicht ganz trivial...>> den "längsten" RUN zu finden und unverändert zu lassen, führt> nicht zum optimalen Ergebnis:
Ja...nee... ist das falsche Kriterium.
> 10 20 30 400 50 60: längster RUN 10-20-30-400, allerdings> ist 400 der "Störer"
Ja.
Fuer 50 und 60 gilt ja wieder 50 < 60; das ist also ein neuer
Run (bzw. dessen Beginn).
Der interessante Punkt ist also: Wie weit muss ich vom Beginn
des neuen Runs (50) zurueckgehen, damit der neue und der
Anfangsteil des alten Runs einen noch laengeren Run ergeben?
Die Antwort in Deinem Beispiel ist: Man muss nur die 400
streichen. Bei 10 20 380 400 50 60 kaeme heraus, dass man
von der 50 rueckwaerts gehend die 400 und die 380 streichen
muesste, damit der lange Run 10 20 xx yy 50 60 zu Stande kommt.
> außerdem kann es passieren, dass durch einen Störer in der> Mitte zwei (fast) gleich lange RUNs entstehen, der zweite> sollte natürlich auch berücksichtigt werden.
Ja.
Der Punkt ist: Durch die Monotoniebedingung findest Du die Runs,
aber die Runs muessen nicht mit den Teilfolgen identisch sein,
die Du suchst, sondern sie enthalten die Teilfolgen nur.
Vielleicht hilft es weiter, wenn Du Dir jeden Run aus einem
Praefix, einer Kernfolge und einem Suffix zusammengesetzt
vorstellst. Die Kernfolgen ergeben zusammen wieder einen
langen Run, Praefix und Suffix sind die Kandidaten fuer die
Stoerer.
Nachdem Du Die Runs gefunden hast, muesstest Du die Idee,
Nachbarn zu betrachten, eine Etage hoeher aufgreifen und
schauen, ob man durch Vergleich mit dem Nachbarrun die
Grenze von Praefix, Kernfolge und Suffix findet.
> Wobei ich wieder bei "arbeite mit dem kürzesten" wäre...
???
ich war jetzt 3 Stunden im Auto, hatte also genügend zeit zum
nachdenken, und bin draufgekommen dass mein obiger "brute Force Ansatz"
Blödsinn ist. Bitte ignorieren :-)
Moin,
zuerst mal muss ich mich entschuldigen - ich lag schief (meine Lösung
funktioniert nur für einzelne, eingeschobene Elemente) und hatte dazu
noch einen schlechten Tag. Sorry ...
Ich habe die "Gruppierungslösung" nochmal durchdacht. Diese scheint mir
(aus heutiger Sicht :-) ) optimal.
Zunächst werden alle Numerierungs-Gruppen (in sich aufsteigend passend)
gesucht und markiert.
Dann werden aufsteigend Fehl-Numerierungs-Gruppen ermittelt. Beginnend
mit der ersten Gruppe werden aufsteigend alle Gruppen mit allen jeweils
folgenden – bis dahin noch fehlerfreien – Gruppen verglichen (höchste
Nummer der aktuellen Gruppe mit kleinster Nummer der Vergleichs-
Gruppe). Zeigt der Vergleich einen Fehler auf, so wird die Gruppe mit
den wenigsten Elementen als fehlerhaft markiert. Sind beide Gruppen
gleich groß, so wird die 2. Gruppe als fehlerhaft markiert. Ausnahme:
Wenn eine der gleich großen Gruppen die "Start-Gruppe" (1. Gruppe
überhaupt) ist, wird diese (1. Gruppe) als fehlerhaft markiert.
Sind alle fehlerhaften Gruppen gefunden kann numeriert werden.
Zunächst sollte nach Möglichkeit durch einfaches Tauschen der gefundenen
Fehl-Numerierungsgruppen miteinander die Numerierung der gefundenen
Gruppen korrigiert werden (nur bei gleichen Gruppengrößen). Da wo es
nicht passt die jeweilige Gruppe neu verteilt im Intervall zwischen den
angrenzenden Gruppen durchnumerieren. Reicht das Intervall nicht aus,
wird so lange von der Folge-Gruppe "geborgt"/integriert bis alles neu
numeriert ist. Nur unschön, wenn eine große Gruppe mit einer kleinen
Start-Nummer weit im oberen Bereich kommt ...
Dein Beispiel:
10 20 30 400 50 60 ->
10 20 30 400 50 60
10 20 30 xxx 50 60
400 ist die welche nicht in die Numerierung passt. Es gibt nur eine,
kein Austausch möglich. Wird im Intervall zwischen 30 und 50 neu mit 40
(gleichverteilt, es gibt nur einen Wert) numeriert.
Willkürlich anders:
60 20 30 40 50 10 ->
60 20 30 40 50 10
xx 20 30 40 50 xx - Tausch möglich
Extremfall:
40 50 60 10 20 30
40 50 60 10 20 30
40 50 60 xx xx xx - neu numerieren
Noch extremer:
40 50 30 60 10 20
40 50 30 60 10 20
40 50 xx xx xx xx - neu numerieren, Tausch nicht sinnvoll
Bis jetzt passt es gedanklich bei jedem Beispiel – auch hier:
451 400 453 499 457 498 201 202 203 204 205 206 207 208 209 210 211 ->
451 400 453 499 457 498 201 202 203 204 205 206 207 208 209 210
211
xxx xxx xxx xxx xxx xxx 201 202 203 204 205 206 207 208 209 210
211 - neu numerieren
Possetitjel schrieb:>> Wobei ich wieder bei "arbeite mit dem kürzesten" wäre...>> ???
Er meint, er fängt mit den kürzesten Runs an. Das war seine
Ausgangsstrategie, siehe oben.
Michael R. schrieb:> zur Häufigkeitsverteilung: wie die "gestörten" Listen aussehen, kann ich> schwer sagen, da ich ja (durch den Nachtlauf) immer vorsortierte,> saubere Listen habe. Aber zur Länge der Listen kann ich was sagen:>> 1-9 2244> 10-99 829> 100-999 265>>=1000 26>> die längste Liste hat ~3.000 Elemente, mein "10.000" war wohl etwas zu> hoch gegriffen. Man darf sich aber nicht täuschen lassen: Die langen> listen sind auch die aktiveren, dort erfolgen auch gehäuft Änderungen!
Danke für die Information, die Längenstatistik über die Listen der
Vergangenheit ist zwar auch interessant, aber ich wollte die inneren
Information einfach zu EINER ausgewählten Liste, die Du mit dem
Algorithmus bearbeiten musst.
> Die Idee mit den RUNs gefällt mir ausgezeichnet! Allerdings ist es nicht> ganz trivial...>> den "längsten" RUN zu finden und unverändert zu lassen, führt nicht zum> optimalen Ergebnis:
Deswegen habe ich auch nach der Auswertung innerhalb einer Tagesliste
gefragt.
Behauptung
Wenn Du nämlich eine Liste hast, deren längster Run größer oder gleich
aufgerundet(n/2) ist, weißt Du, dass es keine bessere Lösung geben kann,
als den Run zu behalten, weil das Verwerfen dieses Runs dazu führt, dass
Du IMMER mehr Anpassungen hast, als wenn Du den Rest reparierst.
Beweis
Verwerfen des ersten Runs bedeutet minimale Kosten von aufgerundet(n/2),
Behalten des ersten Runs bedeutet "nur die Restliste anpassen", bedeutet
maximale Kosten von
länge(Restliste)=
anzahl(alle Elemente)-länge(längster Run)=
n-aufgerundet(n/2)=
abgerundet(n/2)
Des Weiteren fiel mir noch folgendes ein.
Bitte denk mal über die Länge verbundener Runs nach.
Ein verbundener Run besteht aus einzelnen Runs, die alle aufsteigend
sortiert sind.
Meine obige Behauptung gilt auch für verbundene Runs.
Beispiel: Länge=15
100 200 300 400 500 6 7 8 9 10 11 600 700 800 12
Runs:
1. 100 200 300 400 500 (5)
2. 6 7 8 9 10 11 (6)
3. 600 700 800(2)
4. 12 (1)
Verbundene Runs:
1. 100 200 300 400 500 600 700 800 (8)
2. 6 7 8 9 10 11 12 (7)
Betrachtest Du nur die längsten Runs, liegt es nahe den zweiten Run mit
6 Elementen zu behalten.
Ein Blick auf die verbundenen Runs zeigt aber, dass der erste Run zu
einem verbundenen Run gehört, der >= aufgerundet(n/2) =
aufgerundet(15/2)= aufgerundet(7,5)=8 ist.
Wie ich oben gezeigt habe, ist ein verbundener Run mit dieser
Mindestlänge Bestandteil der optimalen Lösung.
Du hast es zwar nicht explizit gesagt, aber ich unterstelle, dass
tagsüber jemand einzelne Listenstörungen verursacht.
Solche Störungen erzeugen zwar mehr Runs, aber sie verkleinern die
verbundenen Runs nicht.
Peter M. schrieb:> Verbundene Runs:> 1. 100 200 300 400 500 600 700 800 (8)> 2. 6 7 8 9 10 11 12 (7)
Hmmm...
eigentlich ist alles ein verbundener Run, es könnte ja auch
6 7 8 9 10 11 12 100 200 300 400 500 600 700 800 sein
oder müsst Runs schon in der richtigen Reihenfolge vorliegen, um sie als
"verbunden" zu betrachten?
über den Rest muss ich heut abend erst nachdenken...
Michael R. schrieb:> eigentlich ist alles ein verbundener Run, es könnte ja auch>> 6 7 8 9 10 11 12 100 200 300 400 500 600 700 800 sein
Hier gibt es keinen Bruch. Das ist ein RUN, der genau Null Anpassungen
benötigt.
>> oder müsst Runs schon in der richtigen Reihenfolge vorliegen, um sie als> "verbunden" zu betrachten?
Ich schrieb dazu oben:
Ein verbundener Run besteht aus einzelnen Runs, die alle aufsteigend
sortiert sind.
Dieter F. schrieb:> 10 20 30 400 50 60
ich muss gestehen, ich hab deine Beschreibung noch nicht wirklich
verstanden (aber ich arbeite dran)
ABER: wieso sind die 400 oben in einer eigenen Gruppe?
Michael R. schrieb:> Dieter F. schrieb:>> 10 20 30 400 50 60>> ich muss gestehen, ich hab deine Beschreibung noch nicht wirklich> verstanden (aber ich arbeite dran)>> ABER: wieso sind die 400 oben in einer eigenen Gruppe?
Das ist Dieters Beispiel.
Nach meiner Logik wäre das
1. Run: 10 20 30 400 (4)
2. Run: 50 60 (2)
null verbundene Run's
Aber dieses Beispiel wiederlegt meine Überlegung von oben zur optimalen
Lösung!
Ich habe dabei unterstellt, dass immer alle Mitglieder eines Runs
angefasst werden müssen.
Nach meiner Logik gehört der 1. Run mit 4>= aufgerundet(6/2)=3 zur
optimalen Lösung, was anfassen von 50 und 60 mit Kosten=2 bedeutet.
Das stimmt aber nicht!
Optimal ist nur die 400 anzufassen (Kosten=1).
Damit habe ich mich selbst wiederlegt. Mist. :(
Peter M. schrieb:> Damit habe ich mich selbst widerlegt. Mist. :(
Passiert mir auch dauernd, wenn dich das tröstet :-)
Aber ich hab da auch ein gemeines beispiel gemacht (auch wenn es
vielleicht in der Praxis selten vorkommt)
Man kann es sogar noch gemeiner machen, indem man die ins Auge
springende 400 ersetzt (die führt einen nämlich gern auf die falsche
Fährte)
10 20 30 40 35 37
Michael R. schrieb:> Peter M. schrieb:>> Damit habe ich mich selbst widerlegt. Mist. :(>> Passiert mir auch dauernd, wenn dich das tröstet :-)
Ja, danke!
Neue Idee:
Prüfe, wie sich die Runs verlängern, wenn man einen Wert an der
Bruchgrenze verändert
Prüfe, wie sich die Runs verlängern, wenn man zwei Werte an der
Bruchgrenze verändert
...
Führe die Operation durch, die die höchste Reparatureffizenz hat:
Effizienz=(RUN-Verlängerung)/Kosten
Peter M. schrieb:> Führe die Operation durch, die die höchste Reparatureffizenz hat:
ich denke eh gerade über eine vorerst einfache Suche nach lokalen Minima
nach. Einfach mal durchprobieren, und gewichten. Gewichten heisst aber
auch, eine gewichtungsfunktion zu haben. Anzahl Gruppen reduzieren ist
klar, aber wenn sich die nicht ändert... längsten Run verlängern?
Ich bin
Michael R. schrieb:> auch, eine gewichtungsfunktion zu haben. Anzahl Gruppen reduzieren ist> klar, aber wenn sich die nicht ändert... längsten Run verlängern?
Die Anzahl der Gruppen vermindert sich schon, allerdings zu steigenden
Kosten bei meiner letzten Idee.
Michael R. schrieb:> ABER: wieso sind die 400 oben in einer eigenen Gruppe?
Uuups, vertan - richtig wäre
10 20 30 400 50 60 ->
10 20 30 400 50 60
10 20 30 400 xx xx
und damit nicht optimal :-(
So, ich glaube ich habe eine tolle Lösung.
Anbei ein bischen Java-Code, der bei N=3000 mit komplett zufälligen
Positionsnummern in wenigen Sekunden ein optimales Ergebnis findet.
Ich habe auch ein paar andere lustige Testcases:
A:
10 20 30 400 500 60
den kennen wir alle schon
B:
10 40 11 50 60 20
Da reicht der Platz zwischen 10 und 11 nicht
C:
10 20 30 40 15 17 25 27 35 37
Hier wird der Solver verleitet, die vordere Folge (10 20 30 40) zu
nehmen.
Ich versuche im nächsten Post zu beschreiben was die Idee meines Codes
ist.
Tilo R. schrieb:> A:> 10 20 30 400 500 60> den kennen wir alle schon>> B:> 10 40 11 50 60 20> Da reicht der Platz zwischen 10 und 11 nicht>> C:> 10 20 30 40 15 17 25 27 35 37> Hier wird der Solver verleitet, die vordere Folge (10 20 30 40) zu> nehmen.
Nachstehend mit dem "Gruppen-Algorithmus":
10 20 30 400 500 60 ->
10 20 30 400 500 60
10 20 30 400 500 xx
> den kennen wir alle schon - (aber ohne die 500. Mit der 500 wird es einfach :-)
)
10 40 11 50 60 20
10 40 11 50 60 20
xx xx 11 50 60 xx
> Da reicht der Platz zwischen 10 und 11 nicht - (da die erste Gruppe ersetzt
würde ist es wurscht ... und würde nach der Gruppen-Version nicht mehr "kosten")
10 20 30 40 15 17 25 27 35 37
10 20 30 40 15 17 25 27 35 37
xx xx xx xx 15 17 25 27 35 37
> Hier wird der Solver verleitet, die vordere Folge (10 20 30 40) zu> nehmen - (nein, in der Gruppen-Version nicht :-) )
(Java schaue ich mir nicht an - das gibt Augenkrebs :-) )
Beschreibe bitte Deine Vorgehensweise. Praktisch wäre es auch, wenn Du
das jeweilige Ergebnis zu den Beispielen packst ...
Im Grunde ist das Problem doch ganz einfach:
Wir müssen die Positionsnummern (PosNums) bestimmen, die sich nicht
ändern.
Das löst mein Code und setzt für diese PosNums ein keep-Flag
Alle anderen müssen dann geändert werden auf Werte, die zwischen den
unveränderten liegen. (Diesen Teil enthält mein Code nicht)
Eine optimale Lösung finden wir garantiert, wenn wir alle Kombinationen
durchprobieren.
Das sind 2^3000 - und das verbietet sich damit.
Aber mal angenommen, wir probieren das aus. Was müssen wir dann
aussortieren?
Keep-Folgen, wo die PosNums nicht streng monoton aufsteigend sind.
Die gesuchten Folgen müssen nicht am Stück (Runs) sein - es tut mir leid
hier auf der falschen Fährte gewesen zu sein und euch auf eine falsche
Spur gelockt zu haben.
Es macht aber eigentlich keinen Sinn, alle keep-Kombinationen bis ins
letzte durchzuprobieren, wenn man es schon weiter vorne verkackt hat.
In einem ersten Schritt probiere ich das in Datensatz 0..N-1.
Das zweite Flag probiere ich nur noch ab da, wo das erste gesetz wurde.
Das 3. nur noch ab dem 2. und so weiter.
Das Verfahren ist ungefähr so, wie wenn man in einem Turnier alle
Spielkombinationen finden will
So kann ich immer noch alle 2^N Kombination erreichen.
Datensätze, die meine Folge kaputt machen würden lasse ich natürlich
aus.
Das allein würde die perfekte Lösung finden, ist aber immer noch zu
teuer.
Deshalb habe ich überlegt, nicht alle Datensätze auszuprobieren, sondern
nur viel versprechende.
Gute Kandidaten sind:
a) nicht weit entfernt, d.h. es müssen nicht viele Records übersprungen
werden. und
b) mit kleiner Positionsnummer, d.h. es sollen nicht zu viele
Positionsnummern übersprungen werden.
Dafür habe ich mir eine Metrik überlegt, nämlich die Summe aus Anzahl
übersprungener Datensätze und Abstand in den Positionsnummern.
Ich habe dazu die Datensätze um eine Ordnungsnummer ergänzt, die angibt,
die "wie vielt größte" Positionsnummer dieser Datensatz ist.
Mein ursprünglicher Plan war immer nur den besten Kandidaten zu nehmen.
Dann kam ich aber auf meinen Testdatensatz C - wo dann die schlechtere
Folge verwendet wird.
Fortsetung folgt...
Ich habe deshalb mehrere (konkret: bis zu RECURSION_WIDTH) "gute"
Kandidaten gesammelt (in bestCandidates) und die alle ausprobiert.
Damit liesen sich alle Testfälle lösen.
Und wenn RECURSION_WIDTH nur groß genug ist, ist die optimale Lösung
unter Garantie auch dabei.
Für N=3000 war das aber immer noch zu langsam.
Ich habe also nach weiteren Abbruchkriterien gesucht, um meinen Suchbaum
auszudünnen.
Tilo R. schrieb:> Wir müssen die Positionsnummern (PosNums) bestimmen, die sich nicht> ändern.
Wie?
Tilo R. schrieb:> Eine optimale Lösung finden wir garantiert, wenn wir alle Kombinationen> durchprobieren.> Das sind 2^3000 - und das verbietet sich damit.
Häh - kannst Du das bitte erklären?
Tilo R. schrieb:> Dann kam ich aber auf meinen Testdatensatz C - wo dann die schlechtere> Folge verwendet wird.
Na, dann warten wir mal gedudig ...
Und dann kam mir die Idee:
wenn ich einen bestimmten Datensatz markiere macht das nur Sinn, wenn
oberhalb davon das Maximum an keeps gesetzt ist. Sonst untersuche ich
einen Pfad, für den es schon weiter oben eine bessere Lösung gegeben
hätte.
Um das zu realisieren wurde das Feld maximumCountOfKeeps in Record
eingeführt.
Und ja, was soll ich sagen. Hätte man auch gleich so machen können.
Klassisches Dynamic Programming halt.
Der ganze Code um die besten Rekursionskandidaten zu finden, die Metrik,
die dazugehörigen Vorarbeiten: Das ist alles quatsch und kann gelöscht
werden.
Wenn ich noch Motivation hätte den Code aufzuräumen ging das vermutlich
auf eine DIN A4 Seite.
Schwierig an der aufgeräumten Version ist im Prinzip nur noch das
Backtracking der konkreten Lösung, wenn man das Optimum gefunden hat.
Dazu würde ich im Record ein weiteres Feld "lastMarkedRecordOnOptimum"
einfügen, mit dem sich dann hinten gesehen eine verkettete Liste der
Keep-Records ergeben würde.
Tilo R. schrieb:> Wenn ich noch Motivation hätte den Code aufzuräumen ging das vermutlich> auf eine DIN A4 Seite.
Quäl Dich, machs und stelle es uns in Prosa vor :-)
Ich habe mal einen Algorithmus in C++ nach dem Prinzip der dynamischen
Prgrammierung zusammengebastelt. Es ist ziemlich schnell, allerdings
wächst der Rechenaufwand quadratisch mit n und (leider) ebenso der
Speicherverbrauch:
1
n t/s RAM/MB
2
————————————————————————
3
3000 0,034 36
4
10000 0,21 400
5
20000 0,80 1600
6
40000 3,1 6400
7
————————————————————————
8
9
CPU: Intel Core i7-4910MQ CPU @ 2.90GHz
Der Algorithmus liefert (sofern ich keine Bugs eingebaut habe) immer ein
Optimum. Es werden auch die Wertebereichsgrenzen 0 und 2**32
berücksichtigt. In folgendem krassen Beispiel sind zwar 20 der 22 Zahlen
bereits in der richtigen Reihenfolge, allerdings kann die erste Zahl
nicht kleiner als 0 und die letzte nicht größer als 2**32-1 gemacht
werden, so dass stattdessen alle 20 vermeintlich schon "richtigen"
Zahlen geändert werden müssen:
1
Aufgabe Lösung
2
————————————————————————————
3
0 <--> 0
4
0 1
5
1 2
6
2 3
7
3 4
8
4 5
9
5 6
10
6 7
11
7 8
12
8 9
13
9 10
14
4294967286 11
15
4294967287 12
16
4294967288 13
17
4294967289 14
18
4294967290 15
19
4294967291 16
20
4294967292 17
21
4294967293 18
22
4294967294 19
23
4294967295 20
24
4294967295 <--> 4294967295
25
————————————————————————————
Man könnte ggf. in einer Nachbearbeitung für eine gleichmäßigere
Verteilung der Zahlen sorgen, indem man alle bspw. alle geänderten
Zahlen zwischen jeweils zwei unveränderten linear zwischen den
unveränderten interpoliert.
Auch ich habe ich mir vorgenommen, später noch etwas zur Funktionsweise
zu schreiben :)
Der Algorithmus von Tilo klingt interessant und irgendwie einfacher. Ich
werde ihn mir gleich mal etwas genauer anschauen.
Dieter F. schrieb:> Kannst Du bitte die Ergebnisse Deines Algorithmus zu den Beispielen> posten?
Das sind die Beispiele, die ich in diesem Thread gefunden habe (rechts
steht jeweils die gefundene Lösung):
Yalu X. schrieb:> Wenn ich ein wichtiges Beispiel übersehen habe, lass es mich wissen, und> ich werde es nachliefern.
Sieht ja prima aus :-) - kannst Du den Algorithmus bitte auch noch in
Prosa schreiben?
Hallo Dieter,
ich bin's, der Peter mit den Übersetzungsproblemen! :)
Dieter F. schrieb:> Tilo R. schrieb:>> Eine optimale Lösung finden wir garantiert, wenn wir alle Kombinationen>> durchprobieren.>> Das sind 2^3000 - und das verbietet sich damit.>> Häh - kannst Du das bitte erklären?
Du kannst jeden Wert der List neu beschreiben oder nicht.
Bei 3000 Werten gibt es genau 2^3000 Kombinationen.
@Michael:
Nachdem zwei Leute schon einen Algorithmus geliefert haben, solltest Du
Ihnen mal einen realen Datensatz (nur die Zahlenfolge!) zum Fraß
vorwerfen.
Du kannst den vielleicht in eine ASCII-Datei wegschreiben, mit
irgendeinem Trennzeichen or CR+LF. Das hat wenig Entropie und lässt sich
gut komprimieren. Das Archiv könntest Du ja an einen Beitrag anhängen.
Was meinst Du?
(Fast) minimale Java Lösung ist fertig.
Und schafft 50.000 in 7 Sekunden (komplett zufällig, ohne Ausgabe).
Ich habe den ganzen quatsch weggemacht.
Die Rekursion auch (die verläuft sich eh nur wenn die Heuristiken
fehlen)
Einfache, doppelte Schleife. O(n^2)
Am Algorithmus gibts da vermutlich kaum noch was zu optimieren.
Der Kern liegt jetzt auf 27 Zeilen.
Der ganze Rest ist zur Vorbereitung und zum Anzeigen des Ergebnisses.
Das sollte sich jetzt 1:1 in eine unhandlichere Sprache wie C übersetzen
lassen. Da ist kein (funktionsrelevanter) Java-Voodoo mehr drin.
Dieter F. schrieb:> Sieht ja prima aus :-) - kannst Du den Algorithmus bitte auch noch in> Prosa schreiben?
Grundidee:
Die Zahlen der Originalsquenz werden alle der Reihe nach bearbeitet und
zu einer neuen, aufsteigenden Sequenz zusammengefügt. Dabei hat man bei
jeder Zahl zwei Alternativen:
A1: Man behält sie bei. Da geht natürlich nur, wenn sie größer als ihr
Vorgänger in der Lösungssequenz ist.
A2: Man ändert sie, und zwar in einen möglichst kleinen Wert, so dass
man sich möglichst wenige Möglichkeiten für die nachfolgenden Zahl
verbaut. Ist die Zahl die erste in der Sequenz, ändert man sie in
den kleinsten Wert überhaupt, nämlich die 0. Hat sie hingegen einen
Vorgänger, wählt man ihren neuen Wert um 1 größer als der Vorgänger.
Das geht aber nur, wenn der Vorgänger nicht schon den maximal
möglichen Wert überhaupt, nämlich 2^32-1=4294967295 hat.
Wenn man für jede Zahl die richtige dieser beiden Alternativen auswählt,
erhält man am Ende eine Lösungsquenz mit der minimalen Anzahl von
Änderungen. Aufgabe ist es nun, jeweils die jeweils richtige Alternative
herauszufinden.
Beispiel:
Dir Originalsequenz sei 3, 5, 4.
Das folgende Baumdiagramm zeigt die Anwendung der o.g. Alternativen
nacheinander für alle 3 Zahlen:
1
3 5 4
2
↓ ↓ ↓
3
4
A1 A1 A1
5
S────────3────────5────────× → Sackgasse
6
│ │ │
7
│ │ │ A2
8
│ │ └────────6 → 1 Änderung (Optimum)
9
│ │
10
│ │ A2 A1
11
│ └────────4────────× → Sackgasse
12
│ │
13
│ │ A2
14
│ └────────5 → 2 Änderungen
15
│
16
│ A2 A1 A1
17
└────────0────────5────────× → Sackgasse
18
│ │
19
│ │ A2
20
│ └────────6 → 2 Änderungen
21
│
22
│ A2 A1
23
└────────1────────4 → 2 Änderungen
24
│
25
│ A2
26
└────────2 → 3 Änderungen
Ein × bedeutet eine Sackgasse. Hier kann A1 nicht angewandt werden, weil
die 4 nicht größer als ihr Vorgänger (5, 4 bzw. 5) ist.
Diesen ganzen Baum mit seinen bis zu 2^n Blättern komplett abzuarbeiten,
ist für größere n kaum möglich. Das ist aber auch gar nicht notwendig.
Betrachtet man den folgenden Teilbaum nach den ersten beiden Schritten,
erkennt man, dass die 2. und 3. Teilsequenz dieselbe Zahl von Änderungen
beinhalten, nämlich jeweils eine:
1
3 5
2
↓ ↓
3
4
A1 A1
5
S────────3────────5 → 0 Änderungen
6
│ │
7
│ │ A2
8
│ └────────4 → 1 Änderung
9
│
10
│ A2 A1
11
└────────0────────5 → 1 Änderung
12
│
13
│ A2
14
└────────1 → 2 Änderungen
Da für die Fortsetzung der Sequenz und die abschließende Bewertung nach
der kompletten Abarbeitung aller Zahlen nur das letzte Element der
Teilsequenz und die Anzahl der bereits gemachten Änderungen von
Bedeutung sind, genügt es bei einer Gruppe von Teilsequenzen mit
gleicher Zahl von Änderungen, die Teilsequenz mit dem kleinsten
Endelement weiterzu verfolgen, da diese den meisten Freiraum für
nachfolgende Zahlen bietet. Im Beispiel wird also die 3. Teilsequenz
nicht weiter verfolgt, der Baum wird an dieser Stelle abgeschnitten:
1
3 5
2
↓ ↓
3
4
A1 A1
5
S────────3────────5 → 0 Änderungen
6
│ │
7
│ │ A2
8
│ └────────4 → 1 Änderung
9
│
10
│ A2 A1
11
└────────0────────\ → Schnitt
12
│
13
│ A2
14
└────────1 → 2 Änderungen
Da eine Teilsequenz der Länge k maximal k Änderungen beinhalten kann,
kann der Teilbaum im k-ten Schritt nach der Beschneidung maximal k+1
Knoten haben. Dadurch wächst der Baum nicht exponentiell, sondern
linear, d.h die Anzahl der Knoten quadratisch. Deswegen ist sowohl die
Laufzeit auch der Speicherverbrauch O(n²).
Auch im 3. Schritt entstehen zwei Sequenzen mit gleicher Anzahl von
Änderungen, von denen eine abgeschnitten wird:
1
3 5 4
2
↓ ↓ ↓
3
4
A1 A1 A1
5
S────────3────────5────────× → Sackgasse
6
│ │ │
7
│ │ │ A2
8
│ │ └────────6 → 1 Änderung (Optimum)
9
│ │
10
│ │ A2 A1
11
│ └────────4────────× → Sackgasse
12
│ │
13
│ │ A2
14
│ └────────\ → Schnitt
15
│
16
│ A2 A1
17
└────────0────────\ → Schnitt
18
│
19
│
20
│
21
│
22
│ A2 A1
23
└────────1────────4 → 2 Änderungen
24
│
25
│ A2
26
└────────2 → 3 Änderungen
Blendet man nun die Sackgassen und die Schnitte aus, bleiben noch 3
potentielle Lösungen übrig, von denen natürlich diejenige mit der
geringsten Anzahl von Änderungen ausgewählt wird, nämlich 3, 5, 6.
Da – wie oben bereits festgestellt – der Baum im k-ten Schritt maximal
k+1 Knoten enthält, kann er auch kompakter in Form einer Dreiecksmatrix
dargestellt werden:
1
Änderungen
2
0 1 2 3
3
———————————————
4
3 → 3 0
5
5 → 5 [4] 1
6
4 → - 6 4 2
Anders als im Baumdiagramm sind in dieser Darstellung die ausgeführten
Schritte nicht von links nach rechts, sondern von oben nach unten
aufgetragen. Des Weiteren sind die Zahlenwerte der Teilsequenzen so
angeordnet, dass die Knoten mit gleicher Anzahl von Änderungen jeweils
in einer Spalte stehen. Der mit eckigen Klammern markierte Eintrag ist
also wie folgt zu lesen:
"Unter allen möglichen Teilsequenzen nach dem 2. Schritt (d.h. nach
Abarbeitung der Zahlen 3 und 5) mit genau 1 Änderung hat die
günstigste den Wert 4 als letztes Element."
Der erste Eintrag in der letzten Zeile ist leer, weil es keine Sequenz
der Länge 3 mit überhaupt keiner Änderung gibt. Das obige Baumdiagramm
hat an der entsprechenden Stelle ein Sackgassen-×. Der Eintrag rechts
daneben zeigt an, dass die optimale Lösungssequenz 1 Änderung beinhaltet
und mit der Zahl 6 endet.
Um die restlichen Elemente der Lösungssequenz zu ermitteln, muss man
sich an den Zweigen und Ästen des Baums bis zu seiner Wurzel
zurückhangeln. Das geht in der Dreiecksmatrix nur, wenn man ihr noch
Informationen über die Baumstruktur hinzufügt. Zu diesem Zweck wird
jeder Zahleneintrag um ein Attribut erweitert, das folgende Bedeutung
hat:
⚡: Das Element ist ungültig (der Baum hat an dieser Stelle eine
Sackgasse). Da für ungültige Elemente der Zahlenwert ohne Bedeutung
ist, wird einfach eine 0 eingetragen.
⚓: Das Element ist ein Wurzelelement und hat deswegen keinen Vorgänger.
↑: Der Vorgänger des Elements liegt in der Zeile darüber in der gleichen
Spalte. Das Element ist aus dem Vorgänger durch Anwendung der
Alternative A1 enstanden.
↖: Der Vorgänger des Elements liegt in der Zeile darüber in der linken
Nachbarspalte. Das Element ist aus dem Vorgänger durch Anwendung der
Alternative A2 enstanden.
1
Änderungen
2
0 1 2 3
3
————————————————
4
3 → 3⚓ 0⚓
5
5 → 5↑ 4↖ 1↖
6
4 → 0⚡ 6↖ 4↑ 2↖
Beginnend vom Endelement 6 führt der Weg über die 5 zum Wurzelelement 3.
Die Lösungsequenz lautet somit – richtig herum gelesen – 3, 5, 6.
Wie wird nun die Dreiecksmatrix mit Werten befüllt?
Die erste Zeile enthält in Spalte 0 immer das erste Element der
Originalsequenz und wird als Wurzelelement attributiert. Ist dieses
Element von 0 verschieden, wird in Spalte 1 eine 0 als Wurzelelement,
eingetragen, sonst wird das Feld als ungültig markiert. Das geschieht in
den Zeilen 25 bis 31 des Programmcodes.
In allen folgenden Zeilen hängt ein Eintrag von den beiden Einträgen in
der Zeile darüber in der gleiche Spalte und in der linken Nachbarspalte
wie folgt ab:
1
.. → .. VL VD .. Zeile i-1
2
AZ → .. .. NE .. Zeile i
3
4
NE: neuer Eintrag
5
VD: direkter Vorgänger
6
VL: linker Vorgänger
7
AZ: aktuelle Zahl aus der Originalsequenz
Ist VL gültig und kleiner als der Maximalwert (2^32-1), dann ist VL+1
ein Kandidat für NE (Anwendung von A2, Programmzeilen 44 bis 49).
Ist VD gültig und AZ größer als VD, dann ist auch AZ ein Kandidat für
NE (Anwendung von A1, Programmzeilen 51 bis 57).
Existieren beide Kandidaten, wird der kleinere von beiden, bei
Gleichheit der zweite ausgewählt (Programmzeile 54).
Je nachdem ob der erste oder der zweite Kandidat ausgewählt wurde
bekommt NE das Attribut ↖ oder ↑ (Programmzeilen 48 und 56).
Das Zurückhangeln zum Wurzelknoten geschieht in den Zeilen 85 bis 92,
die Ausgabe in der richtigen Reihenfolge (beginnend beim Wurzelknoten)
in den Zeilen 94 bis 96.
Hier ist noch ein etwas größeres Beispiel:
1
Änderungen
2
0 1 2 3 4 5 6
3
–––––––––––––––––––––––––––––––––––––––
4
10 → 10⚓ 0⚓
5
20 → 20↑ 11↖ 1↖
6
30 → 30↑ 21↖ 12↖ 2↖
7
40 → 40↑ 31↖ 22↖ 13↖ 3↖
8
35 → 0⚡ 35↑ 32↖ 23↖ 14↖ 4↖
9
37 → 0⚡ 37↑ 36↖ 33↖ 24↖ 15↖ 5↖
Die ermittelte Lösung lautet 10, 20, 30, 31, 35, 37.
Noch ein paar Implementierungsdetails:
Die Dreiecksmatrix ist als Vektor von Vektoren von Strukturen
implementiert. Die Strukturen bestehen aus einem Integer-Zahl
und einem Enum-Attribut.
Um ein paar zusätzliche Abfragen am linken und rechten Rand der
Dreiecksmatrix (am linken gibt es kein VL und am rechten kein VD)
einzusparen, wird am Anfang und am Ende jeder Zeile ein ungültiger
Dummy-Eintrag angefügt. Die Matrix im obigen Beispiel sieht also in
Wirklichkeit so aus:
1
Änderungen+1
2
0 1 2 3 4
3
——————————————————
4
3 → 0⚡ 3⚓ 0⚓ 0⚡
5
5 → 0⚡ 5↑ 4↖ 1↖ 0⚡
6
4 → 0⚡ 0⚡ 6↖ 4↑ 2↖ 0⚡
Die Variable first enthält den Index des ersten gültigen Elements der
aktuell bearbeiteten Zeile. Da in der nächsten Zeile first mindestens
genauso groß ist, können bei der Bearbeitung die erste first Einträge
übersprungen werden. Das macht sich vor allem bei Sequenzen mit sehr
vielen Änderungen positiv in der Laufzeit bemerkbar.
Michael R. schrieb:> c.m. schrieb:>> warum überhaupt eine position updaten/inserten, wenn man "order by">> selects machen kann?>> weil ich keinen Einfluss auf die Applikation habe, und diese nun mal> "order by posnr" macht
In PostgreSQL könnte man das vielleicht mit sortierten Indizes, Views
und ggf. dem Rules-System lösen... aber möglicherweise habe ich auch nur
das Problem nicht richtig verstanden.
Wow, ihr seids ja echt der Hammer!
ich hab jetzt mal die Java-Version sehr sehr ungläubig angestarrt, dann
in Perl übersetzt, gestestet, und sie funktioniert! Zumindest konnte ich
noch keinen Fall finden, wo sie eine nicht optimale Lösung gefunden
hätte.
ich würde das auch gerne mit der (spannend aussehenden) C++-Variante
machen, aber dafür spreche ich C++ zu schlecht :-)
Irgendwie will grad gar nicht in meinen Kopf, warum man einen Suchbaum
mit 2^n Möglichkeiten so einfach mit einer doppelten Schleife (und damit
max n^2) abarbeiten kann... aber vielleicht sehe ich auch grad den Wald
vor lauter Bäumen nicht.
Peter M. schrieb:> Allen Datenbankfreaks sei gesagt, dass es für den Algorithmus egal ist,> ob der Inhalt von Schuhkartons verändert wird, Flugzeuge in andere> Hangars gesteckt werden oder einmal Anfassen einen Mondflug bedeutet.
Bein zwar kein Datenbankfreak, dennoch sei die vermutlich naive Frage
gestattet: Ist es denn undenkbar, dass die teuren Datenbanktrigger für
einen Moment deaktiviert werden?
Berner schrieb:> Peter M. schrieb:>> Allen Datenbankfreaks sei gesagt, dass es für den Algorithmus egal ist,>> ob der Inhalt von Schuhkartons verändert wird, Flugzeuge in andere>> Hangars gesteckt werden oder einmal Anfassen einen Mondflug bedeutet.>> Bein zwar kein Datenbankfreak, dennoch sei die vermutlich naive Frage> gestattet: Ist es denn undenkbar, dass die teuren Datenbanktrigger für> einen Moment deaktiviert werden?
der "Moment" kann ein langer sein bei (dummen) tausenden Updates.
und soweit ich weiß gilt das Deaktivieren von triggern im SQL Server
"global", also über alle Sessions. Wenn dann ein (anderes) update kommt,
und vom Trigger verpasst wird, hast einen Fehler den du vermutlich
jahrelang suchst.
Tilo R. schrieb:> (Fast) minimale Java Lösung ist fertig.
Gratulation, der Algorithmus ist sehr elegant und so bestechend einfach,
dass ich ihn jetzt auch endlich verstanden habe ;-)
Da dein Algorithmus nur O(n) Speicher braucht, ist er dem meinigen
natürlich weit überlegen. Ich hatte ursprünglich auch gedacht, mit O(n)
Speicher auszukommen, und für das eigentliche, zeitaufwendige
Durchnudeln der Eingangsdaten trifft das auch zu, da dort nur immer die
beiden jeweils letzten Zeilen der Dreieckmatrix angefasst werden.
Damit kann ich aber zunächst nur die minimale Anzahl der notwendigen
Änderungen und das letzte Element der Lösungssequenz ermitteln. Für die
Bestimmung der restlichen Elemente ist mir nichts Besseres eingefallen,
als die komplette Dreieckmatrix im Speicher zu halten. Wahrscheinlich
gibt es auch hier eine sparsamere Methode, aber sie hat ihren Weg in
meinen Kopf (noch) nicht gefunden ;-)
Möglicherweise hat dein Code aber noch einen Bug:
IMHO sollte es hier (j-i) statt (i-j) heißen. Der Fehler tritt bei
deinen Beispielen nicht in Erscheinung, da die Zahlenwerte so weit
auseinanderliegen, dass die If-Bedingung sowieso nie wahr wird.
Noch eine potentielle Optimierungsmöglichkeit:
1
if(recordJ.posNum<=lastUsedPosNum)continue;
Diese Zeile kannst du IMHO streichen, da die Abfrage in der nächsten
Zeile (nachdem sie korrigiert ist) mit abgedeckt wird. Dadurch wird der
Algorithmus noch etwas einfacher. Ob er dadurch auch schneller wird,
hängt aber davon ab, wie oft die Bedingung zutrifft. Man müsste das an
repräsentativen Beispieln testen.
Michael R. schrieb:> Irgendwie will grad gar nicht in meinen Kopf, warum man einen Suchbaum> mit 2^n Möglichkeiten so einfach mit einer doppelten Schleife (und damit> max n^2) abarbeiten kann... aber vielleicht sehe ich auch grad den Wald> vor lauter Bäumen nicht.
Der Suchbaum wird ganz gewaltig gestutzt. Lies mal meinen Beitrag von
oben bis zu diesem Abschnitt durch:
Yalu X. schrieb:> Da eine Teilsequenz der Länge k maximal k Änderungen beinhalten kann,> kann der Teilbaum im k-ten Schritt nach der Beschneidung maximal k+1> Knoten haben. Dadurch wächst der Baum nicht exponentiell, sondern> linear, d.h die Anzahl der Knoten quadratisch. Deswegen ist sowohl die> Laufzeit auch der Speicherverbrauch O(n²).
Das ist zwar ein anderer Algorithmus als Tilos, aber das Grundprinzip
des Beschneidens des Baums ist in beiden Fällen dasselbe.
Yalu X. schrieb:> Gratulation, der Algorithmus ist sehr elegant und so bestechend einfach,> dass ich ihn jetzt auch endlich verstanden habe ;-)
Danke :-)
> Möglicherweise hat dein Code aber noch einen Bug:
> IMHO sollte es hier (j-i) statt (i-j) heißen. Der Fehler tritt bei> deinen Beispielen nicht in Erscheinung, da die Zahlenwerte so weit> auseinanderliegen, dass die If-Bedingung sowieso nie wahr wird.
Sehr gut gesehen!
> Noch eine potentielle Optimierungsmöglichkeit:
1
if(recordJ.posNum<=lastUsedPosNum)continue;
> Diese Zeile kannst du IMHO streichen, da die Abfrage in der nächsten> Zeile (nachdem sie korrigiert ist) mit abgedeckt wird.
Stimmt auch!
> Dadurch wird der> Algorithmus noch etwas einfacher. Ob er dadurch auch schneller wird,> hängt aber davon ab, wie oft die Bedingung zutrifft. Man müsste das an> repräsentativen Beispieln testen.
Viel erwarte ich da nicht mehr, es werden ja nur ein paar Zeilen
gespart. Es gibt ja eigentlich keinen Baum mehr wo man Äste abschneiden
kann.
Wenn es jetzt noch schneller sein müsste würde ich zu C gehen. (C++ kann
ich nur in Grundlagen. Ich bewundere es immer wieder wie elegant das
aussieht wenn man std:: beherrscht.)
Das dritte Abbruchkriterium lässt sich aber auch noch verbessern:
Yalu X. schrieb:> Möglicherweise hat dein Code aber noch einen Bug:>> if ((i-j) > (recordJ.posNum-lastUsedPosNum)) continue;>> IMHO sollte es hier (j-i) statt (i-j) heißen. Der Fehler tritt bei
Kann ich bestätigen, hab grad Tests mit "engen" Werten gemacht, mit
(j-i) tut es wie es soll.
Auch die anderen Optimierungen hab ich drinnen.
Mein (Perl) Code findet das Optimum in 2000 Sätzen mit zwischen 10 und
500 Fehlern in 0.6 Sekunden. Ich bin begeistert!
Vielen herzlichen Dank!
Tilo R. schrieb:> Wenn es jetzt noch schneller sein müsste würde ich zu C gehen. (C++ kann> ich nur in Grundlagen.
Hab's mal ausprobiert. Hier sind die Ergebnisse für drei verschiedene
Testsequenzen:
1
Zeiten in s für 40000 Elemente auf
2
Intel Core i7-4910MQ CPU @ 2.90GHz
3
4
Java C C++¹
5
——————————————————————————————————
6
steigend 2,75 1,87 1,67
7
8
fallend 1,69 0,74 3,01
9
10
zufällig 1,15 0,43 1,66
11
——————————————————————————————————
12
13
¹) anderer Algorithmus (s. Thread)
Wie man sieht, hängen die Laufzeiten nicht nur vom Algorithmus und der
Programmiersprache, sondern auch von der Beschaffenheit der Daten ab.
Danke für die C-Version!
Nebenbei: Statt mit einer struct (oder einem Objekt in C++/Java, einem
Hash in Perl) zu arbeiten, kann man auch einfach zwei Hilfsarrays
nehmen. Hat nebenbei den Vorteil, dass man direkt mit der Original-Liste
arbeiten kann, und die nicht erst in die spezifische Datenstruktur
umwandeln muss.
In C/C++ wird sich das nicht viel schenken (dank kluger Compiler), Java
kann ich nicht beurteilen, in Perl machts natürlich viel aus!
Thread beobachten
Seitenaufteilung abschalten