Sollte ich PriorityQueue (Heap) auf List in OCaml implementieren?

Question

Ich verstehe, dass priorityQueue perfekt auf Array ist, da seine Natur in place ist.

Soll ich PriorityQueue (Heap) auf einer Liste in OCaml implementieren?

Wenn ich es auf Liste mache, dann muss ich das in-place entfernen und einen Weg finden, um jedes Mal bei jedem Schritt eine neue Liste zu erstellen. Also frage ich mich, ob es sich lohnt, oder nicht.

---

Eigentlich habe ich eine tiefere Überlegung dazu.

Viele grundlegende Algorithmen / Datenstrukturen wurden von in-place erfunden (ich benutze erfunden, weil ich verstehe, dass viele in-place so umgeformt werden können, dass sie nicht-in-place sind).

FL empfiehlt jedoch keine veränderlichen Dinge. Eine meiner weiteren Fragen ist wie wähle ich zwischen in-place / veränderlich und unveränderlich? oder in OCaml, wann sollte ich zwischen Liste und Array wählen?

---

Zum Beispiel, im obigen priorityqueue Fall, wenn ich gebeten würde, eine priorityqueue in OCaml zu schreiben, sollte ich Array bevorzugen, da es natürlicher und einfacher ist, oder sollte ich Liste wählen um der Unveränderlichkeit willen?

Answer 1

Die Verwendung von unveränderlichen Daten bringt überraschende Vorteile in Bezug auf Modularität und Zuverlässigkeit. Im Wesentlichen ist es unmöglich, dass Daten durch die Änderung durch andere Module beschädigt werden. Module müssen sich nicht länger um andere Module und darum kümmern, wer die Daten "besitzt". Man realisiert nicht, wie mühsam das ist, bis man es nicht mehr tun muss. Ein weiterer unerwarteter Vorteil besteht darin, dass es viel einfacher wird, das Verhalten des Codes nachzuvollziehen, da er sich wie eine mathematische Funktion verhält. Ich habe beide in der Praxis erlebt und das hat mich zu einem FP-Gläubigen gemacht. Die Kosten sind im Allgemeinen überraschend gering, entweder ein kleiner konstanter Faktor oder vielleicht ein zusätzliches log n.

Ein weiterer Vorteil von unveränderlichen Daten ist die Persistenz, d.h. die Fähigkeit, historische Zustände der Daten ohne zusätzlichen Aufwand aufrechtzuerhalten. (Es ist interessant, einen Rückgängig-Vorgang in einer unveränderlichen Umgebung zu implementieren.)

Das gesagt, verwende ich manchmal auch veränderliche Daten, weil sie schneller sein können.

Als Meta-Kommentar würde ich vorschlagen, dass du eine Zeit lang nur unveränderliche Daten in OCaml verwendest. Es stellt anfangs ein sehr interessantes Rätsel dar, wenn nichts anderes. Nach einiger direkten Erfahrung wirst du in der Lage sein zu beurteilen, wo die Trade-offs in bestimmten Fällen liegen. Also schlage ich vor, dass du versuchst, eine unveränderliche Prioritätswarteschlange zu implementieren (oder liest, wie es andere gemacht haben).

Answer 2

Batterien haben hier einen effizienten funktionalen Heap: http://ocaml-batteries-team.github.com/batteries-included/hdoc2/BatHeap.html mit find_min O(1) und alle anderen Heap-Operationen sind log(n)

Ich glaube, die Implementierung ist ein standardmäßiger binomialer Heap, wie in Okasaki beschrieben. Schau hier nach: https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batHeap.ml

Wenn du jedoch weiterhin auf einem Heap mit zerstörerischen Operationen bestehst, dann denke ich, dass Core eine Implementierung aus .NET übernommen hat. Du müsstest einen genauen Blick darauf werfen.

Noch wichtiger ist, dass ich Jeffrey zustimme und vorschlage, dass du dich wirklich gut mit funktionalen Datenstrukturen vertraut machst und nur imperative verwendest, wenn es unbedingt notwendig ist. Ich bin sicher, dass dir das bereits vorgeschlagen wurde, aber die beste Quelle für solche Informationen ist das Buch von Okasaki über rein funktionale Datenstrukturen. Ich kann es nicht genug empfehlen.

Answer 3

Ein Binärheap (die Implementierung der Prioritätswarteschlange, an die Sie wahrscheinlich denken) wird typischerweise auf einem dynamischen Array implementiert (in einigen Sprachen "Vektor" genannt), also einem Array, zu dem Sie Elemente hinzufügen oder entfernen können. Array ist nicht geeignet, da es fest dimensioniert ist; seine Größe ist festgelegt, wenn es erstellt wird. Sie könnten zuerst eine dynamische Array-Struktur auf Basis von Array implementieren und dann den Binärheap darauf aufbauen, wenn Sie dazu bereit sind.

Eine weitere Option für eine Prioritätswarteschlange besteht darin, einen selbstausgleichenden binären Suchbaum zu verwenden; die OCaml-Standardbibliothek verfügt bereits über mehrere Datenstrukturen mit selbstausgleichendem binären Suchbaum -- Set und Map -- und sie werden als unveränderliche, funktionale Datenstrukturen implementiert. Selbstausgleichender binärer Suchbaum bietet für die meisten Operationen die gleiche Zeitkomplexität wie der Binärheap (Minimales Element entfernen und Element hinzufügen; beides O(log n) für beide Strukturen). Er ist weniger effizient beim Aufrufen des minimalen Elements (O(1) für Binärheap; O(log n) für Baum), aber das wird normalerweise sowieso nicht alleine verwendet. Ein Problem beim Verwenden von Set ist, dass doppelte Elemente nicht erlaubt sind; idealerweise würde man einen "Multisatz" verwenden wollen, aber OCaml hat keinen in der Standardbibliothek; wenn Sie sich nicht um doppelte Elemente kümmern, dann ist das kein Problem.

Ich würde nicht empfehlen, List dafür zu verwenden.