in sortierte liste sortiert einfügen

[vsilverlord]

Hallo, ich habe eine sortierte liste ( tsortierteliste), diese hat viele zahlenwerte gespeichert, die alle sortiert sind.
Nun möchte ich eine neue Zahl einfügen, diese soll allerdings richtig einsortiert werden.
Welcher Algorithmus ist dafür wohl am besten geeignet? Heapsort usw. eigenet sich ja eigentlich nur dafür, ganze listen zu sortieren, oder? Welcher algorithmus ist dabei am schnellsten?
gruß

[mkinzler]

Schau die mal TList.Sort() an

[DeddyH]

Ich denke, mit einer binären Suche bekommst Du den Einfüge-Index auch ganz gut.

[vsilverlord]

ok, das problem ist, dass ich nicht nur zahlenwerte einfüge, sondern ganze objekte. Ein attribut dieser Objekte ist dann der zahlenwert, mit dem ich die objekte sortiere, deswegen kann ich tlist.sort() nicht benutzen!
gibts da einen standart algorithmus für binäre suche oder muss ich den neu schreiben? ist das auch für ca. 100000 objekte sinnvoll?
gruß

[DeddyH]

Es gibt ja auch noch TList.CustomSort, da kannst Du selbst bestimmen, nach welchen Kriterien sortiert wird. Und zur binären Suche gibt es IIRC in der DP einige Beispielcodes (u.a. von Luckie).

[nahpets]

Hallo,

für Dein Problem dürfte die binäre Suche die beste Möglichkeit sein, bei 100000 Objekten kommst Du mit ca. 16 oder 17 Vergleichen aus. Weniger geht nicht. (2 hoch 17 = 131072, d. h. bei 131072 Objekten benötigst Du 17 Vergleiche.)

Schau mal bitte unter http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche, dort findest Du auch Beispiele, allerdings nicht für Delphi/Pascal. Sie sollten aber für den Nachbau in Delphi geeignet sein.

[Medium]

Binäre Suche ist sicherlich das schnellste für beliebige Daten deren Verteilung man überhaupt nicht einschätzen kann. Je gleichmäßiger die Einträge verteilt sind, desto effektiver wird die darauf basierende Interpolationssuche, die aber bei unerwartet schlecht verteilten Einträgen wiederum zur Laufzeit der linearen Suche (O(n)) verkümmert. Diesem potentiellen Nachteil wird versucht mit der quadratischen Binärsuche zu begegnen, die wiederum eine Weiterentwicklung der Interpolationssuche ist. Und eben letztere würde ich auch versuchen wenn es um ziemlich viele Einträge geht. Bei nur ein paar hundert bis taused ist der Gewinn gegenüber der einfachen binären Suche vermutlich nicht mehr SO ausschlaggebend - je nach Anwendungsfall halt.

Wenn du recht genau weisst, dass deine Einträge z.B. grob quadradtisch oder logarithmisch vorkommen, könntest du durch Anpassung des Teilungsintervalls die einfache binäre Suche auch schon auf ein prima Niveau bekommen, aber das sind dann spezialisierte Anpassungen die ganz von der jeweils einzelnen Liste abhängen.

[hoika]

Hallo,

Das Problem habe ich auch oft.

Die Liste ist ja bereits sortiert !
Ein neues Element soll einsortiert werden soll.

Zur Zeit hänge ich es einfach hinten an und sortiere noch mal (CustomSort).

Die Frage ist:
Finde ich den Index des neuen Elementes auch ohne komplette Neusortierung,
BinSearch findet ja nur einen Wert, aber der Wert steht ja noch nicht drin.
Es müsste also das "genau eins kleiner davor" Element bzw. dessen Index gefunden werden.

Quicksort ist bei schon sortierten Listen besonders schnell,
oder war das das genaue Gegenteil ?


Heiko

[Medium]

Zitat:

Zitat von hoika

Die Frage ist:
Finde ich den Index des neuen Elementes auch ohne komplette Neusortierung,
BinSearch findet ja nur einen Wert, aber der Wert steht ja noch nicht drin.
Es müsste also das "genau eins kleiner davor" Element bzw. dessen Index gefunden werden.

Was die binäre Suche auch erledigt. Dort wo der Algo abbricht wegen nicht gefunden, musst du nur noch einen zusätzlichen Vergleich mit den zwei verbleibenden Elementen machen, und dann weisst du wo du einfügen musst.

Was du machst würde ich glatt als Verbrechen bezeichnen! Quicksort ist zwar als Sortierer auf vorsortierten Listen schnell (nicht das schnellste vermute ich allerdings, aber auch nicht übel), aber auch nur wenn man die Vertauschung als Kostenfunktion her nimmt. Es werden trotzdem noch N*(N-1)/2 Vergleiche gebraucht! Binary search dagegen braucht nur log(N) Vergleiche (im worst-case(!)).
Die Frage am Ende ist ja hier: Brauche ich die Liste nur ein Mal am Ende sortiert, oder brauche ich sie die ganze Zeit sortiert während Einträge kommen und gehen? Im ersten Fall ist ein einmaliger Quicksort nach Befüllen sicherlich die schnellere und bessere Wahl, im zweiten ganz klar eine (gute) Suche. Aber das so zu mischen... kann man auf ein paar zig bis hundert Elementen mal machen aus Faulheit, aber eigentlich gehört das bestraft ;)

Ein wenig versalzen tut man sich das alles aber wenn man diese schmucken Listen auf Array-Basis benutzt, da hier das Einfügen im worst-case (an Index 0) eine O(N) Operation ist, und u.U. gleich noch Speicherallokation + Umkopieren auslöst. Eine Double-Linked-List ist bei sehr vielen Elementen wohl das leichtgewichtigste, was man sich aber durch den Verlust des wahlfreien Zugriffs erkaufen muss. Ab dann muss eben traversiert werden, aber in der Regel geht man ja eh mit Schleifen über Listen - da tut's dann nicht weh statt "Liste[i]" mal "CurrentElement := CurrentElement.Next" zu schreiben.

[hoika]

Hallo,

Zitat:

Was du machst würde ich glatt als Verbrechen bezeichnen!

höhö,

jaja, der gute alte Code.

Bei neuen Code wird es per order by vorsortiert.

TJAAAAAAA, WIR WAREN ALLE MAL JUNG ;)


Ich habe hier nen generischen Suchalg (ähnlich wie TList.CustomSort),
vielleicht erweitere ich den noch um ein SortedInsert.


Heiko

[vsilverlord]

Hallo, ich hab den algorithmus nicht ganz auf mein ding anwenden können, deswegen hab ich jetz einen eigenen geschrieben, der eine binäre Suche durchführt (glaube ich jedenfalls).
Der sieht allerdings schrecklich aus, weswegen ich den euch mal zeigen möchte, sodass ihr daran (konstruktive) Kritik üben könnt!
Zur Erklärung: Ich habe ein Objektklasse Tauto, diese hat eine eigenschaft Pos, die man mit GibPos abrufen kann. Alle Autos in der Liste sollen nun gemäß ihrer Position eingefügt werden. Die Liste vom Typ Tlist heißt Liste.

Delphi-Quellcode:

procedure tautolist.addauto (auto: tauto);
var
i,mini,maxi:integer;
begin
  i:=round(Liste.Count/2);//Der derzeitige Punkt in der Liste
  maxi:=round(Liste.Count);//der derzeitige höchste Punkt
  mini:=1; // der derzeitige niedrigste Punkt.
  begin
    while (((tauto(Liste.Items[i-1]).GibPos >auto.GibPos)or //wenn Pos des vorherigen zu groß
    (auto.GibPos> tauto(Liste.Items[i+1]).GibPos))=true)// oder Pos des nächsten zu klein
     and(((Liste.Items[i]<>Liste.Last)and(Liste.Items[i]<>Liste.First))=true) do //und wenn nicht am ende oder anfang angekommen
     begin
          begin
          if (tauto(Liste.Items[i+1]).GibPos <auto.GibPos)then //wenn derzeitiger Punkt zu groß
             begin
               maxi:=i;
               i:=round((maxi-mini)/2);
             end;
          if (auto.GibPos< tauto(Liste.Items[i-1]).GibPos)then //wenn derzeitiger Punkt zu klein
             begin
               mini:=i;
               i:=round((maxi-mini)/2);
             end;
          end;
     Liste.Insert(i,auto);
     end;
  end;
end;

[DeddyH]

Ich bin den Code jetzt nicht im Einzelnen durchgegangen, aber ein paar Dinge fallen mir auf:
- niemals mit true vergleichen
- wieso wendest Du Fließkommaoperationen auf ganze Zahlen an? Du könntest alternativ div 2 bzw. shr 1 benutzen.
- warum gehst Du von 1 bis Liste.Count, um dann den Index intern zu erhöhen/erniedrigen?

[edit] shl in shr geändert, war genau falsch herum :oops: [/edit]

[vsilverlord]

Zitat:

- niemals mit true vergleichen
- wieso wendest Du Fließkommaoperationen auf ganze Zahlen an? Du könntest alternativ div 2 bzw. shl 1 benutzen.

das sehe ich ein!

Zitat:

- warum gehst Du von 1 bis Liste.Count, um dann den Index intern zu erhöhen/erniedrigen?

das verstehe ich nicht! ich mach doch eine binäre suche, dh immer "hälfteln", nicht von 1 ab sondern von der Hälfte, also bei 100 items von dem 50sten an.

[Tryer]

Da Du immer auf das Element "i+1" zugreifst macht es doch Sinn von vornherein nicht von 1 bis 100 sondern von 0 bis 99 zu zählen.

Wenn Du statt 'div 2' was anderes nehmen möchtest dann besser 'shr 1' statt 'shl 1', denn das entspricht *2.

Schau Dir auch mal an auf welchen Index zu vesuchst zuzugreifen wenn die Liste leer ist!

MfG,
Tryer

[Satty67]

[OT]

Zitat:

Zitat von DeddyH

- warum gehst Du von 1 bis Liste.Count, um dann den Index intern zu erhöhen/erniedrigen?

das hab' ich (unsinnigerweise) fast 10 Jahre so gemacht. Zum einen weil ich das gleiche ungute Gefühl wie der TS hatte, wenn eine 0 in einer Division steht (vorne darf die das aber natürlich), zum anderen weil ich immer darauf bestand, das eine Liste von 1 - Max geht und nicht von 0 bis (Max-1).

Naja, ich bin davon los gekommen ;)
[/OT]

[alzaimar]

Wieso nimmst Du nicht einfach eine Skiplist? Die ist viel schneller als eine sortierte Liste.

Zitat:

Zitat von Medium

Binäre Suche ist sicherlich das schnellste für beliebige Daten deren Verteilung man überhaupt nicht einschätzen kann.

Nö, glaub ich nich :mrgreen: Skiplist ist eigentlich schneller.

Muss natürlich im Einzelfall getestet werden.

[Medium]

Zitat:

Zitat von wikipedia

Therefore, the total expected cost of a search is O(log(1/p, n))/p which is O(log(n)) when p is a constant.

Ich wage die Behauptung, dass es hier wieder ganz auf den konkreten Fall ankommt ob sich eine Skip-List lohnt. Ein nicht unwichtiger Teil des von dir zitierten ist: "für beliebige Daten deren Verteilung man überhaupt nicht einschätzen kann", das heisst ohne jede Kenntnis der inneren Struktur der Daten. Für spezifische Sets lassen sich fast immer angepasste Verfahren finden, der TE gibt hierüber aber leider keine Auskunft. Also muss man doch vom generischen Fall ausgehen oder? :) In diesem sind die beiden Verfahren aber immerhin gleich gut. Skiplisten bedürften lediglich etwas mehr Implementierungsaufwand oder Fremdklassen, da Delphi keine mitbringt.
Ein Nachteil der Skiplisten ist aber sicherlich der Strukturelle Overhead, sowie redundante Elemente, wodurch man u.U. in die Situation geraten kann dass man mehr Speicher für eine vergleichbare Performance verbrät - und joa, wenn wir über Listen der Größe sprechen dass sich optimierte Suchverfahren lohnen, wird Speicher schon weniger unendlich =] Dem TE wird, wenn er wirklich das Optimum haben will, nicht viel anderes bleiben als alle in Frage kommenden Algos zu basteln, und sie an seinem Echt-Daten Set zu testen. (Ich persönlich habe die besten Erfahrungen mit Interpolationssuche gehabt, aber das war halt auch wieder ein Fall in dem sie einfach gut zu den Daten gepasst hat.)

[alzaimar]

Hi Medium, mein Vergleich zeigt jedoch, das beim Suchen bzw. Einfügen eine Skiplist um ein Vielfaches schneller ist. Die Theorie ist mir hier ziemlich egal, wenn mein PC sagt, es ist schneller, dann isses das auch :mrgreen:

Großartig rumeiern muss man auch nicht:
Version 1: Eine TStringlist implementiert die binäre Suche (wenn Sorted := True)
Version 2: Eine TcsSkiplist.

Sollte in 10 Minuten zusammengeklickert sein.

[Medium]

Probieren > Studieren. Ich hab eine Skiplist noch nicht im Einsatz gehabt, also muss mir dein Wort hier genügen :)

[alzaimar]

Zitat:

Zitat von Medium

...also muss mir dein Wort hier genügen :)

Oder ein Link

Zitat:

Zitat von alzaimar

...Skiplist ist eigentlich schneller.

Dieser Link führt dich zu einem Artikel, in dem ich mal die gängigen Strukturen (Hashmap, Skiplist, Sorted List, Hashed Stringlist) miteinander vergleiche: Als Basis dienen Random-Strings. Das Zeitverhalten zum Suchen und Einfügen ist grafisch dargestellt. Als 'Sorted List' habe ich die TStringlist mit 'Sorted = True' verwendet, bei der ja die Binärsuche verwendet wird.