F # Priority Queue

Ich hat versucht, diese Code-Snippet zu verwendenF # Priority Queue

https://code.msdn.microsoft.com/windowsdesktop/Net-Implementation-of-a-d3ac7b9d

eine Heap-basierte Implementierung von Prim-Algorithmus zu implementieren, um das Mindest Spanning Tree (MST) Problem in einem ungerichteten verbunden zu lösen Graph.

nach ein paar Iterationen finde ich, dass die Heap/Priority-Queue nicht mehr gut gepflegt ist. das ist der Kopf der PriorityQueue hat nicht den niedrigsten Schlüssel im Heap.

PQ 0 [-7230, 309] 
... 
PQ 146 [-7277, 308]

Hat jemand diesen Code verwendet und ähnliche Probleme festgestellt? Ich kann einen Link auf GitHub, wenn jemand es betrachten würde

Meine Bedürfnisse sind für eine Heap-Datenstruktur, die das Löschen eines Elements in der Mitte unterstützt. Es sieht so aus, als hätte Fsharpx.collections keine solche Datenstruktur.

Kennt jemand eine gute Implementierung irgendwo verfügbar?

dank

Quelle

2016-03-24 Fagui Curtain

-1

Meine Antwort ist inspiriert von V.B. aber hier ist es in voller

ich eine andere Bibliothek als FSharpx.collections verwendet haben, sie genannt wird

Spreads

die Seite für Informationen und Anleitungen lesen.

SortedDeque ist die Datenstruktur, die ich für dieses Problem benötige. Ich habe den gleichen Code, nur von der Microsoft Blog-Seite Code auf die Bibliothek Funktionen und fand das gute Ergebnis, so ist es in der Tat einige Fehler in der Microsoft Blog-Seite Code

PS. Diese Spread-Bibliothek wurde entwickelt, um finanzielle Daten für quantitative Analysen zu formatieren und ich bin froh, dass ich es gefunden habe !!! IT sieht aus wie diese Bibliothek ist ziemlich neu und deshalb ist es nicht auf der Suche von Google oder referenziert in einer anderen SO-Frage (oder wenn es ich nicht gesehen habe)

FSharpx.Collections ist dafür nutzlos Problem, wie Sie aus dieser Diskussion sehen können heap issue in FSharpx.Collections

Quelle

2016-03-28 09:22:09

Wenn Sie mit SortedDeque endete, sollten Sie meine Antwort akzeptiert haben. Spreads ist meine Bibliothek und ich habe dir einen direkten Link dazu gegeben. Ich verstehe nicht, was "in vollem Umfang" du dazu hinzufügst ...:/ –

Weil meine Frage zwei Teile hat. Bestätigen, dass FSharpx.Collections die Aufgabe nicht erfüllt. Eine Bibliothek mit einer Datenstruktur finden, die für mein Problem funktioniert. Du hast nur den zweiten Teil beantwortet. Ich wollte dich nicht beleidigen. Spreads sind übrigens eine ausgezeichnete Arbeit. Ich verbreite das Wort. Entfernen Sie bitte das Downvote –

Nevermind! Es ist nicht meins –

Vor kurzem portiert ich eine MaxHeap von PLINQ bis F # here und es MinHeap gemacht. Es ist Array-basiert und funktioniert viel besser als jede "rein funktionale" Alternative.

Aber nach viel Benchmarking, fand ich, dass SortedDeque basierend auf nur einem einfachen sortierten Ringpuffer deutlich besser auf most use cases führt, auch wenn ich in der Mitte hinzufügen oder löschen muss.

Quelle

2016-03-24 10:02:38

für SortedDeque seinen ganzen Code unten? Linie 88 bis 485? –

@FaguiCurtain Ja, + Tests –

auf FixedMeanHeap.fs https://github.com/Spreads/Spreads/edit/master/src/Spreads.Collections/Common/FixedMinHeap.fs Ich kann keine Mitglieder sehen, die das Löschen in der Mitte ermöglichen vom Haufen? –

Antwort

Verwandte Themen