Hallo, ich mache mir gerade ein paar Gedanken, über die Möglichkeiten in einem nicht sortierten Array mit n Elementen festzustellen ob ein Eintrag doppelt vorhanden ist (ja/nein). Der erste Ansatz ist, jedes Element mit dem anderen zu vergleichen. 1-2, 1-3, 1-4, ..., 1-n; 2-3, 2-4, 2-5, ..., 2-n usw. Ist keine Dublette vorhanden, benötigt das (n²+n)/2 Vergleiche. Andere Lösungen wären, das Array vorher zu sortieren und dann zu durchsuchen. Die lasse ich mal rausfallen. Jetzt habe ich mir ein paar Gedanken gemacht, ob es nicht irgendeine Abkürzung geben könnte. Eine Idee ist, jedes Array-Element mit einer Primzahl zu bewerten, alle zu multiplizieren und dann per Primfaktorzerlegung auf doppelte Primzahlen zu prüfen. Z.B. ein Array mit 100 Elementen von Typ unsigned char. 0=2 1=3 2=5 3=7 4=11 usw. Das würde prinzipiell funktionieren, aber müssten a) die Primzahlen z.B. in einer Lookup-Tabelle gespeichert werden, b) das Produkt wird bei anderen Datentypen schnell unhandelbar groß und c) die Primfaktorzerlegung benötigt entsprechend viele Schritte. Führt auch zu keiner schnelleren Lösung. Gibt es noch andere Varianten, ggf. schnellere?
Thomas W. schrieb: > Andere Lösungen wären, das Array vorher zu sortieren und dann zu > durchsuchen. Die lasse ich mal rausfallen. Warum? Wenn der Wertebereich/die Datentypen passen geht das auch schneller als O(n log n) bspw. Radix- oder Counting-Sort > Eine Idee ist, jedes Array-Element mit einer Primzahl zu bewerten, alle > zu multiplizieren und dann per Primfaktorzerlegung auf doppelte > Primzahlen zu prüfen. Primzahlen sind ein gutes Stichwort: Mit einer Hash-Tabelle arbeiten. Laufzeit wäre, da das Einfügen/Abfragen von Werten in der Hash-Tabelle O(1) und im schlimmsten Fall O(n) hat: O(n) bzw. O(n^2). Die Frage ist: Was soll optimiert werden? Geschwindigkeit, Speicherverbrauch oder beides? Zum Bloom-Filter: Kann reichen, muss aber nicht... Das Teil erkennt zwar immer, ob etwas noch nicht vorkam, aber liefert für etwas schon vorhandenes nur eine Wahrscheinlichkeit (kam möglicherweise vor oder auch nicht).
:
Bearbeitet durch User
Thomas W. schrieb: > Gibt es noch andere Varianten, ggf. schnellere? Die Frage ist, was du vergleichst. Bei Zahlen gibt es kaum Abkürzungen, aber bei Strings, besonders ab einer bestimmten Länge, würde ich erstmal von allen Strings einen Hash bilden und dann diese vergleichen. Man kann mit einfachen Hashfunktionen arbeiten, denn das Restrisiko, dass 2 verschiedene Strings den gleichen Hash erzeugen, kann man ja ausschliessen indem man bei angezeigter Gleichheit die Strings nochmal selbst vergleicht - möglicherweise reicht schon eine einfache Prüfsumme. Kostet Speicherplatz für die Hashes, ist aber ab einer bestimmten Stringlänge schneller. Georg
Oder falls du in C++ programmierst, einen STL Map verwenden. Du brauchst die unsortierte Liste nur ein Mal durchlaufen. Ist ein Schluessel schon Vorhanden, hast du eine Doublette gefunden. Falls nicht, ins Map eintragen und weiter laufen.
cfgardiner schrieb: > Oder falls du in C++ programmierst, einen STL Map verwenden. Du brauchst > die unsortierte Liste nur ein Mal durchlaufen. Ist ein Schluessel schon > Vorhanden, hast du eine Doublette gefunden. Falls nicht, ins Map > eintragen und weiter laufen. Ist auch nicht schneller als sortieren. ein einzelnes Insert in die Map ist O(log n), macht zusammen dann wieder O(n log n).
Lass vor dem Eintragen eines neuen Wertes, die bisherigen Einträge über compare am neuen Wert vorbeilaufen und trag ihn nur ein, wenn kein equal-Match dabei ist.
wenn der Wertebereich überschaubar ist, könnte man eine bit-Array anlegen. Und beim durchlaufen das Bit für den Wert auf 1 setzen. Wenn es schon 1 ist, dann doppelt. das sollte dann linear schnell sein.
Peter II schrieb: > wenn der Wertebereich überschaubar ist, könnte man eine bit-Array > anlegen. Und beim durchlaufen das Bit für den Wert auf 1 setzen. Wenn es > schon 1 ist, dann doppelt. So in der Art würde ich es auch bei generischen Daten machen. Man kann eine einfache Prüfsumme bilden und in einem Array (Größe entspricht dem Wertebereich der Prüfsumme) an der Position der Summe einen Pointer auf das untersuchte Element anhängen. Falls man dort schon eine oder mehrere Adressen findet, muss man zwischen den Elementen noch einmal genauer vergleichen. Weil theoretisch alle Elemente die gleiche Prüfsumme haben könnten, kommt man im Extremfall wieder auf die gleiche Komplexität, aber im Mittel wird man sparen.
Linksammler schrieb: > Ist auch nicht schneller als sortiere Aber nur wenn der Doublettenvergleich nur einmal stattfindet. Wenn er immer wieder mal stattfindet und dazwischen eingefügt wird ist eine sortierte Liste oder ein HashSet schneller, weil nicht mehr alles sortiert werden muss. Wenn der TO klar klären würde was er konkret machen will könnte man ihm konkret helfen. Übrigens bringt es nichts bei einem Teilproblem die Performance zu optimieren und dabei ggf. die Komplexität zu erhöhen, wenn dieser Teil überhaupt nicht das Bottleneck ist.
Hallo, bei Strings würde ich über die Stringlänge ein Array of Dictionaries aufbauen, denn unterschiedlich lange Strings sind ja wohl immer unterschiedlich. Gruß, Michael
Linksammler schrieb: > Ist auch nicht schneller als sortieren. Darum geht es ja auch garnicht, aber 2 16bit-Prüfsummen sind erheblich schneller zu vergleichen als 2 100-Zeichen-Strings - wahrscheinlich lohnt sich das schon ab 32-Bit-Daten. Michael Appelt schrieb: > denn unterschiedlich lange Strings sind ja wohl immer > unterschiedlich. Lohnt sich nicht, denn sie haben auch unterschiedliche Prüfsummen, jedenfalls fast immer. Georg
Georg schrieb: > Darum geht es ja auch garnicht, aber 2 16bit-Prüfsummen sind erheblich > schneller zu vergleichen als 2 100-Zeichen-Strings - wahrscheinlich > lohnt sich das schon ab 32-Bit-Daten. Thomas W. schrieb: > Z.B. ein Array mit 100 Elementen von Typ unsigned char. Ist also nur ein Byte pro Array-Eintrag. aus 8-Bit eine 16-Bit "Prüfsumme" zu berechnen ist zwar einfach und kollisionsfrei möglich, macht die Sache aber nicht wirklich schneller.
Ohne weiter Beschreibung der Umgebung wirds wohl nicht möglich sein... Auf einem embedded-Gerät macht die Berechnung eines Hash-Wertes wohl mehr Aufwand als einfaches sortieren mit quicksort(natürlich iterativ implementiert...). Alle Aussagen sind ziemlicher Schmarn, solange man den Einsatz nicht kennt...
ffff schrieb: > Alle Aussagen sind ziemlicher Schmarn, solange man den Einsatz nicht > kennt... Gratulation, die erste vernünftige Antwort.
Noch eine rein theoretische Anmerkung: Es gibt auf dem Gebiet der theoretischen Informatik(die sich ja u.a. genau mit solchen Themen auseinandersetzt) wohl kein Thema, das besser durchdacht/ausgereizt ist als sortieren oder finden von einzelnen Werten. Besser wie O(n) wirds wohl auch nicht gehen, denn um zu erkenne, ob ein Wert doppelt vorkommt, muss ich ja mindestens jeden Wert einmal anschauen! Von dem her sind Sortieralgorithmen schon eine sehr gute Art und Weise doppelte Werte zu finden(mit der geeigneten Erweiterung in der Implementierung muss man auch nicht zuerst sortieren und dann die Werte suchen, sondern kann das in einem Rutsch machen). Und bei Sortieralgorithmen sollte für jeden Geschmack etwas passendes dabei sein...!
Arc Net schrieb: > Zum Bloom-Filter: Kann reichen, muss aber nicht... Das Teil erkennt zwar > immer, ob etwas noch nicht vorkam, aber liefert für etwas schon > vorhandenes nur eine Wahrscheinlichkeit (kam möglicherweise vor oder > auch nicht). Na und? Das Ding kann man schließlich tunen, so daß die false positive rate so klein wird, wie man eben möchte.
Thomas W. schrieb: > Eine Idee ist, jedes Array-Element mit einer Primzahl zu bewerten, alle > zu multiplizieren und dann per Primfaktorzerlegung auf doppelte > Primzahlen zu prüfen. [...] die Primfaktorzerlegung benötigt > entsprechend viele Schritte. Führt auch zu > keiner schnelleren Lösung. > > Gibt es noch andere Varianten Wenn es denn in Richtung Zahlentheorie sein soll bzw. einfach arithmetisch zu beschreiben, kann das über einem Polynomring formuliert werden, z.B. über Z[X]:
Die Bedingung, dass ein es i != j gibt mit a_i = a_j kann dann formuliert werden als
wobei p' die (formale) Ableitung von p nach X bezeichnet.
Man kann die Suche nach Dubletten auf Mengenoperationen zurückführen, indem man aus den zu untersuchenden Elementen eine Menge erzeugt und prüft, ob dadurch die Größe dieser Menge kleiner als die ursprüngliche Anzahl der Elemente ist. Welche interne Repräsentation des Mengendatentyps am günstigsten ist, hängt davon ab, - von welchem Datentyp die Elemente sind, - welchen Wertebereich sie haben und - ob die Rechenzeit oder der Speicherbedarf Priorität hat. Beispielcode in Haskell:
1 | import Data.Set |
2 | |
3 | containsDuplicates xs = size (fromList xs) < length xs |
In Haskell gibt es derzeit (mindestens) 4 Set-Implementationen mit sehr unterschiedliche Eigenschaften: Data.Set: Balanced Tree Data.HashSet: Hash-Tabelle Data.IntSet: Patricia Tree Data.BitSet: Integer-Wert (1 Bit für jedes mögliche Element) Um zwischen diesen Alternativen zu wechseln, muss in obigem Code lediglich die Import-Zeile geändert werden. So kommt in den Genuss einer gut auf die Anwendung abgestimmten Lösung, ohne das Rad neu erfinden zu müssen.
Hallo, schonmal vielen Dank für die Antworten. Zur Aufgabenstellung: Die Aufgabe ist eigentlich nicht meine eigene. Ich habe mir nur ein paar Gedanken dazu gemacht wie sich sowas effizient lösen lassen könnte. Die Aufgabe war nur, 10 Bytes an Daten pro Element die verglichen werden sollen. Darum würde ich das mal als Byte-Array annehmen. Wie die Bitmuster verteilt sind weiß ich nicht. Das Ganze soll in einer SPS ablaufen mit den entsprechenden Beschränkungen, wie kein bzw. nur sehr eingeschränkter dynamischer Speicher. Für die Laufzeit muss man wegen der Echtzeitfähigkeit immer den schlechtesten Fall annehmen. Angeblich können die Daten nicht einzeln sortiert abgelegt werden. Darum habe ich mir mal als Aufgabenstellung "unsortiertes Array mit beliebigen unstrukturierten Daten" gegeben. Bei sortierten Daten gäbe es das Problem auch gar nicht.
In so einem Fall(wenig Speicher) würde sich anbieten: 1) erst sortieren 2) dort einbauen, wenn man doppelte Werte hat, diese evtl. gleich entfernen sortieralgorithmus: Heap-Sort, kein zusätlicher Speicherbedarf, Laufzeit O(n log n)...
ffff schrieb: > Es gibt auf dem Gebiet der theoretischen Informatik(die sich ja u.a. > genau mit solchen Themen auseinandersetzt) wohl kein Thema, das besser > durchdacht/ausgereizt ist als sortieren oder finden von einzelnen > Werten. A+D zählt zur praktischen Informatik
Thomas W. schrieb: > Die Aufgabe war nur, 10 Bytes an Daten pro Element die verglichen werden > sollen. Sind die 10 Bytes ein Eintrag, oder gibt es pro Element eine Liste mit 10 Einträgen zu je einem Byte? Wenn Ersteres, wie groß ist die Liste? Dürfen die Daten verändert werden? (Wenn nicht fallen alle in-situ Sortierungen ohne zusätzliches Anlegen einer Kopie und damit erneuten Aufwand raus) Bei 10 Einträgen würde ich mir über solche Optimierung keinen Kopf machen, insbesondere, da du sowieso mit dem worst-case rechnen musst und eben nicht die beste Methode hinsichtlich ihrer O Notation suchst. (Was interessiert dich die Laufzeit bei entsprechend großen n, wenn n const = 10?) Bei hinreichend großen n, dass die Schrittgröße (wie umfangreich sind die Operationen pro Schritt) in der Gesamtlaufzeit zurück tritt, kommst du nur im speziellen mit a-priori Informationen auf etwas das besser/schneller wäre als O(nlogn) im Allgemeinen (o.B.d.A) ist dies aber nicht möglich. A-priori Informationen könnten sein: Dubletten sind immer an besonderen Stellen zu finden, oder: Wenn xyz, dann existiert keine Dublette) Mein Ansatz wäre hier das pro Element in der Liste 1.) die Suche in einem Rot-Schwarz-Baum (o.Ä.) und 2.) das Einfügen des Elements in diesen Baum. Beide Operationen sind von O(logn) (Wichtig: es gibt auch andere Suchbäume, deren Operationen nicht alle in O(logn) liegen) Insgesamt also O(nlogn) für alle Elemente.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.