AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Doppel schnell aus Liste löschen.

Ein Thema von Bjoerk · begonnen am 7. Dez 2014 · letzter Beitrag vom 14. Dez 2014
Antwort Antwort
Seite 1 von 9  1 23     Letzte »    
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#1

Doppel schnell aus Liste löschen.

  Alt 7. Dez 2014, 22:20
Delphi-Version: 2007
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.)
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;

Geändert von TBx (11. Dez 2014 um 13:11 Uhr) Grund: Titel korrigiert
  Mit Zitat antworten Zitat
Jens01

Registriert seit: 14. Apr 2009
673 Beiträge
 
#2

AW: Doppel schnell aus Lise löschen.

  Alt 7. Dez 2014, 22:43
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.
Achtung: Bin kein Informatiker sondern komme vom Bau.

Geändert von Jens01 ( 7. Dez 2014 um 22:51 Uhr)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#3

AW: Doppel schnell aus Lise löschen.

  Alt 7. Dez 2014, 23:03
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.

Geändert von Bjoerk ( 7. Dez 2014 um 23:08 Uhr) Grund: Edit
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.077 Beiträge
 
Delphi XE2 Professional
 
#4

AW: Doppel schnell aus Lise löschen.

  Alt 7. Dez 2014, 23:09
Es wäre hilfreich, zu wissen wie TFloatPoint, TFloatPoints und Util_SameFloatPoint definiert sind.
Ohne diese Informationen sind alle Vorschläge wie "Topfschlagen".
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#5

AW: Doppel schnell aus Lise löschen.

  Alt 7. Dez 2014, 23:16
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;

Geändert von Bjoerk ( 7. Dez 2014 um 23:25 Uhr) Grund: Code ergänzt
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#6

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 01:27
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.
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.077 Beiträge
 
Delphi XE2 Professional
 
#7

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 02:57
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;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#8

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 07:53
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.
  Mit Zitat antworten Zitat
Benutzerbild von Jasocul
Jasocul

Registriert seit: 22. Sep 2004
Ort: Delmenhorst
1.355 Beiträge
 
Delphi 11 Alexandria
 
#9

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 08:07
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.
Peter
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#10

AW: Doppel schnell aus Liste löschen.

  Alt 8. Dez 2014, 08:24
Dann hättest Du -rein theoretisch- das gleiche Performanceproblem bzw. Optimierungspotential
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 9  1 23     Letzte »    


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 15:07 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz