Doppel schnell aus Liste löschen.

[Bjoerk]

Ich hab mehrere Tests mit dem Code #47 durchgeführt. Scheint zu stimmen. Weiß aber nicht wieso?

Falls jemand probieren möchte (Testform):

[Namenloser]

@Dejan Vu: Das war jetzt nicht auf das Beispiel bezogen sondern allgemein.

Solange es immer nur Paare von zusammengehörenden Punkten gibt, sollte es wohl kein Problem geben. Problematisch könnte es aber werden, wenn es mehr als zwei zusammengehörige Punkte gibt.

Könnte sein, dass du z.B. irgendwie in einer Reihe die Punkte a b c d hast, wobei jeder Punkt zu seinen Nachbarn, und nur zu seinen Nachbarn, „gleich“ ist. Dann könnte es womöglich passieren, dass der Algorithmus die Punkte durcheinanderwürfelt und a c b d daraus macht oder so, sodass anschließend wieder keine Duplikate erkannt werden. Genau überlegt habe ich es mir nicht, ich warne nur.

Allerdings ist eh etwas unklar, was in einem solchen Fall passieren soll, wie du ja auch schon angemerkt hast.

[Dejan Vu]

Perfekt ist das Verfahren nicht. Aber wir verstehen es wenigstens. Bei so einem Kd-Baum oder spacial indexes müsste ich mich erst mal reinfräsen.

Zitat von Bjoerk:

Ich hab mehrere Tests mit dem Code #47 durchgeführt. Scheint zu stimmen. Weiß aber nicht wieso?

Also darauf würde ich mich jetzt mal nicht verlassen. Der zweite Sortiervorgang könnte die Ordnung durcheinanderbringen (instabiles Sortierverfahren).

Klappt mein Code nicht? Immerhin wird nur 1x sortiert und schnell ist er auch und ich glaube auch, das er korrekt ist . Und hör mit dem 'Delete' auf, das ist doch Grottenlangsam.

[Bjoerk]

Hier nein. Das Delete ist der Witz an der Sache. Sonst würde es nicht funktionieren. SortX und SortY müssen auf verschiedene Listen angewendet werden, sonst hat man nur SortY (Siehe auch Namenloser).

[Horst_]

Hallo,

da bin ich missverstanden worden...
Beim Versuch mit kleinem eps

Delphi-Quellcode:

procedure TFloatPointsTestForm.RemoveDoublesButtonClick(Sender: TObject);
const
  Eps = 1E-3;

steigt das Programm sofort aus.

Gruß Horst

[Bjoerk]

Nein, ich hatte nur das als letzte Möglichkeit gesehen um nicht groß am Code ändern zu müssen. Gut. Dann wäre das jetzt geklärt, daß es auch so nicht geht. Danke Horst. Allerdings steigt das Progamm nicht aus, sondern eine MessageBox wird angezeigt, daß FLoatPoints.RemoveDoubles nicht erfolgreich war. Dann kann man das mit der Sort Variante hier vergessen. Daß ich sattdessen im Code nun auf if List.IndexOf(Value) < 0 prüfe bevor Elemente hinzugefügt werden hab ich ja schon geschrieben.

Edit: Man könnte auch zuerst nach x sortieren und in Listen mit gleichen X splitten und dann nach y sortieren und später wieder zusammenfügen. Hab jetzt aber kein Bock mehr auf das Thema (zumindest heute nicht mehr).

[EgonHugeist]

Zitat von Bjoerk:

Ok. Thanx. Schau ich mir an.

Als letzter Versuch fäll tmir noch das ein? Der Quicksort ist ja unfassbar schnell. Ist das so korrekt?

HybridSort oder RadixSort? Es geht so einiges, wenn man keinen zusätzlichen Code oder Speicher-Verbrauch in Betracht zieht.

[Bjoerk]

Ok. Sagt mir aber leider nix.

Hab doch noch Bock.

Ungetestet:

Delphi-Quellcode:

procedure TFloatPoints.RemoveDoubles;
const
  Eps = 1E-4;
var
  X: double;
  I, J: integer;
  NewList, SortList: TFloatPoints;
begin
  NewList := TFloatPoints.Create;
  try
    SortList := TFloatPoints.Create;
    try
      SortByX;
      I := 0;
      while I < FCount do
      begin
        SortList.Clear;
        X := FItems[I].X;
        while (I < FCount) and (SameValue(X, FItems[I].X, Eps)) do
        begin
          SortList.Add(FItems[I]);
          Inc(I);
        end;
        SortList.SortByY;
        for J := SortList.Count - 1 downto 1 do
          if SameFloatPoint(SortList[J], SortList[J - 1]) then
            SortList.Delete(J);
        NewList.AddPoints(SortList);
      end;
      Assign(NewList);
    finally
      SortList.Free;
    end;
  finally
    NewList.Free;
  end;
end;

[EgonHugeist]

Zitat von Bjoerk:

Ok. Sagt mir aber leider nix.

Macht nix, google es mal. Radix baut eine zweite Liste auf(Speicher x2) aber die Raten sind unglaublich! Es existieren so einige Radix Übersetzunengen.
Alexandr's HybridSort schlägt die "kleine/niedliche" QuickSort Variante um's 1,5fache. Radix dagegen ... kommt auf den Fall an.. x10 oder viiiel mehr!

@Nameloser: QSort ist in der Lage "unendlich" sogar mit Zufalls Ergebnissen zu arbeiten! e.g. FastCode-Project -> SortBV(Ein validation Test betrachtet diese Variante), Alle noch X-mal schnelleren Interpretationen/Replacements können jedoch nur mit "exakten" Ergebnissen umgehen.

[Dejan Vu]

Zitat von Dejan Vu:

Klappt mein Code nicht?

Zitat von Bjoerk:

Hier nein.

Echt? Geht Doch.

Delphi-Quellcode:

Function ComparePoints(Const P1, P2 : TFloatPoint) : Integer;
Begin
  Result := SortCompareX(p1,p2);
  if Result = 0 then REsult := SortCompareY(p1,p2);
End;

procedure TFloatPoints.FastRemoveDoubles;
var
  i,j : Integer;

Begin
  QuickSort(0,Count-1,ComparePoints);
  j:=0;
  For i:=1 to Count - 1 do
    if ComparePoints(Fitems[i],fItems[j])<>0 then begin
      inc(j);
      fItems[j] := fItems[i];
    end;
  fCount := j;
End;

Oder hatte ich was anderes geschrieben?

Im älteren Code von dir schien aber die Quicksort-Methode nicht richtig zu sortieren, jedenfalls bei mir. Aber jetzt scheint alles in Ordnung zu sein.