Duplikate in einer Type Liste löschen

Übersicht

BlitzBasic

Allgemein

	EPS Betreff: Duplikate in einer Type Liste löschen	Mi, Aug 23, 2006 9:07 Antworten mit Zitat
Hi zusammen, ich habe eine Type Liste, sagen wir mal: Code: [AUSKLAPPEN] [EINKLAPPEN] Type MyType Field ID% Field MyString$ End Type ID ist ein Counterwert der bei jedem Eintrag anders ist. MyString ist ein als Beispiel mal ein String. Wie kann ich jetzt AM SCHNELLSTEN erkennen ob in der Typeliste mehrmals MyString$ vorkommt? Bis jetzt hab ich 2 For Each Schleifen ineinander verschachtelt und jeweils MyString miteinander verglichen. Bei einer Übereinstimmung hab ich dann noch geschaut ob ID unterschiedlich ist und wenn ja den Type Eintrag gelöscht. Ganz einfache Sache und funktioniert auch prima, aber bei über 1000 Einträgen dauert das ganze dann schon ein paar Sekunden, was auch verständlich ist, da sich das ganze ja potenziert durch die beiden Schleifen. Daher die Frage ob es einen cleveren Algo gibt der das ganze etwas beschleunigt. Sozusagen aus einem "Bubblevergleich" einen "Quickvergleich" oder noch schneller macht. Danke
mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier Man kann sich öfter als zweimal im Leben halb tot lachen.

EPS

Betreff: Duplikate in einer Type Liste löschen

Mi, Aug 23, 2006 9:07
Antworten mit Zitat

Hi zusammen,

ich habe eine Type Liste, sagen wir mal:

Code: [AUSKLAPPEN]

Type MyType
Field ID%
Field MyString$
End Type

ID ist ein Counterwert der bei jedem Eintrag anders ist. MyString ist ein als Beispiel mal ein String.

Wie kann ich jetzt AM SCHNELLSTEN erkennen ob in der Typeliste mehrmals MyString$ vorkommt?

Bis jetzt hab ich 2 For Each Schleifen ineinander verschachtelt und jeweils MyString miteinander verglichen. Bei einer Übereinstimmung hab ich dann noch geschaut ob ID unterschiedlich ist und wenn ja den Type Eintrag gelöscht.

Ganz einfache Sache und funktioniert auch prima, aber bei über 1000 Einträgen dauert das ganze dann schon ein paar Sekunden, was auch verständlich ist, da sich das ganze ja potenziert durch die beiden Schleifen.

Daher die Frage ob es einen cleveren Algo gibt der das ganze etwas beschleunigt. Sozusagen aus einem "Bubblevergleich" einen "Quickvergleich" oder noch schneller macht.

Danke

mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier

Man kann sich öfter als zweimal im Leben halb tot lachen.

	Dreamora	Mi, Aug 23, 2006 9:27 Antworten mit Zitat
Es gibt klevere Möglichkeiten, ja. Aber die setzen voraus, dass man schon Mal primär beim Einfügen den Kopf benutzt hat und nicht einfach stupid hinten anhängt. 1. Das ganze sortiert einfügen -> O(n) pro Element das du einfügst, sollte drin liegen 2. Wenn man beim einfügen sieht "ich bin schon drin" -> garnicht einfügen (alternativ kann man auch garnicht sortiert einfügen und dann Sortieralgo drüber laufen lassen. Damit kommt man algorithmisch besser weg, auch wenn da die Algorithmik leicht witzlos ist, da sie nicht von "babymengen" aus geht wo die Ausführung einzelner Operationen noch laufzeittechnisch zum tragen kommen ... )
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Mi, Aug 23, 2006 9:27
Antworten mit Zitat

Es gibt klevere Möglichkeiten, ja.
Aber die setzen voraus, dass man schon Mal primär beim Einfügen den Kopf benutzt hat und nicht einfach stupid hinten anhängt.

1. Das ganze sortiert einfügen -> O(n) pro Element das du einfügst, sollte drin liegen
2. Wenn man beim einfügen sieht "ich bin schon drin" -> garnicht einfügen

(alternativ kann man auch garnicht sortiert einfügen und dann Sortieralgo drüber laufen lassen. Damit kommt man algorithmisch besser weg, auch wenn da die Algorithmik leicht witzlos ist, da sie nicht von "babymengen" aus geht wo die Ausführung einzelner Operationen noch laufzeittechnisch zum tragen kommen ... Smile

)

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	BladeRunner Moderator	Mi, Aug 23, 2006 9:31 Antworten mit Zitat
Ansatz: Erster Durchlauf: Erstes Stringelement nehmen. Alle weiteren werden mit diesem verglichen, falls identisch, gelöscht. Beim ersten Durchlauf einen Counter einrichten der die Gesamtzahl an Elementen erfasst. zweiter Durchlauf: 2es Element nehmen (einfach einen Counter hochzählen lassen der die ersten x elemente unberücksichtigt lässt). Selbes vorgehen wie bei eins, jedoch wird bei Löschen eines Elementes der Gesamtcounter reduziert. Wiederholen solange bis Anzahl verbleibender Elemente-1 als Startwert durchlaufen ist. Verglichen wird nur mit den Einträgen ab Handle aktueller Vergleichstring bis Ende (mit after), da der Rest der Liste ja schon vorüberprüft ist. Im Vergleich zur doppelten Schleife sollte schon eine spürbare Verschnellerung erkennbar sein, je nachdem wieviele "Doppeleinträge" es gibt kann sich die Zeit fast linearem Durchlauf annähern. Hoffe ich hab keinen Denkfehler drinne.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Mi, Aug 23, 2006 9:31
Antworten mit Zitat

Ansatz:
Erster Durchlauf: Erstes Stringelement nehmen. Alle weiteren werden mit diesem verglichen, falls identisch, gelöscht. Beim ersten Durchlauf einen Counter einrichten der die Gesamtzahl an Elementen erfasst.
zweiter Durchlauf: 2es Element nehmen (einfach einen Counter hochzählen lassen der die ersten x elemente unberücksichtigt lässt).
Selbes vorgehen wie bei eins, jedoch wird bei Löschen eines Elementes der Gesamtcounter reduziert.
Wiederholen solange bis Anzahl verbleibender Elemente-1 als Startwert durchlaufen ist.
Verglichen wird nur mit den Einträgen ab Handle aktueller Vergleichstring bis Ende (mit after), da der Rest der Liste ja schon vorüberprüft ist.

Im Vergleich zur doppelten Schleife sollte schon eine spürbare Verschnellerung erkennbar sein, je nachdem wieviele "Doppeleinträge" es gibt kann sich die Zeit fast linearem Durchlauf annähern.

Hoffe ich hab keinen Denkfehler drinne.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	EPS	Mi, Aug 23, 2006 9:58 Antworten mit Zitat
@Dreamora...wenn "das Kind aber nunmal schon in den Brunnen gefallen ist" bzw. die Liste nunmal schon existiert hilft mir das wenig, ausserdem würde ich die Zeit dann halt nicht im Anschluß verlieren, sondern schon beim einfügen. Abgesehen davon geht das in meinem Fall nicht, weil Duplikate auch erwünscht sein können und nur optional entfernt werden sollen, daher brauch ich einen Algo. @BladeRunner...das ist zumindest mal ein Ansatz den ich einbauen werde, danke. Bin für weitere Vorschläge aber immer noch offen
mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier Man kann sich öfter als zweimal im Leben halb tot lachen.

EPS

Mi, Aug 23, 2006 9:58
Antworten mit Zitat

@Dreamora...wenn "das Kind aber nunmal schon in den Brunnen gefallen ist" bzw. die Liste nunmal schon existiert hilft mir das wenig, ausserdem würde ich die Zeit dann halt nicht im Anschluß verlieren, sondern schon beim einfügen. Abgesehen davon geht das in meinem Fall nicht, weil Duplikate auch erwünscht sein können und nur optional entfernt werden sollen, daher brauch ich einen Algo.

@BladeRunner...das ist zumindest mal ein Ansatz den ich einbauen werde, danke.

Bin für weitere Vorschläge aber immer noch offen Smile

mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier

Man kann sich öfter als zweimal im Leben halb tot lachen.

	Dreamora	Mi, Aug 23, 2006 10:11 Antworten mit Zitat
Dann wirds lustig, wenn du einen Kernbestandteil deiner Datenstruktur optionalisieren willst. (weil ob ein Schlüssel unique ist oder nicht ist für Einfügen, Sortieren und Entfernen von grundlegender Bedeutung. Nicht unique hat dabei normalerweise schlechtere Laufzeit zur Folge weil man kein early drop machen kann)
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Mi, Aug 23, 2006 10:11
Antworten mit Zitat

Dann wirds lustig, wenn du einen Kernbestandteil deiner Datenstruktur optionalisieren willst. (weil ob ein Schlüssel unique ist oder nicht ist für Einfügen, Sortieren und Entfernen von grundlegender Bedeutung. Nicht unique hat dabei normalerweise schlechtere Laufzeit zur Folge weil man kein early drop machen kann)

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	EPS	Mi, Aug 23, 2006 10:35 Antworten mit Zitat
Das ist jetzt nicht bös gemeint, aber den Satz versteh ich nicht
mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier Man kann sich öfter als zweimal im Leben halb tot lachen.

EPS

Mi, Aug 23, 2006 10:35
Antworten mit Zitat

Das ist jetzt nicht bös gemeint, aber den Satz versteh ich nicht Embarassed

mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier

Man kann sich öfter als zweimal im Leben halb tot lachen.

	Rallimen Sieger des 30-EUR-Wettbewerbs	Mi, Aug 23, 2006 18:54 Antworten mit Zitat
Die doppelte Schleife ist natürlich zu langsam, da ja alles doppelt abgefragt wird! Besser ist es mit einer For ...each und after Schleife Code: [AUSKLAPPEN] [EINKLAPPEN] For t1.typ = Each Typ t2.typ = After t1 While t2 <> Null Print t1\x + " " + t2\x If t1\x = t2\x Then ;mach was End If t2 = After t2 Wend Next So gibt es keine doppelten Abfragen und sollte demnach 50% schneller sein Noch eine andere Möglichkeit ist es das ganze Feld zu sortieren! und dann nur die Nachbareinträge zu überprüfen! Einen schnell erstellten Sortieralgo gibt es hier! www.blitzforum.de/forum/viewtopic.php?t=11467 ob es damit schneller geht mußt du mal ausprobieren!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Mi, Aug 23, 2006 18:54
Antworten mit Zitat

Die doppelte Schleife ist natürlich zu langsam, da ja alles doppelt abgefragt wird!
Besser ist es mit einer For ...each und after Schleife

Code: [AUSKLAPPEN]

For t1.typ = Each Typ
t2.typ = After t1

While t2 <> Null
Print t1\x + " " + t2\x

If t1\x = t2\x Then
;mach was
End If

t2 = After t2
Wend

Next

So gibt es keine doppelten Abfragen und sollte demnach 50% schneller sein

Noch eine andere Möglichkeit ist es das ganze Feld zu sortieren!
und dann nur die Nachbareinträge zu überprüfen!
Einen schnell erstellten Sortieralgo gibt es hier!
www.blitzforum.de/forum/viewtopic.php?t=11467

ob es damit schneller geht mußt du mal ausprobieren!

[BB2D | BB3D | BB+]

	EPS	Mi, Aug 23, 2006 19:01 Antworten mit Zitat
Jep, genau die Lösung hab ich jetzt auch drin. Ein sortieren ist leider nicht möglich da die Reihenfolge innerhalb der Liste auch durcheinander sein darf, es sollen halt nur keine Duplikate enthalten sein.
mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier Man kann sich öfter als zweimal im Leben halb tot lachen.

EPS

Mi, Aug 23, 2006 19:01
Antworten mit Zitat

Jep, genau die Lösung hab ich jetzt auch drin.

Ein sortieren ist leider nicht möglich da die Reihenfolge innerhalb der Liste auch durcheinander sein darf, es sollen halt nur keine Duplikate enthalten sein.

mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier

Man kann sich öfter als zweimal im Leben halb tot lachen.

	$tankY	Fr, Aug 25, 2006 12:58 Antworten mit Zitat
Du könntest die vorhandene Liste nochmal in ein anderes Type einspeisen und dabei überprüfen, ob der Eintrag schon vorhanden ist.

$tankY

Fr, Aug 25, 2006 12:58
Antworten mit Zitat

Du könntest die vorhandene Liste nochmal in ein anderes Type einspeisen und dabei überprüfen, ob der Eintrag schon vorhanden ist.

	Vertex	Fr, Aug 25, 2006 13:16 Antworten mit Zitat
Der Ansatz von Dreamora könnte dennoch erfolgen. Es spielt ja keine Rolle, in welcher Reihenfolge die Datensätze sind(da ID vorhanden). Code: [AUSKLAPPEN] [EINKLAPPEN] +---+---+---+---+---+---+---+ \| A \| C \| B \| A \| C \| A \| D \| +---+---+---+---+---+---+---+ +---+ \| A \| +---+ Pos = 1 +---+---+ \| A \| C \| +---+---+ Pos = 2 +---+---+---+ \| A \| C \| B \| +---+---+---+ Pos = 3 +---+---+---+---+ \| A \| C \| B \| A \| +---+---+---+---+ Pos = 3 +---+---+---+---+---+ \| A \| C \| B \| A \| C \| +---+---+---+---+---+ Pos = 3 +---+---+---+---+---+---+ \| A \| C \| B \| D \| A \| C \| +---+---+---+---+---+---+ Pos = 4 Was soll das bewirken? Immer, wenn ein Element hinein kommt, dann wird geprüft, ob es schon zwischen Index 0 und Pos - 1 vorhanden ist. Wenn nicht, wird es an der Position Pos angehangen und Pos um 1 erhöht. Ist es schon vorhanden, wird es am Ende der Liste angehangen und Pos bleibt unberührt. Zum Schluss stehen dann ab Pos alle doppelt und mehr vorkommenden Datensätze die du auf Anfrage super schnell löschen kannst. mfg olli

Vertex

Fr, Aug 25, 2006 13:16
Antworten mit Zitat

Der Ansatz von Dreamora könnte dennoch erfolgen. Es spielt ja keine Rolle, in welcher Reihenfolge die Datensätze sind(da ID vorhanden).

Code: [AUSKLAPPEN]

+---+---+---+---+---+---+---+
| A | C | B | A | C | A | D |
+---+---+---+---+---+---+---+

+---+
| A |
+---+
Pos = 1

+---+---+
| A | C |
+---+---+
Pos = 2

+---+---+---+
| A | C | B |
+---+---+---+
Pos = 3

+---+---+---+---+
| A | C | B | A |
+---+---+---+---+
Pos = 3

+---+---+---+---+---+
| A | C | B | A | C |
+---+---+---+---+---+
Pos = 3

+---+---+---+---+---+---+
| A | C | B | D | A | C |
+---+---+---+---+---+---+
Pos = 4

Was soll das bewirken? Immer, wenn ein Element hinein kommt, dann wird geprüft, ob es schon zwischen Index 0 und Pos - 1 vorhanden ist. Wenn nicht, wird es an der Position Pos angehangen und Pos um 1 erhöht. Ist es schon vorhanden, wird es am Ende der Liste angehangen und Pos bleibt unberührt.

Zum Schluss stehen dann ab Pos alle doppelt und mehr vorkommenden Datensätze die du auf Anfrage super schnell löschen kannst.

mfg olli

	Dreamora	Fr, Aug 25, 2006 13:46 Antworten mit Zitat
Die Idee hat nen Touch von Genialität. Hut ab.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Aug 25, 2006 13:46
Antworten mit Zitat

Die Idee hat nen Touch von Genialität.
Hut ab.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Vertex	Fr, Aug 25, 2006 13:51 Antworten mit Zitat
Hehe, danke Ich habe das mal schnell umgesetzt. Bei den Indizes war ich etwas verwirrt, so das die ein oder andere If Abfrage vllt. garnicht sein muss. Code: [AUSKLAPPEN] [EINKLAPPEN] Global Length%, Position% Init() CreatePerson("A") CreatePerson("C") CreatePerson("B") CreatePerson("A") CreatePerson("C") CreatePerson("A") CreatePerson("D") Display() WaitKey DeleteRedundantData() Cls : Locate 0, 0 Display() WaitKey End Type TPerson Field ID% Field Name$ End Type Function Init() Delete Each TPerson Length = 0 Position = 0 End Function Function DeleteRedundantData() Local Dummy.TPerson, Dummy2.TPerson, Index% For Dummy = Each TPerson If Index = Position Then Exit Index = Index + 1 Next While Dummy <> Null Dummy2 = After Dummy Delete Dummy Dummy = Dummy2 Wend End Function Function CreatePerson(Name$) Local Person.TPerson, Dummy.TPerson, Index%, Exist% Person = New TPerson Length = Length + 1 Person\ID = Length Person\Name = Name$ Dummy = First TPerson For Index% = 0 To Position - 1 If Dummy <> Person And Dummy\Name$ = Name$ Then Exist = True Exit Else Dummy = After Dummy EndIf Next If Not Exist Then If Dummy <> Person Then Insert Person Before Dummy Position = Position + 1 EndIf End Function Function Display() Local Person.TPerson For Person = Each TPerson Print Person\Name$ + " " + Person\ID Next End Function Zum Teil ist das aber schon pervers, dass Instanzen autom. in die Liste eingetragen werden. Bei BlitzMax sehe das viel effizienter aus. mfg olli Edit: Arg, beim genaueren Überlegen hat Rallimens Code die selbe Effizienz.

Vertex

Fr, Aug 25, 2006 13:51
Antworten mit Zitat

Hehe, danke Smile

Ich habe das mal schnell umgesetzt. Bei den Indizes war ich etwas verwirrt, so das die ein oder andere If Abfrage vllt. garnicht sein muss.

Code: [AUSKLAPPEN]

Global Length%, Position%

Init()
CreatePerson("A")
CreatePerson("C")
CreatePerson("B")
CreatePerson("A")
CreatePerson("C")
CreatePerson("A")
CreatePerson("D")

Display()
WaitKey

DeleteRedundantData()
Cls : Locate 0, 0
Display()

WaitKey
End

Type TPerson
Field ID%
Field Name$
End Type

Function Init()
Delete Each TPerson
Length = 0
Position = 0
End Function

Function DeleteRedundantData()
Local Dummy.TPerson, Dummy2.TPerson, Index%

For Dummy = Each TPerson
   If Index = Position Then Exit
   Index = Index + 1
Next

While Dummy <> Null
   Dummy2 = After Dummy
   Delete Dummy
   Dummy = Dummy2
Wend
End Function

Function CreatePerson(Name$)
Local Person.TPerson, Dummy.TPerson, Index%, Exist%

Person = New TPerson
Length = Length + 1
Person\ID = Length
Person\Name = Name$

Dummy = First TPerson
For Index% = 0 To Position - 1
   If Dummy <> Person And Dummy\Name$ = Name$ Then
      Exist = True
      Exit
   Else
      Dummy = After Dummy
   EndIf
Next

If Not Exist Then
   If Dummy <> Person Then Insert Person Before Dummy
   Position = Position + 1
EndIf
End Function

Function Display()
Local Person.TPerson

For Person = Each TPerson
   Print Person\Name$ + " " + Person\ID
Next
End Function

Zum Teil ist das aber schon pervers, dass Instanzen autom. in die Liste eingetragen werden. Bei BlitzMax sehe das viel effizienter aus.

mfg olli

Edit: Arg, beim genaueren Überlegen hat Rallimens Code die selbe Effizienz.

	Dreamora	Fr, Aug 25, 2006 14:19 Antworten mit Zitat
Dummy <> Person Der Check ist nicht nötig. Da Person neu erzeugt wurde, kann es von Grund auf nicht gleich sein. Ich würde mir sorgen machen, wenn sie es wären ^^ Und jopp, mit BM wäre da definitiv noch ein wenig mehr Saft drin. Aber das hat schon genügend Saft für den Typus Anwendung den man mit 1 Core und B3D machen kann und möchte ^^
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Aug 25, 2006 14:19
Antworten mit Zitat

Dummy <> Person

Der Check ist nicht nötig.
Da Person neu erzeugt wurde, kann es von Grund auf nicht gleich sein.
Ich würde mir sorgen machen, wenn sie es wären ^^

Und jopp, mit BM wäre da definitiv noch ein wenig mehr Saft drin.
Aber das hat schon genügend Saft für den Typus Anwendung den man mit 1 Core und B3D machen kann und möchte ^^

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	EPS	Fr, Aug 25, 2006 20:08 Antworten mit Zitat
Die Idee ist wirklich nicht schlecht, hat nur leider einen Haken...sie ist auf meine Thematik nicht anwendbar, da die Listenfolge durcheinanderkäme wenn ich schon beim hinzufügen auf Duplikate prüfen würde. Bei meiner Liste sind (wie schon einmal gesagt) Duplikate auch erlaubt, sie sollen nur auf Wunsch enfernt werden. Egal, für einen ähnlichen Fall ist dies sicher ne geniale Lösung und DANKE für den Aufwand und die Hirntätigkeit
mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier Man kann sich öfter als zweimal im Leben halb tot lachen.

EPS

Fr, Aug 25, 2006 20:08
Antworten mit Zitat

Die Idee ist wirklich nicht schlecht, hat nur leider einen Haken...sie ist auf meine Thematik nicht anwendbar, da die Listenfolge durcheinanderkäme wenn ich schon beim hinzufügen auf Duplikate prüfen würde.

Bei meiner Liste sind (wie schon einmal gesagt) Duplikate auch erlaubt, sie sollen nur auf Wunsch enfernt werden.

Egal, für einen ähnlichen Fall ist dies sicher ne geniale Lösung und DANKE für den Aufwand und die Hirntätigkeit Wink

mGUI - Graphical User Interface für Blitz3D...Informationen gibt es hier

Man kann sich öfter als zweimal im Leben halb tot lachen.

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Duplikate in einer Type Liste löschen

Betreff: Duplikate in einer Type Liste löschen