Ich brauche eine Funktion, die eine Liste annimmt und ein eindeutiges Element zurückgibt, wenn es existiert, oder [], wenn dies nicht der Fall ist. Wenn viele einzigartige Elemente existieren, sollte das erste zurückgegeben werden (ohne Zeit zu verschwenden, um andere zu finden). Außerdem weiß ich, dass alle Elemente in der Liste von (kleinen und bekannten) Set A stammen. Zum Beispiel erledigt diese Funktion den Job für Ints:
%Vor%Dies ist jedoch nicht gut genug, weil es das Sortieren (n log n) beinhaltet, während es in linearer Zeit durchgeführt werden könnte (weil A klein ist). Zusätzlich benötigt es die Art von Listenelementen, während Ord. Alles, was benötigt werden sollte, Gl. Es wäre auch schön, wenn die Anzahl der Vergleiche so klein wie möglich wäre (dh wenn wir eine Liste durchqueren und Element el zweimal treffen, testen wir nachfolgende Elemente nicht auf Gleichheit mit el)
Dies ist, warum zum Beispiel: Zählen von einzigartigen Elementen in einer Liste löst das Problem nicht - alle Antworten beinhalten das Sortieren oder Durchlaufen der ganzen Liste, um die Anzahl aller Elemente zu finden.
Die Frage ist: Wie geht es in Haskell richtig und effizient?
Okay, lineare Zeit, aus einer endlichen Domäne. Die Laufzeit ist O ((m + d) log d) , wobei m die Größe der Liste und d die Größe ist der Domäne, die linear ist, wenn d festgelegt ist. Mein Plan ist es, die Elemente des Sets als Schlüssel eines trie zu verwenden, mit den counts als Werten Durchsuche den trie nach Elementen mit count 1.
%Vor%Zählen Sie jedes der Elemente. Dies durchläuft die Liste einmal, erstellt einen Trie mit den Ergebnissen ( 0 (m log d) ) und gibt dann eine Funktion zurück, die das Ergebnis im Trie abbildet (mit Laufzeit O (log d) ).
%Vor% Wir verwenden die Einschränkung Enum , um Werte vom Typ a in Ganzzahlen zu konvertieren, um sie im Trie zu indizieren. Eine Enum -Instanz ist Teil des Zeugen Ihrer Annahme, dass a eine kleine, endliche Menge ist ( Bounded wäre der andere Teil, aber siehe unten).
Und dann nach denen suchen, die einzigartig sind.
%Vor% Diese Funktion übernimmt als ersten Parameter eine Aufzählung der gesamten Domäne. Wir hätten eine Bounded a Einschränkung und stattdessen [minBound..maxBound] verwenden können, was für mich semantisch ansprechend ist, da im Wesentlichen Enum + Bounded , aber ziemlich unflexibel ist, da jetzt die Domäne zur Kompilierungszeit bekannt sein muss. Also würde ich diese etwas hässlichere, aber flexiblere Variante wählen.
uniques durchquert die Domäne einmal (träge, so dass head . uniques dom nur solange durchläuft, bis das erste eindeutige Element gefunden wird - nicht in der Liste, sondern in dom ) für jedes laufende Element Die Suchfunktion, die wir eingerichtet haben, ist O (log d) , also nimmt der Filter O (d log d) , und das Erstellen der Zählertabelle dauert O (m log d) . So läuft uniques in O ((m + d) log d) , was linear ist, wenn d fest ist. Es wird mindestens Ω (m log d) benötigen, um irgendwelche Informationen von ihm zu erhalten, da es die gesamte Liste durchqueren muss, um die Tabelle zu erstellen (Sie müssen bis zum Ende der Liste, um zu sehen, ob ein Element wiederholt wurde, also können Sie nicht besser als das tun).
Es gibt wirklich keine Möglichkeit, dies effizient mit nur Eq zu tun. Sie müssten eine weniger effiziente Methode verwenden, um die Gruppen gleicher Elemente zu erstellen, und Sie können nicht wissen, dass nur ein Element eines bestimmten Elements vorhanden ist, ohne die gesamte Liste zu durchsuchen.
Beachten Sie außerdem, dass Sie zur Vermeidung unnützer Vergleiche eine Möglichkeit benötigen, zu überprüfen, ob ein Element schon einmal gefunden wurde. Die einzige Möglichkeit besteht darin, eine Liste mit Elementen zu erstellen, von denen bekannt ist, dass sie mehrere Vorkommen haben. und die einzige Möglichkeit, zu überprüfen, ob das aktuelle Element in dieser Liste ist ... ist es, sie mit jedem zu vergleichen.
Wenn Sie möchten, dass dies schneller als O (etwas wirklich Schreckliches) funktioniert, brauchen Sie das Ord constraint.
Ok, basierend auf den Erläuterungen in den Kommentaren, hier ist ein schnelles und schmutziges Beispiel dafür, was ich denke , nach dem du suchst:
%Vor%Das erste Argument ist eine Liste von Kandidaten, die anfänglich alle möglichen Elemente sein sollten. Das zweite Argument ist die Liste möglicher Ergebnisse, die zunächst leer sein sollten. Das dritte Argument ist die zu prüfende Liste.
Wenn keine Kandidaten mehr vorhanden sind oder das Ende der Liste ohne Ergebnisse erreicht wird, wird Nothing zurückgegeben. Wenn es das Ende der Liste mit den Ergebnissen erreicht, gibt es das vor der Ergebnisliste zurück.
Andernfalls untersucht es das nächste Eingabeelement: Wenn es kein Kandidat ist, ignoriert es es und fährt fort. Wenn es in der Ergebnisliste ist, haben wir es zweimal gesehen. Entfernen Sie es aus den Ergebnis- und Kandidatenlisten und fahren Sie fort. Andernfalls fügen Sie es zu den Ergebnissen hinzu und fahren fort.
Leider muss dies immer noch die gesamte Liste nach einem einzigen Ergebnis durchsuchen, da nur so sichergestellt werden kann, dass es wirklich einzigartig ist.
Wenn Ihre Funktion höchstens ein Element zurückgeben soll, sollten Sie fast sicher Maybe a anstelle von [a] verwenden, um Ihr Ergebnis zurückzugeben.
Zweitens haben Sie zumindest keine andere Wahl, als die gesamte Liste zu durchlaufen: Sie können nicht sicher sagen, ob ein bestimmtes Element wirklich einzigartig ist, bis Sie sich alle anderen angesehen haben.
Wenn Ihre Elemente nicht Ord ediert sind, aber nur für Eq uality getestet werden können, haben Sie wirklich keine bessere Option als etwa:
Beachten Sie, dass Sie die duplizierten Elemente nicht herausfiltern müssen, wenn Sie nicht möchten - der ungünstigste Fall ist in beiden Fällen quadratisch.
Bearbeiten:
Das obige vermisst die Möglichkeit eines frühen Ausgangs aufgrund des oben erwähnten kleinen / bekannten Satzes möglicher Elemente. Beachten Sie jedoch, dass im schlimmsten Fall immer noch die gesamte Liste durchlaufen werden muss: Es muss nur mindestens eines dieser möglichen Elemente fehlen aus der Liste sein ...
Allerdings eine Implementierung, die im Falle einer Erschöpfung vorbeugt:
%Vor%Beachten Sie, dass wenn Ihre Liste Elemente enthält, die nicht dort sein sollten (weil sie nicht in der kleinen / bekannten Menge sind), werden sie durch den obigen Code ausdrücklich ignoriert ...
Wie andere gesagt haben, ohne zusätzliche Einschränkungen, können Sie dies nicht in weniger als quadratischer Zeit tun, denn ohne etwas über die Elemente zu wissen, können Sie sie nicht in einer vernünftigen Datenstruktur halten.
Wenn wir Elemente vergleichen können, eine offensichtliche O (n log n) -Lösung, um zuerst die Anzahl der Elemente zu berechnen und dann die erste mit der Zahl 1 zu finden:
%Vor% Beachten Sie, dass der log n Faktor von der Tatsache herrührt, dass wir in Map der Größe n arbeiten müssen. Wenn die Liste nur k eindeutige Elemente enthält, dann ist die Größe unserer Karte höchstens k , so dass die Gesamtkomplexität nur O (n log k) ist. .
Aber wir können es noch besser machen - wir können ein Hash-Tabelle anstelle einer Map, um eine O (n) Lösung zu erhalten. Dazu benötigen wir die ST Monade, um veränderbare Operationen auf der Hash-Map durchzuführen, und unsere Elemente müssen Hashable . Die Lösung ist im Grunde die gleiche wie zuvor, nur ein bisschen komplexer aufgrund der Arbeit in der ST monad:
Hinweise:
HT.new anstelle von HT.newSized (length xs) verwenden. Dies spart Ihnen etwas Speicher und einen Durchlauf über xs , aber im Fall von vielen verschiedenen Elementen muss die Hash-Tabelle mehrmals skaliert werden. Hier ist eine Version, die den Trick macht:
%Vor% Also durchlaufen wir zuerst die Eingabeliste ( collect ), während wir eine Liste von Buckets mit gleichen Elementen pflegen, die wir mit insert aktualisieren. Dann wählen wir einfach das erste Element aus, das in einem Singleton-Bucket erscheint ( select ).
Die schlechte Nachricht ist, dass dies quadratische Zeit braucht: Für jedes besuchte Element in collect müssen wir die Liste der Buckets durchgehen. Ich fürchte, das ist der Preis, den Sie zahlen müssen, um den Elementtyp nur auf Eq beschränken zu können.
So etwas sieht ziemlich gut aus.
%Vor%Das erste Element des resultierenden Tupels der Falte enthält, was Sie erwarten, eine Liste mit einem eindeutigen Element. Das zweite Element des Tupels ist die Erinnerung an den gespeicherten Prozess, wenn ein Element bereits verworfen wurde oder nicht.
Informationen zur Speicherplatzleistung.
Da Ihr Problem das Design ist, sollten alle Elemente der Liste mindestens einmal durchlaufen werden, bevor ein Ergebnis angezeigt werden kann. Und der interne Algorithmus muss zusätzlich zum guten Wert noch den verworfenen Wert verfolgen, aber der verworfene Wert wird nur einmal angezeigt. Dann ist im schlimmsten Fall die erforderliche Speichermenge gleich der Größe der eingegebenen Liste. Diese solide Ware, wie Sie sagten, dass die erwartete Eingabe ist klein.
Zeitleistung.
Da die erwartete Eingabe klein und nicht standardmäßig sortiert ist, ist es sinnlos, die Liste in den Algorithmus zu sortieren, oder bevor sie angewendet wird, ist sie nutzlos. In der Tat können wir fast statisch sagen, dass die zusätzliche Operation, ein Element an seiner geordneten Stelle (in die Unterliste a und b des Tupels (a,b) ) zu setzen, die gleiche Zeit kostet, als zu prüfen, ob Dieses Element erscheint in der Liste oder nicht.
Unten eine schönere und explizitere Version des Faltblattes.
%Vor% In der verschachtelten Anweisung if ... then ... else ... wird die Liste result im schlimmsten Fall zweimal durchlaufen. Dies kann mit der folgenden Hilfsfunktion vermieden werden.
Aber der Helfer kann mit fold wie folgt umgeschrieben werden, was definitiv schöner ist.
%Vor%Tags und Links algorithm haskell functional-programming