Seite 1 von 2
Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 18:38
von ThoPie
Hallo,
ich lese eine Datenbank in eine LinkedList ein. In der LinkedList ist u.a. ein Integer-Feld. Nach dem Einlesen sollen evtl. auftretende Duplikate bzgl. dieses Integer-Feldes gelöscht werden. Eine nachträglich Neusortierung der LinkedList ist leider nicht möglich, da die ursprüngliche Sortierung erhalten bleiben muss.
Also z.B. aus 1,4,2,3,4,1,6 soll 1,4,2,3,6 werden.
Vielen Dank für eure Bemühungen.
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 18:47
von gnasen
du könntest die Liste kopieren, die kopierte Liste sortieren und doppelte aussortieren. Diejenigen, die du aussortierst, kannst du dann einfach in der original Liste löschen.
Zum identifizieren könntest du einfach die Pointer der original Elemente zusätzlich in die kopierte Liste schreiben.
Vllt nicht die performanteste, aber einfachste Lösung.
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 18:53
von STARGÅTE
Hier mein Beispiel:
Er legt eine Interne Index-Liste an und vergleicht diese mit der Original-Liste,
bei mehrfachen auftauchen eines Indizes in der Original Liste wird das Element gelöscht:
Code: Alles auswählen
Structure Irgendwas
Index.i
Long.l
String$
;[...]
EndStructure
Procedure UniqueList(List LinkedList.Irgendwas())
Protected NewList Index.i()
ForEach LinkedList()
ForEach Index()
If LinkedList()\Index = Index()
DeleteElement(LinkedList())
Break
EndIf
Next
AddElement(Index()) : Index() = LinkedList()\Index
Next
EndProcedure
NewList Zufall.Irgendwas()
For n = 1 To 20
AddElement(Zufall())
Zufall()\Index = Random(9)
Next
Debug "Vorher"
ForEach Zufall()
Debug Zufall()\Index
Next
UniqueList(Zufall())
Debug "Nachher"
ForEach Zufall()
Debug Zufall()\Index
Next
Vorher
5
2
2
6
0
1
7
3
8
3
0
9
9
6
8
2
9
9
3
7
Nachher
5
2
6
0
1
7
3
8
9
Die Structure einfach anpassen und die Procedure ggf. anpassen
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 19:07
von ThoPie
Vielen Dank.
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 20:01
von Kiffi
man kann auch 'ne Map dafür nehmen:
Code: Alles auswählen
; aus 1,4,2,3,4,1,6 soll 1,4,2,3,6 werden.
NewList MyLL()
AddElement(MyLL()) : MyLL() = 1
AddElement(MyLL()) : MyLL() = 4
AddElement(MyLL()) : MyLL() = 2
AddElement(MyLL()) : MyLL() = 3
AddElement(MyLL()) : MyLL() = 4
AddElement(MyLL()) : MyLL() = 1
AddElement(MyLL()) : MyLL() = 6
NewMap myMap()
ForEach MyLL()
If FindMapElement(myMap(), Str(MyLL()))
DeleteElement(MyLL())
Else
AddMapElement(myMap(),Str(MyLL()))
EndIf
Next
ForEach MyLL()
Debug MyLL()
Next
Grüße ... Kiffi
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 22:11
von AND51
Die schnellste Methode eine Liste zu sortieren besteht darin, jedes Element mit allen
nachfolgenden Elementen zu vergleichen.
Dabei spielt es auch kene Rolle, ob es sich um Zahlen oder Strings handelt.
Streng genommen ist dies sogar der einzig "richtige" Weg, denn:
Beim Sortieren und anschließenden Filtern wird die Reihenfolge der Daten verändert;
beim erstellen einer Zweitliste zum Zwecke des Vergleichs wird doppelt so viel Speicher (und Zeit) benötigt;
beim Überführen einer LinkedList zu einer Map (Kiffi's beispiel) geht zusätzliche Zeit für die Konvertierung drauf.
Um jedes Element mit jedem nachfolgenden zu Vergleichen bedarf es einer ForEach-Schleife, die die Liste normal durchblättert. Bei jedem Element wird angehalten, die Position in der Liste gemerkt und mit allen nachfolgenden Elementen verglichen. Das macht die "While NextElement()"-Schleife (die zeitsparender Weise nur dann durchlaufen wird, wenn es noch nachfolgende Elemente gibt). Anschließend wird zum Ausgangselement zurückgesprungen, damit die ForEach-Schleife normal weiterblättern kann.
Das ganze sieht dann so aus:
Code: Alles auswählen
NewList MyLL()
AddElement(MyLL()) : MyLL() = 1
AddElement(MyLL()) : MyLL() = 4
AddElement(MyLL()) : MyLL() = 2
AddElement(MyLL()) : MyLL() = 3
AddElement(MyLL()) : MyLL() = 4
AddElement(MyLL()) : MyLL() = 1
AddElement(MyLL()) : MyLL() = 6
Procedure DublettenFiltern(List Liste())
ForEach Liste()
Protected *vergleichsElement=@Liste() ; Pointer und Wert des aktuellen
Protected vergleichsWert=Liste() ; Elements speichern und...
While NextElement(Liste()) ; ...mit allen NACHFOLGENDEN Elementen vergleichen
If Liste() = vergleichsWert
DeleteElement(Liste(), 1) ; bei Fund Dublette löschen
EndIf
Wend ; diese Schleife blättert die LinkedList bis zum Ende durch
ChangeCurrentElement(Liste(), *vergleichsElement) ; zum Ausgangselement zurückkehren, damit ForEach zum nächsten Vergleichselement springt
Next
EndProcedure
Debug "vorher"
ForEach MyLL()
Debug MyLL()
Next
DublettenFiltern(MyLL())
Debug "nachher"
ForEach MyLL()
Debug MyLL()
Next
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 22:45
von edel
@Kiffi
Dann wuerde ich mir aber doch gleich die Liste schenken und nur die Map nehmen, da braucht man auch nix filtern
Re: Duplikate aus LinkedList entfernen
Verfasst: 26.10.2009 23:51
von Kiffi
edel hat geschrieben:Dann wuerde ich mir aber doch gleich die Liste schenken und nur die Map nehmen, da braucht man auch nix filtern
stimmt auch wieder
Grüße ... Kiffi
Re: Duplikate aus LinkedList entfernen
Verfasst: 27.10.2009 14:36
von dige
Ich würde die Struktur um ein weiteres Feld 'lfn' erweitern,
in dem die Originalsoritierung gespeichert wird 1...n
Dann nach dem besagten Integer Feld mit SortStructuredList
sortieren lassen und alle Elemente mit gleichem Nachfolger
löschen. Anschliessend über das Feld 'lfn' die Originalreihenfolge
wiederherstellen.
Sollte am performantesten sein..
Re: Duplikate aus LinkedList entfernen
Verfasst: 27.10.2009 17:30
von AND51
dige hat geschrieben:Ich würde die Struktur um ein weiteres Feld 'lfn' erweitern,
in dem die Originalsoritierung gespeichert wird 1...n
Dann nach dem besagten Integer Feld mit SortStructuredList
sortieren lassen und alle Elemente mit gleichem Nachfolger
löschen. Anschliessend über das Feld 'lfn' die Originalreihenfolge
wiederherstellen.
Sollte am performantesten sein..
Doch AND51 hat geschrieben:Die schnellste Methode eine Liste zu sortieren besteht darin, jedes Element mit allen nachfolgenden Elementen zu vergleichen.
Du findest also das hinzufügen eines weiteren Strukturfeldes, das Sortieren nach diesem Feld, das Filtern und ein Zurücksortieren nach dem Strukturfeld performanter als nur einen einfachen Filterdurchlauf?