Gibt es eine Bibliothek, die eine Datenstruktur bereitstellt, die die Reihenfolge der Elemente beibehält und keine Duplikate enthält? Und gibt es einen Eigennamen für eine solche Datenstruktur?Eine Liste ohne Duplikate oder eine geordnete Menge
Ich erwarte, dass es sich wie eine Liste mit nub verhält, die nach jeder Operation darauf angewendet wird. Natürlich erwarte ich nicht, dass es als ineffektiv umgesetzt wird.
Hier ist eine Lösung:
Verwenden Sie ein fingertree mit dem Set Monoid als Maß. Dann prüfen Sie bei Beilagen zuerst die Mitgliedschaft, indem Sie die measure Ihres vollen Fingerstrees verwenden. Dies gibt Ihnen O(log(n)) Nachteile und Snoc, O(1) löscht.
Hier ist eine andere Lösung:
Paar eine normale Liste mit einem normalen Set und im Grunde die gleiche Wirkung erzielen. Sie erhalten bessere konstante Faktoren, aber O(log(n)) löscht.
Hier ist eine Frage: Was möchten Sie beim Einfügen eines Duplikats passieren? Sollte die bestehende Position erhalten bleiben? Die neue Position? Priority Queues können abhängig von Ihren Anforderungen sein.
Es erinnert mich an Java [LinkedHashSet] (http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html). Ich nehme an, ein ähnlicher Ansatz könnte für eine unveränderliche funktionale Datenstruktur verwendet werden. –
Wenn Ihr Typ zu 'Ord' gehört, können Sie' Data.Set' zum Schreiben und 'ordNub' verwenden, das' O (n * log m) 'benötigt, wobei' n' die Anzahl der Elemente und 'm ist 'die Anzahl der einzigartigen Gegenstände. Wenn "Hashable" und nicht "Ord", können Sie dasselbe mit "Data.HashSet" tun. Wäre das ausreichend ineffizient? –
Hallo 2013, bist du zu einer Lösung gekommen? – akst