Effektiver Algorithmus zum eliminieren doppelter Werte
-
std::set
-
hmmmmmmmm schrieb:
std::set
Wurde schon indirekt von "Informatikker" genannt.
-
Die Liste ist bereits sortiert, aber was das für einen Unterschied?
-
Ishildur schrieb:
Die Liste ist bereits sortiert, aber was das für einen Unterschied?
Die Tatsache, dass Duplikate dann immer aufeinander folgen?
-
Stimmt auf die Sortierverfahren mit linearem Aufwand bin ich gar nicht gekommen, wenn du also nur Zahlen hast wären diese auf jeden Fall eine sehr effiziente Lösung.
Wenn die Werte sortiert sind, sind Listen doch optimal, da du hier in O(1) die Duplikate löschen kannst. Ich bin mir gerade nicht sicher wie std::unique arbeitet, aber wenn das einen sortierten Container erwartet, dann verwende std::unique.
-
Moment mal... Du hast eine sortierte Liste, die keine Duplikate enthalten soll? std::set hält seine Werte intern immer sortiert und enthält zu keinem Zeitpunkt Duplikate. Du musst die Liste also nie händisch sortieren bzw. Duplikate entfernen. Das dürfte die komfortabelste Möglichkeit sein, wie ja bereits schon erwähnt wurde.
Gruß
Don06
-
Informatikker schrieb:
Stimmt auf die Sortierverfahren mit linearem Aufwand bin ich gar nicht gekommen, wenn du also nur Zahlen hast wären diese auf jeden Fall eine sehr effiziente Lösung.
Das Radixsort-Verfahren vergesse ich auch immer wieder. Vorhin ist mir eingefallen, dass da doch irgendwas war und musste erst in meiner Schnipsel-Sammlung rumstöbern um an den Namen zu kommen, dann ab nach Wikipedia, die Komplexität nachschlagen
Informatikker schrieb:
Wenn die Werte sortiert sind, sind Listen doch optimal, da du hier in O(1) die Duplikate löschen kannst. Ich bin mir gerade nicht sicher wie std::unique arbeitet, aber wenn das einen sortierten Container erwartet, dann verwende std::unique.
Das Sortieren müsste mit Listen aber recht schmerzhaft werden, radix sortiert sowieso nicht in-place, man muss also noch einen Container dazwischen schalten. Ich hätte dann einfach (im vector o.Ä.) nicht die Elemente gelöscht, sondern so wie hier in der Beispielimplementation umgeschoben und einen Iterator auf das Ende der Sequenz zurückgegeben. Naja, viele Wege führen halt nach Rom.
-
Don06 schrieb:
Moment mal... Du hast eine sortierte Liste, die keine Duplikate enthalten soll? std::set hält seine Werte intern immer sortiert und enthält zu keinem Zeitpunkt Duplikate. Du musst die Liste also nie händisch sortieren bzw. Duplikate entfernen. Das dürfte die komfortabelste Möglichkeit sein, wie ja bereits schon erwähnt wurde.
Gruß
Don06Verwendet intern aber meist einen Rot-Schwarz-Baum das heißt n mal Einfügen liegt in O(nlog(n)) während das Einfügen in eine std::list für n Elemente O(n) ist und das Entfernen der Duplikate ebenfalls O(n). Wenn einfach nur n Elemente gespeichert werden und dann einmal alle Duplikate raus sollen, dann wäre das vorzuziehen.
Wenn zu jedem Zeipunkt keine Duplikate vorhanden sein sollen, wäre std::set vorzuziehen, da die Liste sonst O(n²) Aufwand hätte (n mal O(1) einfügen + O(n) für Duplikate entfernen, also O(nn)).
-
Hallo zusammen, ich bin es wieder einmal
Ich habe eine Liste, welche ich nicht verändern darf und muss daraus eine zusätzliche Liste anfertigen, welche keine Duplikate enhält. Die Originalliste darf und muss meisstens sogar Duplikate enthalten und darf NICHT verändert werden!
Mir ist schon klar, dass bei einer sortieren Liste die Duplikate aufeinanderfolgen, nur ist mir nicht klar, inwiefert dies den Algorithmus beschleunigt
-
Ishildur schrieb:
Mir ist schon klar, dass bei einer sortieren Liste die Duplikate aufeinanderfolgen, nur ist mir nicht klar, inwiefert dies den Algorithmus beschleunigt
Direktes Suchen von Duplikaten nutzt nur den Gleichheits-Operator. Sortieren nutzt auch den Kleiner-als-Operator. Weil Sortieren aus dem Grund mehr Informationen verfügbar hat, läuft das insgesamt schneller ab als direktes Duplikate-Suchen.
In der Groß-O-Notation ist das der Unterschied zwischen O(n^2) fürs direkte Suchen und O(n log n) fürs Sortieren mit anschließendem Entfernen der Duplikate.
-
Das beschleunigt deinen Algorithmus insofern, dass du die Liste von Anfang bis Ende durchgehst, dabei immer ein Element entfernst und in die neue Liste einhängst, wenn es sich von dem zuletzt eingehängten Element unterscheidet. Das ist alles.
Und in deinem Fall Kopieren statt umhängen.
-
beim umkopieren der orgianliste in die neue liste zusaetzlich in einer bittable checken ob die betreffende zahl schon vorhanden war, wenn nicht, bit setzen und kopieren. Bis 32bit sollte das ganz gut gehen. falls du das sehr oft machst und deswegen das clear von der bittable kritisch ist, kannst du beim freigeben der kopierten liste einfach die betreffenden eintraege auf 0 setzen.
Gerade bei sehr sehr vielen zahlen sollte das schnell laufen.
-
ich weiß nicht, ob das jemand gelesen hat, aber Ishildur (und das schreib man ohne h, aber ok) hat schon angemerkt, dass die ausgangsliste sortiert ist. die lösung ist also einfach:
1: du nimmst das erste element der alten liste und gibst es in die neue.
2: du gehst zum nächsten element der alten liste und vergleichst es mit dem letzten element der neuen liste. sind die elemente gleich, wiederholst du schritt 2. sind die werte verschieden, gehst du zu schritt 3.
3: du hängst das aktuelle element der alten liste an die neue an. weiter bei schritt 2.
schritt 2 wird solange ausgeführt, bis man das letzte element der alten liste erreicht hat. und fertig.
diese lösung ist klarerweise für die situation, dass die gegebene liste sortiert ist und nicht verändert werden darf.
-
Badestrand schrieb:
Für Integer kann man auch Radixsort anwenden, was in O(n) läuft.
... wenn die Schlüsselgröße konstant ist!
-
besserwisser schrieb:
ich weiß nicht, ob das jemand gelesen hat, aber Ishildur (und das schreib man ohne h, aber ok) hat schon angemerkt, dass die ausgangsliste sortiert ist. die lösung ist also einfach:
1: du nimmst das erste element der alten liste und gibst es in die neue.
2: du gehst zum nächsten element der alten liste und vergleichst es mit dem letzten element der neuen liste. sind die elemente gleich, wiederholst du schritt 2. sind die werte verschieden, gehst du zu schritt 3.
3: du hängst das aktuelle element der alten liste an die neue an. weiter bei schritt 2.
schritt 2 wird solange ausgeführt, bis man das letzte element der alten liste erreicht hat. und fertig.
diese lösung ist klarerweise für die situation, dass die gegebene liste sortiert ist und nicht verändert werden darf.
Oder unique_copy()
-
Jester schrieb:
Badestrand schrieb:
Für Integer kann man auch Radixsort anwenden, was in O(n) läuft.
... wenn die Schlüsselgröße konstant ist!
Das ist in der praxis doch im Prinzip immer gegeben, insofern man nicht mit Big-Integer Klassen arbeitet.
Gibt es bessere Verfahren zum Sortieren, wenn die Länge nicht kostant ist als O(m*n)? Gibt doch bestimmt was mit O(log(m)*n) oder?
-
Informatikker schrieb:
Das ist in der praxis doch im Prinzip immer gegeben, insofern man nicht mit Big-Integer Klassen arbeitet.
Ja, in der Praxis sind die Eingabegrößen auch immer durch eine konstante beschränkt und daher haben alle Algorithmen eine Laufzeit von O(1) und auch dieselbe Speicherkomplexität.
Gibt es bessere Verfahren zum Sortieren, wenn die Länge nicht kostant ist als O(m*n)? Gibt doch bestimmt was mit O(log(m)*n) oder?
Das kommt ein bißchen auf die Schlüssel an. Integers sortieren geht afair in O(n log log n). Für Integers kann man sogar eine assoziative Datenstruktur bauen, die insert/find/delete in O(log log n) Zeit unterstützt: http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
Allerdings ist die nicht sonderlich praktikabel... und wenn man's genau nach Anleitung macht nicht mal für die "konstanten 32 Bit".
-
Jester schrieb:
Für Integers kann man sogar eine assoziative Datenstruktur bauen, die insert/find/delete in O(log log n) Zeit unterstützt
...wenn die Schlüsselgröße konstant ist! :p
Allerdings ist die nicht sonderlich praktikabel... und wenn man's genau nach Anleitung macht nicht mal für die "konstanten 32 Bit".
Hab noch nie damit gearbeitet, darf man fragen warum?
edit: Wegen "However, for small trees the overhead associated with vEB trees is enormous" [aus en-Wiki]?
-
Badestrand schrieb:
Jester schrieb:
Für Integers kann man sogar eine assoziative Datenstruktur bauen, die insert/find/delete in O(log log n) Zeit unterstützt
...wenn die Schlüsselgröße konstant ist! :p
nein, die Laufzeit ist logarithmisch in der Anzahl der Bits des Schlüssels.
genau, der overhead ist riesig. in den experimenten, die ich gesehen habe war std::map deutlich schneller als der vEB. Allerdings gibt es eine für 32Bit getunete Version, die schneller ist als std::map.
-
ich muss mal damit herausplatzen, dass ich patricia tries über alles liebe.
es gibt keine datenstruktur, die mir besser gefällt. deshalb fällt mir bei dem Van Emde Boas tree auf, dass man die gleiche methode zur pfadverkürzung anwenden könnte wie das bei patricia tries gemacht wird. leider bringt das relativ wenig.wenn jemand diesen baum implementiert hat (oder auch schon andere datenstrukturen), würde ich gerne mal tests damit machen. einen contest, wenn ihr so wollt. mehr aber aus interesse, welche datenstrukturen für welche aufgaben am besten geeignet ist, als aus konkurrenzdenken.
würde da jemand mitmachen?
ich kann meine patricia trie implementierung anbieten.