Duplikate entfernen

Boldar · Verfasst: Sa 06.02.10 20:05

Hallo,
Ich suche eine Methode, mit der Duplikate aus einem wie folgt aufgebautem Array entfernt werden:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

type TPointex = record
  x, y: real;
end;
type TLine = record
  A, B: TPointex;
end;
type TLines = array of TLine;

Der Eintrag soll natürlich nur entfernt werden, wenn Anfangs- und Endpunkt der Linie gleich sind.

Am besten bräuchte ich eine Methode mit linearer Laufzeit.
Gibt es die?
Würde eine Umstellung des Arrays auf Pointer, also so:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

type TPointex = record
  x, y: real;
end;
type TLine = record
  A, B: TPointex;
end;
type PLine = TLine^
type TLines = array of PLine;

Sinn machen, weil dann nur die Pointer kopiert werden müssten?

mfg Boldar

Kha · Verfasst: Sa 06.02.10 20:29

Boldar hat folgendes geschrieben :

Gibt es die?

Ja, wenn du eine Lookup-Struktur mit Suche und Hinzufügen in O(1) hast, also z.B. eine Hash-Tabelle.
Der Algorithmus ist dann trivial:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

    static IEnumerable<TSource> CreateDistinctIterator<TSource> (IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
    {
      var items = new HashSet<TSource> (comparer);
      foreach (var element in source) {
        if (! items.Contains (element)) {
          items.Add (element);
          yield return element;
        }
      }
    } // (c) Mono

Boldar hat folgendes geschrieben :

Sinn machen, weil dann nur die Pointer kopiert werden müssten?

Wäre zumindest bei TLine sicher keine schlechte Idee. Wobei ich persönlich gleich zu Klassen greifen würde

.

_________________
>λ=

Horst_H · Verfasst: So 07.02.10 17:37

Hallo,

ist die Datenstruktur nicht etwas unpassend?
Mit einer Punkte Liste waere es etwas kompakter.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Type
  TPointex = record
    x, y: double;
  end;
  tPointList = array of TPointex;

  tPointIdx : integer;
  
  TLine = record
            Von_A,Nach_B: tPointIdx;
          end;
  TLines = array of TLine;

Das ist zwar indirekter im Zugriff, aber man braucht nicht staendig Fliesskommazahlen zu vergleichen/hashen , sondern nur die Nummern der Punkte.
Diese Punkteliste koennte auch schon nach x und bei gleichem x nach y sortiert sein ( links oder unter ) .Zudem kann man leichter einen Punkt veraendern und musz nicht alle Linien wegen dieser Aenderung durchsuchen.
Es ist ja auch die Frage , ob eine Linie von A nach B auch das gleiche wie eine Linie von B nach A sein soll, dann koennte man einfach A links oder unter B waehlen. Im PunkteIdx Von_A < Nach_B.

Grusz Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme