Doppel schnell aus Liste löschen.

[Bjoerk]

Zitat von Horst_:

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.

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 von Dejan Vu:

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

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