Effektiver Algorithmus zum eliminieren doppelter Werte
-
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.