tas binaire vs tas binomial vs tas de fibonacci, en ce qui concerne la performance d'une file d'attente prioritaire
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelqu'un pourrait-il expliquer comment s'il vous plaît me dois-je décider d'utiliser une ou une autre implémentation de tas, parmi ceux mentionnés dans le titre?
Je voudrais une réponse à me guider sur le choix de la mise en œuvre en ce qui concerne la performance de la structure, en fonction du problème. En ce moment, je fais une file d'attente prioritaire, mais je voudrais savoir non seulement la plus appropriée pour la mise en œuvre ce cas, mais les bases qui me permettent de choisir une mise en œuvre dans toute autre situation ...
Autre chose à considérer est que j'utilise haskell cette fois-ci, donc, si vous connaissez des truc ou quelque chose qui permettrait d'améliorer la mise en œuvre avec cette langue, s'il vous plaît laissez-moi savoir! mais comme avant, des commentaires sur l'utilisation d'autres langues sont les bienvenues aussi!
Merci! et désolé si la question est trop basique, mais je ne suis pas familier avec des tas du tout. Ceci est la première fois que je suis confronté à la tâche de mettre en œuvre un ...
merci encore!
La solution
Vous trouverez peut-être le troisième article http: //themonadreader.files.wordpress .com / 2010/05 / issue16.pdf pertinente.
Autres conseils
Tout d'abord, vous ne serez pas en œuvre un tas standard dans Haskell. Vous implémentez une place être persistante et fonctionnel tas. Parfois, les versions fonctionnelles des structures de données classiques sont aussi que l'original performant (par exemple simples arbres binaires) mais parfois pas (par exemple des files d'attente simples). Dans ce dernier cas, vous aurez besoin d'une structure de données fonctionnelle spécialisée.
Si vous n'êtes pas familier avec les structures de données fonctionnelles, je suggère de commencer avec beaucoup de Okasaki ou href="http://cs.cmu.edu/~rwh/theses/okasaki.pdf" thèse rel="nofollow noreferrer"> (chapitres intérêts:. au moins 6.2.2, 7.2.2)
Si tout cela est allé au-dessus de votre tête, je suggère de commencer la mise en œuvre d'un simple lié ?? tas binaire. (Faire un tas binaire basé sur réseau efficace dans Haskell est une tâche fastidieuse bits.) Une fois cela fait, vous pouvez essayer à mettre en œuvre un tas binomial en utilisant le code pseudo de Okasaki ou même à partir de zéro.
Ils ont la complexité de temps différents sur les différentes opérations sur la priorité des files d'attente. Voici un tableau visuel pour vous
╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║ Operation ║ Binary ║ Binomial ║ Fibonacci ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ insert ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ find Min ║ O(1) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Revmove ║ O(logN) ║ O(logN) ║ O(logN) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Decrease Key ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Union ║ O(N) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║ ║ ■ Heap height = logN ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min. ║
║ ║ ║ ■ Height = k. ║ (keeps find min/max O(1)) ║
║ ║ ║ ■ Degree of root = k. ║ ■ Set of marked nodes. ║
║ Useful ║ ║ ■ Deleting root yields ║ (keep the heaps flat) ║
║ Properties ║ ║ binomial trees ║ ║
║ ║ ║ Bk-1, … , B0. ║ ║
║ ║ ║ (see graph below) ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝
Je suis cette image de la Princeton diapositives conférence
Binary Heap:
Binomial Heap:
Fibonacci Heap:
Note: binomiale et Fibonacci Heap semble familier, mais ils sont subtilement différents:
- tas binomial:. Consolider avec impatience arbres après chaque insertion
- tas de fibonacci. Consolidation paresseusement defer jusqu'à suppression min suivant
Certains référence à tas binomial fonctionnelle, et Fibonacci Heap tas Pairing: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
Si la performance est vraiment la question, je suggère d'utiliser tas d'appariement. Le seul risque est que sa performance est encore une conjecture jusqu'à présent. Mais les expériences montrent que la performance est assez bonne.
