Effektiver Algorithmus zum eliminieren doppelter Werte

Ishildur

Hmmm, ich hatte mich vermutlich zuwenig klar ausgedrückt. Ich will nicht sortieren, sondern lediglich doppelte Einträge eliminieren! Das Problem, welches ich dabei sehe, ist, dass ich eine Liste der bereits entdeckten Werten anlegen muss und diese ständig abfragen muss:

Pseudocode:

List<int> alt;
List<int> neu;

for(int i=0;i<alt.size();++i){
 bool bDub = false; 

 for(int k=0;k<neu.size();++k){
  if(alt.get(i) == neu.get(k){
   bDub = true;
   break;
  }
 }

 if(!bDub) neu.add(alt.get(i));
}

Und das ist IMHO O(n^2)

Meine Frage ist nun, ob es da möglicherweise einen eleganteren Weg gibt?

Badestrand

Ishildur schrieb:

Meine Frage ist nun, ob es da möglicherweise einen eleganteren Weg gibt?

Ja, indem du die Liste vorher sortierst. Alternativ natürlich eine Kopie der Liste anlegen und diese sortieren. Übrigens ist für die "reale" Laufzeit eine Liste ungünstig, ein vector z.B. wäre weitaus performanter.

std::set

Badestrand

hmmmmmmmm schrieb:

std::set

Wurde schon indirekt von "Informatikker" genannt.

Ishildur

Die Liste ist bereits sortiert, aber was das für einen Unterschied?

MFK

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.

Don06

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

Badestrand

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ß
Don06

Verwendet 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)).

Ishildur

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

Christoph

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.

rapso

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.

Jester

Badestrand schrieb:

Für Integer kann man auch Radixsort anwenden, was in O(n) läuft.

... wenn die Schlüsselgröße konstant ist!

Michael E.

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?

Jester

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".

Badestrand

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]?