Doppel schnell aus Liste löschen.

[Bjoerk]

Bei 100.000 Punkten kann das schon mal 10 sec. dauern. Hat jemand eine bessere Idee? Die Klasse ist eigentlich schon ziemlich optimiert, analog TList (Capacity, Move und Co.) :gruebel:

Delphi-Quellcode:

function TFloatPoints.IndexOf(const Value: TFloatPoint): integer;
var
  I: integer;
begin
  Result := -1;
  for I := 0 to FCount - 1 do
    if Util_SameFloatPoint(FItems[I], Value) then
    begin
      Result := I;
      Break;
    end;
end;

procedure TFloatPoints.RemoveDoubles;
var
  List: TFloatPoints;
  I: integer;
begin
  List := TFloatPoints.Create;
  try
    for I := 0 to FCount - 1 do
      if List.IndexOf(FItems[I]) < 0 then
        List.Add(FItems[I]);
    Assign(List);
  finally
    List.Free;
  end;
end;

[Jens01]

Warum baust Du eine Liste neu auf, wenn Du welche rauslöschen willst? Oder habe ich das nicht verstanden?
Schachpunkt kömmte aus dies "Util_SameFloatPoint" sein.

... Ach, "Double" für "doppelte" ...

Delphi-Quellcode:

function IsDuplicateInList(List: array of Variant): Boolean;
var
  i : Integer;
  ii: Integer;
begin
  for i    := 0 to Length(List) - 2 do
    for ii := i + 1 to Length(List) - 1 do
      if List[i] = List[ii] then
        Exit(True);
  Result := False;
end;

Das ist aus meiner Toolsammlung, hilft das weiter?

Das Sortieren der Liste könnte helfen.

[Bjoerk]

Hi Bud. Stimmt. Die Werte sollen aber rausgelöscht werden. So isses schomal schneller. In der Compare gibst wohl nichts zu optimieren? (Sch.. dxf Files, das sind ja Unmengen von Punkten drin..)

Delphi-Quellcode:

procedure TFloatPoints.RemoveDoubles;
var
  I, J: integer;
begin
  for I := FCount - 2 downto 0 do
    for J := FCount - 1 downto I + 1 do
      if Util_SameFloatPoint(FItems[I], FItems[J]) then
        Delete(J);
end;

function Util_SameFloatPoint(const A, B: TFloatPoint; const Eps: double = 1E-4): boolean;
begin
  Result := SameValue(A.X, B.X, Eps) and SameValue(A.Y, B.Y, Eps);
end;

Edit: Falls du wissen möchtest wofür:
http://abel-software.de/download/DrawPadTutorial.pdf
Seite 4, Dxf Fangpunkte.

[Amateurprofi]

Es wäre hilfreich, zu wissen wie TFloatPoint, TFloatPoints und Util_SameFloatPoint definiert sind.
Ohne diese Informationen sind alle Vorschläge wie "Topfschlagen".

[Bjoerk]

Ok. Hier:

Delphi-Quellcode:

  TFloatPoint = record
    X, Y: double;
    procedure Clear;
  end;

  TFloatPoints = class
  private
    FItems: array of TFloatPoint;
..
 

function TFloatPoints.Add(const Value: TFloatPoint): integer;
begin
  Result := FCount;
  if Assigned(FOnFloatPointsAdd) then // TSnapPointsFinderThread;
    FOnFloatPointsAdd(Value)
  else
    Ins(Result, Value);
end;

procedure TFloatPoints.Ins(const Index: integer; const Value: TFloatPoint);
begin
  if (Index >= 0) and (Index <= FCount) then
  begin
    if FCount = FCapacity then
      SetCapacity(FCapacity + DeltaCapacity);
    if Index < FCount then
    begin
      Move(FItems[Index], FItems[Index + 1], (FCount - Index) * SizeOf(TFloatPoint));
      FillChar(FItems[Index], SizeOf(TFloatPoint), 0);
    end;
    FItems[Index] := Value;
    Inc(FCount);
  end;
end;

procedure TFloatPoints.Delete(const Index: integer);
begin
  if (Index >= 0) and (Index < FCount) then
  begin
    Dec(FCount);
    if Index < FCount then
    begin
      Move(FItems[Index + 1], FItems[Index], (FCount - Index) * SizeOf(TFloatPoint));
      FillChar(FItems[FCount], SizeOf(TFloatPoint), 0);
    end;
    FItems[FCount].Clear;
  end;
end;

[Namenloser]

Das ist deshalb so langsam, weil du für jeden Punkt im Schnitt die Hälfte oder so aller anderen Punkte durchläufst, um die Koordinaten zu vergleichen. Dadurch explodiert natürlich die Laufzeit bei größerem n. Du musst also das Nachschlagen von in der Nähe liegenden Punkten beschleunigen.

Wenn die Werte der Koordinaten alle in der gleichen Größenordnung sind, wäre eine Möglichkeit, sie durch Multiplikation mit einer geeigneten Konstante in Integer konvertieren, und diese dann einfach in eine Hashmap einzufügen (ggf. mehrfach wegen unterschiedlicher Rundung).

Eine andere Möglichkeit, die auch ohne Integer-Konvertierung funktionieren würde, wäre ein K-d-Baum.

[Amateurprofi]

Versuch es mal so:

Bei ca. 100000 Einträgen wird am Schluss ca. 100000*100000 mal SameValue aufgerufen.
Die Idee ist, in TFloatPoints.InList, wiederholtes laden des Items (das mit allen Einträgen der Liste verglichen wird) und Epsilon in die FPU Register zu vermeiden und auch die Zugriffe auf die Items der Liste zu beschleunigen.
Ein kurzer Test verlief erfolgreich.
Ich habe 1000 Einträge mit Zufallswerten von X und Y im Bereich 0 bis 9 erzeugt.
Somit können nur max 100 verschiedene Einträge vorhanden sein.
Nach Aufruf von RemoveDuplicates enthielt die Liste dann auch 100 statt vorher 1000 Einträge.
Auf das Clear für "gelöschte" Einträge habe ich verzichtet, denn erstens kann auf diese Einträge eh nicht zugegriffen werden (bzw. sollte nicht zugegriffen werden können) und zweitens weiß ich nicht, was Clear macht. Ich vermute TFloatPoint.Clear setzt X und Y = 0. Da aber X=0 und Y=0 auch gültige Koordinaten sind, sehe ich da keine Vorteile.

Ich habe übrigens ein

Delphi-Quellcode:

type TAFloatPoint=Array of TFloatPoint;

eingefügt und die Definition von FItems auf

Delphi-Quellcode:

FItems:TAFloatPoint;

geändert.

Delphi-Quellcode:

procedure TFloatPoints.RemoveDoubles;

FUNCTION InList(List:TAFloatPoint; const Item:TFloatPoint; Count:Integer):Boolean;
const Epsilon:Double=1E-4;
asm
            fld      Epsilon        // st0=Epsilon
            fld      QWord [edx]    // st0=X, st1=Epsilon
            fld      QWord [edx+8]  // st0=Y, st1=X, st2=Epsilon
@Loop:      fld      QWord [eax]    // st0=List.X, st1=Y, st2=X, st3=Epsilon
            fsub     st,st(2)       // st0=List.X-X
            fabs
            fcomip   st,st(3)       // List.X-X vs. Epsilon
            ja       @Next          // Verschieden (Abs(List.X-X) > Epsilon)
            fld      QWord [eax+8]  // st0=List.Y, st1=Y, st2=X, st3=Epsilon
            fsub     st,st(1)       // st0=List.Y-Y
            fabs
            fcomip   st,st(3)       // List.X-X vs. Epsilon
            jbe      @True          // Gleich (Abs(List.X-X) <= Epsilon)
@Next:      add      eax,16
            sub      ecx,1
            jnz      @Loop
            xor      al,al
            jmp      @End
@True:      mov      al,1
@End:       ffree    st(2)
            ffree    st(1)
            ffree    st
end;
var
   I,J: integer;
begin
   if FCount<2 then Exit;
   J:=1;
   for I:=1 to FCount-1 do
      if not InList(FItems,FItems[I],J) then begin
         FItems[J]:=FItems[I];
         Inc(J);
      end;
   FCount:=J
end;

[Dejan Vu]

1. Vorschlag: Sortiere die Liste und dann lösche beim einmaligen Durchlaufen alle Punkte raus, die "gleich! dem vorherigen Wert sind. Das 'löschen' geht so, das man das entstehenden Loch einfach mit dem nächsten Element auffüllt. etwa so:

Delphi-Quellcode:

procedure RemoveDuplicates (aList : TSomeList);
Var
  i,j : Integer;

Begin
  aList.Sort();
  j := 0;
  for i := 1 to aList.Length - 1 do 
    if aList[i].CompareTo(aList[j]) <> TCompareResult.Equal then begin 
      inc(j);
      aList[j] := aList[i];
    end;

  aList.Length := j;
end;

Sortieren ist vom Aufwand O(n log n), ergo ist das Verfahren vom gleichen Aufwand. Besser als O(n^2), wie beim zu optimierenden Verfahren.
Es geht aber noch schneller: Verwende dazu eine Dictionary und übertrage mit o.g. Pattern nur die Werte, die noch nicht in der Dictionary sind.

Delphi-Quellcode:

procedure RemoveDuplicates<TElement> (aList : TSomeList);
Var
  i,j : Integer;
   lookup : THashMap<TElement>;
Begin
  j := 0;
  lookup := THashmap<TElement>.Create;
  try
    for i := 1 to aList.Length - 1 do 
      if not lookup.Contains(aList[i]) then begin 
        lookup.Add(aList[i]);
        inc(j);
        aList[j] := aList[i];
      end;
  finally
    lookup.Free;
  end;
  aList.Length := j;
end;

K.a. ob es in Delphi eine THashmap gibt. Das ist eine Dictionary, aber nur für Schlüssel (ohne Nutzdaten)

Der Aufwand ist hier O(n), wenn das Nachschlagen ('Contains') und Anfügen ('Add') an eine THashmap vom Aufwand O(1) ist. Das sollte aber so sein, da hier idR Hashlisten zum Einsatz kommen. Wegen der Floatwerte muss der Comparator der THashmap vermutlich angepasst werden.

[Jasocul]

Vielleicht wäre es ja auch möglich, die doppelten Elemente gar nicht erst in die Liste aufzunehmen?
Also beim Einlesen der Daten in die Liste schon prüfen, ob der Wert schon enthalten ist.

[Dejan Vu]

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

[himitsu]

Zitat:

Zitat von Dejan Vu (Beitrag 1282581)

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

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

Zitat von Bjoerk (Beitrag 1282590)

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

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

Zitat von Jasocul (Beitrag 1282588)

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

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.

[Bjoerk]

Zitat:

Zitat von Horst_ (Beitrag 1282598)

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

Thanx. Das war das wo ich auf dem Schlauch stand. :oops:

Delphi-Quellcode:

function TFloatPoints.SortCompare(const I, J: integer): integer;
const
  Eps = 1E-4;
var
  A, B: TFloatPoint;
begin
  A := FItems[I];
  B := FItems[J];
  if CompareValue(A.X, B.X, Eps) > 0 then
    Result := 1
  else
    if CompareValue(A.X, B.X, Eps) < 0 then
      Result := -1
    else
      if CompareValue(A.Y, B.Y, Eps) > 0 then
        Result := 1
      else
        if CompareValue(A.Y, B.Y, Eps) < 0 then
          Result := -1
        else
          Result := 0;
end;

[Dejan Vu]

Machs doch so ('Sign' müsste in der Unit Math sein'). 'Sign' ist eigentlich gar nicht notwendig.

Delphi-Quellcode:

function TFloatPoints.SortCompare(const I, J: integer): integer;
const
   Eps = 1E-4;
var
   A, B: TFloatPoint;
begin
   A := FItems[I];
   B := FItems[J];
   Result := Sign(CompareValue(A.X, B.X, Eps));
   If Result = 0 then 
     Result := Sign(CompareValue(A.Y, B.Y, Eps));
End;

[himitsu]

CompareValue gibt auch nur -1, 0 oder +1 raus, also genau das, was SortCompare als Result benötigt, womit man sich das Sign sparen kann.

[Bjoerk]

Zitat:

Zitat von Dejan Vu (Beitrag 1282606)

Machs doch so [..]

Stimmt. Nochmal zum Geschwindigkeitsproblem. Ob einfache Schleife plus Quicksort schneller ist als Summe N Durchläufe wage ich allerdings zu bezweifeln. Ich lass es aber jetzt erst mal so. Von Hashmaps hab ich leider keine Ahnung und auch leider Keine Zeit weiter hieran zu arbeiten. Thanx!

Delphi-Quellcode:

function TFloatPoints.SortCompare(const I, J: integer): integer;
const
  Eps = 1E-4;
begin
  Result := CompareValue(FItems[I].X, FItems[J].X, Eps);
  if Result = 0 then
    Result := CompareValue(FItems[I].Y, FItems[J].Y, Eps);
end;

procedure TFloatPoints.QuickSort(L, R: integer);
var
  I, J, K: integer;
begin
  repeat
    I := L;
    J := R;
    K := (L + R) shr 1;
    repeat
      while SortCompare(I, K) < 0 do
        Inc(I);
      while SortCompare(J, K) > 0 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;

procedure TFloatPoints.Sort;
begin
  if FCount > 1 then
    QuickSort(0, FCount - 1);
end;

(*
procedure TFloatPoints.RemoveDoubles;
var
  I, J: integer;
begin
  for I := FCount - 2 downto 0 do
    for J := FCount - 1 downto I + 1 do
      if Util_SameFloatPoint(FItems[I], FItems[J]) then
        Delete(J);
end;
*)

procedure TFloatPoints.RemoveDoubles;
var
  I: integer;
begin
  Sort;
  for I := FCount - 1 downto 1 do
    if Util_SameFloatPoint(FItems[I], FItems[I - 1]) then
      Delete(I);
end;

[Mavarik]

Zitat:

Zitat von Bjoerk (Beitrag 1282556)

Ok. Hier:

Delphi-Quellcode:

procedure TFloatPoints.Ins(const Index: integer; const Value: TFloatPoint);
begin
  if (Index >= 0) and (Index <= FCount) then
  begin
    if FCount = FCapacity then
      SetCapacity(FCapacity + DeltaCapacity);
    if Index < FCount then
    begin
      Move(FItems[Index], FItems[Index + 1], (FCount - Index) * SizeOf(TFloatPoint));
      FillChar(FItems[Index], SizeOf(TFloatPoint), 0);
    end;
    FItems[Index] := Value;
    Inc(FCount);
  end;
end;

procedure TFloatPoints.Delete(const Index: integer);
begin
  if (Index >= 0) and (Index < FCount) then
  begin
    Dec(FCount);
    if Index < FCount then
    begin
      Move(FItems[Index + 1], FItems[Index], (FCount - Index) * SizeOf(TFloatPoint));
      FillChar(FItems[FCount], SizeOf(TFloatPoint), 0);
    end;
    FItems[FCount].Clear;
  end;
end;

Immer mit einem Move die komplette Liste um eins verschieben? Autsch.

Nimm Dir noch ein Flag Del : boolean;
Und dann wenn Du fertig bist einmal das Array ohne die gelöschten in ein neues kopieren.

Mavarik

[Horst_]

Hallo,

da wäre eine .Copy Funktion wohl besser.

Delphi-Quellcode:

j := 0;
Für i von 1 bis Fcount  
  falls Liste[i] <> Liste[i-1] dann
    kopiere Liste[i-1] -> Liste[j]
    erhöhe j
Setze Fcount auf j

Vielleicht muss man den letzen nochmals gesondert untersuchen, aber es geht ja nur ums Prinzip

Gruß Horst

[Dejan Vu]

Schau Dir mal meine Vorschläge an:
http://www.delphipraxis.net/1282576-post8.html

Zitat:

Zitat von Bjoerk (Beitrag 1282610)

Ob einfache Schleife plus Quicksort schneller ist als Summe N Durchläufe wage ich allerdings zu bezweifeln. Ich lass es aber jetzt erst mal so. Von Hashmaps hab ich leider keine Ahnung und auch leider Keine Zeit weiter hieran zu arbeiten. Thanx!

Na, ich würde nicht wagen, das zu bezweifeln, sondern belegen, das es langsamer ist.

Ich werde heute abend mal ein paar benchmarks posten.

[Bjoerk]

Ok. Aber nur wenn du Zeit und Lust hast. Möchte das Thema auch nicht überstrapazieren? Hier (Auszug zusammenkopiert).

[Dejan Vu]

So, das hier ist 20x(*) schneller als deine Methode.

Delphi-Quellcode:

Procedure TFloatPoints.FastRemoveDoubles;
Var
  i,j : Integer;

Begin
  sort;
  j := 0;
  for i:=1 to Count-1 do
    if not SameFloatPoint(Fitems[i],FItems[j]) then begin
      inc(j);
      Fitems[j] := fItems[i];
    End;
  FCount := j;
End;

Die Variante mit der Hashmap hab ich mir geschenkt. Da dürften erst bei > 1 Mio spürbare Unterschiede auffallen: Quicksort ist ja schön schnell.

Davon abgesehen ist auch in 'AddPoints' noch mächtig Luft nach oben.

Delphi-Quellcode:

procedure TFloatPoints.FastAddPoints(Value: TFloatPoints);
var
  newCount, newCapacity : integer;

begin
  newCount := Self.Count + Value.Count;
  if newCount = Self.Count then exit;
  while fCapacity < newCount do fCapacity := fCapacity + DeltaCapacity;
  SetCapacity(fCapacity);
  Move(value.FItems[0],FItems[Count+1], value.Count*SizeOf(value[0]));
  self.FCount := newCount;
end;

Den Rest habe ich mir nicht mehr angeschaut, aber ich frage mich, wieso Du die Quellen von TList kopiert hast, wo Du doch dein TFloatPoint einfach in eine TList packen kannst. Dann kannst du dir das ganze Gedöns sparen. Na ja. Mach wie Du denkst.


(*) 20x bei 100.000 Elementen. Sind es mehr, ist der Unterschied noch drastischer. Sind es weniger, dann ist der Unterschied auch nicht mehr so hoch.

[Bjoerk]

Nicht schlecht. Aber, was soll das if newCount = Self.Count then exit in der FastAddPoints?

[himitsu]

Das Verhalten von Capacity und blockweiser Vergrößerung ist doch bereits im TList eingebaut?
PS: TList.Insert

Zitat:

Zitat von Dejan Vu (Beitrag 1282672)

So, das hier ist 20x schneller als deine Methode.

Da müssen dringend ein paar Sleep in den Code, denn es soll ja nur doppelt so schnell werden!

[Dejan Vu]

Zitat:

Zitat von Bjoerk (Beitrag 1282673)

Nicht schlecht. Aber, was soll das if newCount = Self.Count then exit in der FastAddPoints?

Na, wenn es nix zu tun gibt, dann tschüss.

[Bjoerk]

Das soll doch analog AddStrings sein. Die Zeile muß natürlich raus. :)

[Dejan Vu]

Ok. Die Sleep-Anweisungen von Himitsu rein und dafür die Abfrage, ob es etwas zu tun gibt, raus.

[Bjoerk]

Hab ich schon eingebaut. Sonst wäre mein Software ja so schnell wie "richtige" Software. :mrgreen:

[Dejan Vu]

Du bist einfach der Software-Gott.

[Namenloser]

Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.

Stellt euch mal folgende Punktkonstellation vor:

Code:

            A B





            C

Die Koordinaten sind z.B. A(10.0, 2.0), B(10.001, 2.0), C(10.0, 5.0). A und B sollen im Rahmen des Epsilons als identisch gelten.

Wenn du das jetzt lexikographisch nach sortierst (nach der X-Koordinate zuerst), dann kommt die Reihenfolge A, C, B heraus. A und B werden also nie als Duplikate erkannt, weil sie nach der Sortierung nicht hintereinander stehen.

Das funktioniert leider so nur im Eindimensionalen.

Im Mehrdimensionalen braucht man andere Indexstrukturen, wie K-d-Bäume. Genau für solche Anwendungsfälle, wie die nächsten Nachbarn eines Punktes suchen, wurden die erfunden.

[Bjoerk]

Zitat:

Zitat von Dejan Vu (Beitrag 1282688)

Du bist einfach der Software-Gott.

Wo du grad zu Höchstform aufläufst. Ich poste mal noch ein anderes Problem.

[Bjoerk]

Zitat:

Zitat von Namenloser (Beitrag 1282690)

Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.

Ok. Was denkst du denn über # 16?

Edit: Vergiss es. Genasu so falsch..

Hast du ein Beispiel für K-d-Bäume?

[Namenloser]

Ich habe leider kein Beispiel dafür. Es muss aber auch kein K-d-Baum sein, es gibt ja noch andere mehrdimensionale Indexstrukturen.

Die einfachste wäre hier denke ich die Hashmap-Lösung. Im Grunde ist die Idee, dass man ein grobes Raster über die Punkte legt, und pro Kästchen abspeichert, welche Punkte darin liegen:

Code:

|-----|-----|-----|---
|x    |     |     |
|     |     |     |
|-----|-----|-----|---
|     | xx  |     |
|     |     |     |
|-----|-----|-----|---
|     |     |    x|
|    x|x    |     |
|-----|-----|-----|---

(Sorry, die DP zerstört mal wieder das Layout, aber ich denke es ist klar, wie es gemeint ist.)

Dann muss man, um „identische“ Punkte zu finden, nur noch die Punkte aus dem gleichen Kästchen und aus den 8 Nachbarkästchen überprüfen.

Im Grunde braucht man nicht mal eine Hashmap, sondern ein einfaches 2D-Array tut es auch, ist nur u.U. weniger speichereffizient, wenn es größere, Bereiche gibt, die leer stehen.

Ein genereller Nachteil dieser Lösung ist, dass man die Kästchengröße irgendwie von Hand tunen muss.