in sortierte liste sortiert einfügen

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