Doppel schnell aus Liste löschen.

[himitsu]

Zitat von Dejan Vu:

Dann hättest Du -rein theoretisch- das gleiche Performanceproblem bzw. Optimierungspotential

Nicht, wenn es sehr viele Doppelte sind, denn jetzt werden die Doppelten mit verglichen und so wären sie garnicht erst in der Liste.

Und wenn man die Liste gleich sortiert aufbaut, dann verringert sich auch noch der Nachschau- und Sortieraufwand.

[mkinzler]

Es kommt auch darauf an, wieviele auf einen Schlag eingefügt werden und wieviele Einträge die Liste hat.
Eine kleine Verzögerung beim Einfügen ist meist weniger schlimm, als eine größere, wenn später vorhandene Werte entfernt werden müssen.

Bei eienr Stringliste kann man das Einfügen von Doubletten ja einfach durch entsprechenden Wert von <TStringList>.Duplicates verhindern.

[Dejan Vu]

Natürlich kann es sinnvoll sein, eine Prüfung am Eingang vorzunehmen, aber rein rechnerisch ist der Aufwand eh der Gleiche. Wenn ich bei jedem Einfügen mit 'IndexOf' prüfe, ob es den Wert schon gibt, dann habe ich bei jedem Einfügen den Aufwand O(n). Wenn ich also N Elemente einfüge ist das O(n^2). Kein Unterschied zu vorher (vom Aufwand, Komplexität, Big-Oh). Klar, die zu durchsuchende Liste ist anfangs kürzer, insofern wird das schon etwas bringen, aber zuerst schrauben wir an der Komplexität (Aufwand, Algorithmus), und anschließend kümmern wir uns um den Kleinkram.

Wenn ich die Liste ständige sortiert halte, ist der Aufwand sogar höher, denn das Einfügen eines Wertes in eine Liste ist leider vom Aufwand O(n), denn auch wenn das Suchen schnell geht, muss ich doch Platz schaffen, um das Element in der Mitte irgendwo einzufügen, und das geht in einer normalen Liste nicht unter O(n). Ergo habe ich beim Einfügen in eine sortierte Liste den Aufwand O(log n) für das Suchen + O(n) für das Einfügen = O(n). Für N Elemente sind das wieder O(n^2).

Das lohnt sich nur, wenn die Wartezeit beim Einfügen eines Elements unwichtig ist bzw. in der Betrachtung keine Rolle spielt, z.B. da die Erfassung z.B. manuell oder nur sporadisch erfolgt.

[Jasocul]

Programmieraufwand:
Ob ich nun beim Einfügen eine Prüf-Routine habe oder eine Routine im Anschluss habe, halte ich für einen geringen Unterschied beim Programmieraufwand (wenn überhaupt einer da ist).

Schnelligkeit:
Das hängt natürlich von der Menge der Elemente ab.
Aber prinzipiell sollte die Anzahl der Vergleiche weniger sein, wenn man vor dem Einfügen prüft, weil grundsätzlich weniger Elemente vorhanden sind.
Abgesehen davon spart man sich im Doppelungsfall das Einfügen und das spätere Löschen.

Oder stimmt etwas nicht mit meinem gesunden Menschenverstand?

[mkinzler]

Zitat:

Wenn ich bei jedem Einfügen mit 'IndexOf' prüfe, ob es den Wert schon gibt, dann habe ich bei jedem Einfügen den Aufwand O(n).

Unter Umständen fällt das aber nicht so auf.

[Bjoerk]

OK. Vielen Dank für die Beiträge. Ich werde mal testen. Bei der Sort Variante bin ich mir im Moment gar nicht sicher, ob eine so sortierte Liste garantiert, daß identische Punkte auch hintereinander in der Liste liegen.

Delphi-Quellcode:

procedure TFloatPoints.QuickSort(L, R: integer);
var
  I, J, K: integer;
  Pivot: TFloatPoint;
begin
  repeat
    I := L;
    J := R;
    K := (L + R) shr 1;
    Pivot := FItems[K];
    repeat
      while (FItems[I].X < Pivot.X) and (FItems[I].Y < Pivot.Y) do
        Inc(I);
      while (FItems[J].X > Pivot.X) and (FItems[J].Y > Pivot.Y) do
        Dec(J);
      if I <= J then
      begin
        Exchange(I, J);
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then
      QuickSort(L, J);
    L := I;
  until I >= R;
end;

[himitsu]

Zitat von Bjoerk:

Bei der Sort Variante bin ich mir im Moment gar nicht sicher, ob eine so sortierte Liste garantiert, daß identische Punkte auch hintereinander in der Liste liegen.

Wenn nicht, dann stimmt was mit der Sortierung nicht.

[Bjoerk]

Aha.

[Horst_]

Hallo,

Du sortierst doch zweidimensional.
Da musst Du doch zuerst x und nur bei gleichem x auf y testen

Statt

Delphi-Quellcode:

while (FItems[I].X <= Pivot.X) and (FItems[I].Y < Pivot.Y) do
        Inc(I);

Nun

Delphi-Quellcode:

while true do
  begin
  IF FItems[I].X <  Pivot.X then
    inc(i)
  else
    IF (FItems[I].X = Pivot.X) AND  (FItems[I].Y < Pivot.Y) then
      inc(i)
    else
      Break;
  end;

Gruß Horst

[Dejan Vu]

Zitat von Jasocul:

Programmieraufwand:

Der ist gut Mit 'Aufwand' meine ich die Performance hinsichtlich der Komplexität. Also Big-Oh. Man sagt doch: Quicksort ist vom Aufwand O(n log n), Bubblesort ist vom Aufwand O(n^2) usw.

Zitat:

Oder stimmt etwas nicht mit meinem gesunden Menschenverstand?

Ganz bestimmt nicht, also ganz bestimmt ist alles in Ordnung. Ich sagte ja: Es ist vermutlich schneller, das ganze während des Einfügens zu machen, aber von der Komplexität her (hier wieder: Nicht, was man tippt ) ist es das Gleiche.

Von der reinen Performance her wäre die Hashmap-Variante mit Sicherheit die schnellste.