Gibt es eine einfache Kombination von Standard-Funktionen höherer Ordnung, um die einzigartigen Elemente in einer Liste zu zählen?Einzelne Elemente in einer Liste zählen
Zum Beispiel das Ergebnis für
[1, 1, 4, 0, 4, 4]
wäre so etwas wie
[(1,2), (4,3), (0,1)]
werden, wenn Auftrag nicht wichtig ist dies funktioniert:
map (\[email protected](x:_) -> (x, length xs)) . group . sort
group . sort wird Ihnen eine Liste von Listen wo alle Elemente, die gleich sind, in der gleichen Unterliste (ohne sor t, nur aufeinanderfolgende gleiche Elemente würden zusammen gruppiert werden). Die map wandelt dann jede Unterliste in ein (element, lengthOfSublist)-tuple um.
Wenn Sie das Ergebnis nach dem ersten Vorkommen sortieren möchten, können Sie vor der Sortierung zip verwenden, um jedem Element einen Index hinzuzufügen, nach der Gruppierung erneut nach diesem Index zu sortieren und dann den Index zu entfernen.
Die Sortierung könnte auf großen Listen sehr teuer sein. Es könnte besser sein, die Lösungen von KennyTM oder sdcwc für eine schnellere Leistung zu verwenden. – GeneralBecos
@GeneralBecos Warum ist das Sortieren langsamer als das Erstellen einer Karte? Beide sind "O (n log n)". – sepp2k
Wenn Sie eine Häufigkeitsverteilung vornehmen, entspricht die Anzahl der Elemente im schlimmsten Fall der Anzahl der Elemente in der Liste. Im häufigeren Szenario wird die Anzahl der Elemente in der Verteilung viel geringer sein. Daher wird die Karte im Durchschnitt die Sortierung übertreffen. – GeneralBecos
Die einfachste Sache wäre, die Elemente in Reihenfolge zu sortieren, "Gruppe" zu verwenden, um sie in Unterlisten gleicher Elemente zu platzieren und dann die Elemente in jeder Unterliste zu zählen.
map (\xs -> (head xs, length xs)) . group . sort
Übrigens können Sie schreiben '\ xs -> (Kopf xs, Länge xs)' als 'Kopf &&& "Länge", mit Control.Arrow-Modul. – sdcvvc
Wenn die Liste nur ganze Zahlen enthält, auch wenn
import qualified Data.IntMap as I
countElems1 :: [Int] -> [(Int, Int)]
countElems1 = I.toList . foldr (\k -> I.insertWith (+) k 1) I.empty
(Denken Sie daran, mit der Optimierung zu kompilieren verwenden könnte, sonst wird dies 2x langsamer als die group . sort Methode. Mit -O2 es ist etwas schneller um 14%.)
Sie auch eine der multisetpackages verwenden könnte, die die Funktion so einfach wie
machtimport qualified Math.Combinatorics.Multiset as S
countElems4 = S.toCounts . S.fromList
aber weniger effizient sein.
Alle oben genannten Lösungen ignorieren die ursprüngliche Reihenfolge.
Und das ist ohne die jüngsten Geschwindigkeit Verbesserungen der Container-Bibliothek, ich wette. –
Worüber Sie reden ist nur run length encoding auf sortierte Daten: das kostenlose Online-Buch Real World Haskell hat eine great example of this. Sie werden die Liste sortieren müssen, bevor Sie sie durch den runLengthEncoder setzen.
Es ist * nicht * RLE. RLE wird '[(1,2), (4,1), (0,1), (4,2)] '. – kennytm
@KennyTM Bitte beachten Sie, dass ich 'auf sortierten Daten' sagte. Also nicht ganz RLE, aber fast mit sortierten Eingabe ich denke es ist, oder? –
Mit Data.Map und Tupel Sektionen:
count = Map.fromListWith (+) . map (, 1)
(In Map.toList wenn Sie eine Liste benötigen.)
ist wichtig, um? Wenn ja, wie lautet die Bestellung? Reihenfolge des ersten Auftretens? – sepp2k