Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Duplikate entfernen
Boldar - Sa 06.02.10 20:05
Titel: Duplikate entfernen
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:
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 - 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:
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;
}
}
} |
| 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 - So 07.02.10 17:37
Hallo,
ist die Datenstruktur nicht etwas unpassend?
Mit einer Punkte Liste waere es etwas kompakter.
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
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!