Doppel schnell aus Liste löschen.

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

[Dejan Vu]

Zitat von Bjoerk:

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.

[himitsu]

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

Zitat von Dejan Vu:

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!