ghc-psqueues

Das psqueues-Paket stellt <http://en.wikipedia.org/wiki/Priority_queue Priority Search Queues> in drei verschiedenen Varianten bereit. * 'OrdPSQ k p v', das die 'Ord k'-Instanz nutzt, um schnelles Einfügen, Löschen und Nachschlagen zu ermöglichen. Diese Implementierung basiert auf Ralf Hinzes <http://citeseer.ist.psu.edu/hinze01simple.html A Simple Implementation Technique for Priority Search Queues>. Sie ähnelt daher der <http://hackage.haskell.org/package/PSQueue PSQueue>-Bibliothek, ist jedoch erheblich schneller und bietet eine etwas andere API. * 'IntPSQ p v' ist eine weit effizientere Implementierung. Sie legt den Schlüsseltyp auf 'Int' fest und verwendet einen <http://en.wikipedia.org/wiki/Radix_tree radix tree> (wie 'IntMap') mit einer zusätzlichen Min-Heap-Eigenschaft. * 'HashPSQ k p v' ist eine recht direkte Erweiterung von 'IntPSQ': sie verwendet einfach die Hashes der Schlüssel als Indizes in der 'IntPSQ'. Bei Hash- Kollisionen wird eine 'OrdPSQ' zur Auflösung genutzt. Die Leistung dieser Implementierung ist mit der von 'IntPSQ' vergleichbar, sie ist jedoch breiter einsetzbar, da die Schlüssel nicht auf 'Int' beschränkt sind, sondern auf jeden 'Hashable'-Datentyp. Jede der drei Implementierungen stellt dieselbe API bereit, sodass sie austauschbar verwendet werden können. Die Benchmarks zeigen, wie sie im Vergleich zueinander abschneiden, und auch im Vergleich zu den anderen Priority-Search-Queue-Implementierungen auf Hackage: <http://hackage.haskell.org/package/PSQueue PSQueue> und <http://hackage.haskell.org/package/fingertree-psqueue fingertree-psqueue>. <<http://i.imgur.com/KmbDKR6.png>> <<http://i.imgur.com/ClT181D.png>> Typische Anwendungen von Priority Search Queues umfassen: * Caches und insbesondere LRU-Caches; * Scheduler; * Wegfindungsalgorithmen wie Dijkstra und A*.