spezieller Sortier-Algorithmus gesucht

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

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!

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.

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

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.

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. :)

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).

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.

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!

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.

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 :-(

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:
>> 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.

ich nehme das optimal zurück :-(

Tilo R. schrieb:
> ich nehme das optimal zurück :-(

und ich muss noch mehr nachdenken. Da ist noch sehr viel Luft zum 
Optimum.

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.

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.

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...

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 :-)

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.

Peter M. schrieb:
> Ein verbundener Run besteht aus einzelnen Runs, die alle aufsteigend
> sortiert sind.

hab ich falsch überlesen, sorry...

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.

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.

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.

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.

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):

1

Beispiel 1:    Beispiel 2:    Beispiel 3:    Beispiel 4:

2

 10  10        100 100         60   0         40   0

3

 20  20        200 200         20  20         50   1

4

 30  30        300 300         30  30         60   2

5

400 400        600 301         40  40         10  10

6

500 500        400 400         50  50         20  20

7

 60 501        500 500         10  51         30  30

8

Änderungen: 1  Änderungen: 1  Änderungen: 2  Änderungen: 3

9

10

11

Beispiel 5:    Beispiel 6:    Beispiel 7:    Beispiel 8:

12

 40  40         10  10         10  10         10  10

13

 50  50         20  20         40  40         20  11

14

 30  51         30  30         11  41         30  12

15

 60  60         40  31         50  50         40  13

16

 10  61         35  35         60  60         15  15

17

 20  62         37  37         20  61         17  17

18

Änderungen: 3  Änderungen: 1  Änderungen: 2   25  25

19

                                              27  27

20

                                              35  35

21

                                              37  37

22

                                             Änderungen: 3

Wenn ich ein wichtiges Beispiel übersehen habe, lass es mich wissen, und
ich werde es nachliefern.

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.

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:

1

                if ((i-j) > (recordJ.posNum-lastUsedPosNum)) continue;

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:

1

    if ((i-j) > (recordJ.posNum-lastUsedPosNum)) continue;

> 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:

1

    if (recordJ.maximumCountOfKeeps > keeps) continue;

Hier geht auch ein >=.

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!