16
Gibt es Implementierungen einer rein funktionalen soft heap Datenstruktur in einer beliebigen Sprache?Rein funktionaler Soft-Heap
A
Antwort
20
Eine schnelle Suche in der digitalen ACM-Bibliothek zeigt, dass Chazelles weiche Heap-Struktur, obwohl sie sehr interessant ist, relativ wenig studiert hat und dass persistente/funktionale weiche Haufen daher ein offenes Forschungsthema sind.
Also würde ich nein sagen, es gibt keine bekannten Ansätze für persistente weiche Haufen. Eine Beschreibung zu beschreiben, wäre ein veröffentlichbares Ergebnis (es könnte dazu führen, dass das Kopieren hinzugefügt wird, wo Sie die ursprüngliche Struktur verändern würden, und die Möglichkeiten zum Teilen identifizieren).
+3
@Jon, wenn Sie planen, dieses Problem anzugehen, und Sie haben noch nicht gelesen * Rein funktionale Datenstrukturen *, ich schlage vor, Sie tun dies. Auch wenn es sich nicht um Soft Heaps handelt, wird es Ihnen Grundprinzipien des Designs funktionaler Datenstrukturen beibringen, die bei der Lösung dieses Problems hilfreich sein können. –
+1
Es gibt eine ziemlich voll ausgestattete OCaml-Implementierung von Okasaki's Skew Binomial Heaps in meiner Oni CF-Bibliothek: http://bitbucket.org/jhw/oni –
0
Dieses Projekt hat Java-Code, der vielleicht nicht zu schrecklich ist, um ihn in Scala zu übersetzen ... und dann funktionaler zu machen.
https://github.com/lowasser/SoftSelect
Aber wie bisher rein funktionale Datenstrukturen festgestellt Haskell Codebuch hat, die Soft-Heaps, zumal das Beispiel Java-Code zu übernehmen einfacher sein kann.
+0
Ich schaue mir auch dieses Papier von der ACM an, wo SoftHeaps mit binären gemacht werden Bäume: http://dl.acm.org/citation.cfm?id=1496823 – RudeDude
1
Die Haim Kaplan, Robert E. Tarjan, Uri Zwick Papier beschreibt aber nicht vollständig rein funktionelle Variante analysieren.
Verwandte Themen
- 1. CMS in funktionaler Programmiersprache
- 2. UI basierend auf funktionaler Programmierung
- 3. C++ Anzahl funktionaler Wörter Vorkommen
- 4. Enterprise-Muster mit funktionaler Programmierung
- 5. Wie könnte ein Spieler in einem Spiel mit rein funktionaler Programmierung einen anderen Spieler beschädigen (Alter ändern)?
- 6. überwiegender rein virtueller Betreiber
- 7. Rein objektorientierte Sprachen
- 8. Intelligente rein funktionale Sätze
- 9. rein virtuelle Methode namens
- 10. Rein funktionales Äquivalent von weakhashmap?
- 11. Rein numerische Permalinks in WordPress
- 12. Wie rein virtuelle geschütztes Eigentum
- 13. Capturing R6025 rein virtuellen Anruf
- 14. rein virtueller Destruktor in C++
- 15. Was ist der Unterschied zwischen funktionaler, strukturierter und prozeduraler Programmierung?
- 16. funktionaler Stil, um zwei Listen mit Scala zu multiplizieren
- 17. Lambda kann nur mit funktionaler Schnittstelle verwendet werden?
- 18. Extrahieren von Objekten in Array mit funktionaler Programmierung
- 19. Funktionaler Grund, warum gespeicherte Prozeduren INSERT/EXECUTE INTO nicht unterstützen?
- 20. Cloning C++ Klasse mit rein virtuellen Methoden
- 21. Warum ist LINQ nicht rein funktional?
- 22. Bild weniger rein CSS Pfeil Tags
- 23. Wie rein virtuelle Funktion in C++ implementieren
- 24. Mimic Python (rein) virtuelle Funktionen wie C#
- 25. Compress Arbeitsverzeichnis rein mit Bash Regex
- 26. Effiziente Heaps in rein funktionalen Sprachen
- 27. Applikative Funktoren rein passender nicht verpackt
- 28. Ist diese simple rein funktionale Warteschlange gültig?
- 29. C++ - Parameter einer rein virtuellen Funktion
- 30. Clang -Wweak-vtables und rein abstrakte Klasse
ich letzte Nacht bekam durch ein wenig davon;: Es finden sich unter Ich habe die Zeitkomplexitäten nicht verifiziert, aber sie scheinen falsch log (1/e) zu sein, wobei e 0
nlucaroni
Großartig! Log ist nur negativ für Argumente kleiner als 1, aber 1/ε ist nicht, weil 0 <ε <1, also 1 <ε⁻¹ <∞. –
Oh natürlich. Ja, du hast recht. Ich war eindeutig (oder nicht ich denke), denke log (ε). Also, wenn er sagt, dass alle Operationen amortisiert sind, Kosten 0, spricht er von einem konstanten Faktor? – nlucaroni