doppelte eintraege finden
-
hola leute
kennt einer einen guten algo um in einer liste bzw in einem array doppeltvorkommende eintraege ausfindig zu mchen ?
der zeit wuerd ich eine zweite liste erstellen, die erste liste reinkopieren, sortieren und sequentiell durchgehen und vergleichen. wenn aber die liste, wie in meinem fall schon zig MB hat, dann faengt er, beim erstellen der zweiten liste, das auslagern auf die platte an. dann wirds ziemlich traege. mindestens so traege wie mein hirn heute schaltet.fuer anregungen links oder ner tasse kaffee bin ich dankbar
Meep Meep
-
Meep Meep schrieb:
hola leute
kennt einer einen guten algo um in einer liste bzw in einem array doppeltvorkommende eintraege ausfindig zu mchen ?jo.
der zeit wuerd ich eine zweite liste erstellen, die erste liste reinkopieren, sortieren und sequentiell durchgehen und vergleichen.
jo, so macht man es.
wenn aber die liste, wie in meinem fall schon zig MB hat, dann faengt er, beim erstellen der zweiten liste, das auslagern auf die platte an. dann wirds ziemlich traege. mindestens so traege wie mein hirn heute schaltet.
kannst nur das sortieren beschleunigen, indem du was kluges machst, wo nicht so schlimm ausgelagert werden muss. das hängt aber ganz von den daten ab, die du hast. bieten sich die schlüssel an, daß du erstmal viele kleinere dateien baust? also zum beispiel bei strings kann es gut sein, in einem rutsch erstmal die liste in 256 kleinere listen zu trennen, je nach anfangsbuchstaben. ist so eine kleine-liste noch zu groß, kann man genauso weiterzerlegen. (ist natürlich nicht super-optimal, wenn alle strings mit "http://" beginnen).
sind vielleicht die schlüssel klein und die daten groß? dann kannste nur die schlüssel kopieren und sortieren. aber ich hab ka, welche daten du hast. ganz allgemein ist dein verfahren einfach das beste. kann man, weil man die daten genauer kennt, was spezielles machen, kanns erheblich besser werden.
-
volkard schrieb:
Meep Meep schrieb:
der zeit wuerd ich eine zweite liste erstellen, die erste liste reinkopieren, sortieren und sequentiell durchgehen und vergleichen.
jo, so macht man es.
...auf keinen fall, wenn man's mit zig megabytes datenbestand zu tun hat.
@Meep: nimm von vorn herein eine sortierte liste, dann erkennst du schon beim einfügen ob das element schon da ist oder nicht.
-
net schrieb:
...auf keinen fall, wenn man's mit zig megabytes datenbestand zu tun hat.
@Meep: nimm von vorn herein eine sortierte liste, dann erkennst du schon beim einfügen ob das element schon da ist oder nicht.lol
wenn er die Originalliste sortieren dürfte würde er wohl keine Kopie ziehen, oder? Und wie willste sonst rauskriegen was doppelt ist außer mit sortieren? Günstiger geht's nicht.
-
Jester schrieb:
wenn er die Originalliste sortieren dürfte würde er wohl keine Kopie ziehen, oder?
das können wir doch nicht wissen.
Jester schrieb:
Und wie willste sonst rauskriegen was doppelt ist außer mit sortieren? Günstiger geht's nicht.
gegen das sortieren hat doch keiner was
-
halloechen leute
@net
leider funktioniert das vorsortieren nicht, weil ich hier mit einem chon fertigerstelltem vector arbeite, den ich per referenz bekomme. sind uebrigens strings mit groessen zwischen 8 und 16 bytes. der vector selbst darf leider auch nicht sortiert werden. nachdem is immer mindestens 8 zeichen lange strings sind, werd ich es mal mit int-zeigern auf die strings probieren. die in einem neuen vector ablegen und da dann sortieren.naja vielleicht faellt ja jemand noch ne bessere methode ein
Meep Meep
-
Nimm doch gleich iteratoren auf die strings.
-
Jester schrieb:
Nimm doch gleich iteratoren auf die strings.
wird das dadurch schneller, sicherer, hübscher, fehlerärmer, interessanter oder sowas?
-
Wird hübscher, weil Du den iterator z.B. direkt an die Löschfunktion des vector geben kannst.
-
den int-zeiger kann ich auch dem vector zum loeschen uebergeben, weil methode dafuer vorhanden is
Meep Meep
-
Ich wuerde das so machen:
1. Ne Liste von INTEGERn anlegen - zuerst leer.
- in die Liste kommen alle SORTIERTEN Indizes der Strings rein
2. string- Vector durchgehen:
- 3. fuer jeden String Index in Liste suchen
- Suche in Listen- Mitte starten
- Je nach vergleich nach oben/unter weitersuchen mit HALBER Schrittweite
4. Index in Liste einfuegenDie String Indizes werden gleich sortiert in Liste geschrieben
voilaIn einer extra Liste koennten gleich doubletten markiert werden.
Ev. geht das auch mit Array of int
-
warum nicht einfach die daten in ein std::set schreiben ?