Existe-t-il une implémentation de structure de données de file d'attente prioritaire dans la bibliothèque standard de Ruby?

La bibliothèque standard de Ruby a-t-elle une implémentation de file d'attente prioritaire?

23
demandé sur Andrew Marshall 2010-11-17 15:18:23

5 réponses

Il y a aussi https://rubygems.org/gems/PriorityQueue , qui fonctionne toujours 1.9 même s'il n'a pas été changé depuis 2005.

Cela fonctionne bien d'après ce que j'ai essayé, il y a un benchmark, et c'est bien documenté. Je ne pourrais pas dire cela pour PriorityQueue et Heap des algorithmes (ce qui ne semble pas permettre de changer facilement la clé pour une valeur donnée).

5
répondu eregon 2012-05-05 21:11:46

Vient de publier une extension ruby (en C++) implémentant des files d'attente prioritaires, c'est l'ordre des grandeurs plus rapide que les implémentations basées sur ruby. Voir https://rubygems.org/gems/priority_queue_cxx.

4
répondu user2449437 2014-03-25 14:20:21

Il y a une implémentation skewheap dans RubyGems, si vous êtes intéressé.

1
répondu pjs 2014-03-25 14:27:04

Il y a le rubygem de longue date rbtree qui fournit ce type de fonctionnalité. C'est une implémentation de Arbre Rouge-Noir.

De plus, il existe une implémentation ruby pure rbtree-pure .

0
répondu copiousfreetime 2014-09-01 17:31:24