Doppel schnell aus Liste löschen.

[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
type TAFloatPoint=Array of TFloatPoint; eingefügt und die Definition von FItems auf
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 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.

[Mavarik]

Zitat von Bjoerk:

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

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.