Est-ce que les tas de Fibonacci ou les files D'attente de Brodal sont utilisés dans la pratique n'importe où?
est-ce que les tas de Fibonacci sont utilisés dans la pratique n'importe où? J'ai regardé autour de AINSI et trouvé des réponses aux questions connexes (voir ci-dessous), mais rien qui répond tout à fait à la question.
- il y a de bonnes implémentations de Fibonacci là-bas, y compris dans les bibliothèques standards comme Boost C++. le fait que ces bibliothèques contiennent des tas de Fibonacci suggère qu'elles doivent être utiles quelque part.
- nous savons que certaines conditions doivent être remplies pour qu'un tas de Fibonacci soit plus rapide dans la pratique: " pour bénéficier des tas de Fibonacci dans la pratique, vous devez les utiliser dans une application où decrease_keys sont incroyablement fréquents "; " pour que le tas de Fibonacci brille vraiment, vous avez besoin de l'un des cas suivants: a) comparaisons coûteuses: tas de Fibrine minimiser le nombre de comparaisons nécessaires pour organiser les données. b) La majorité des opérations est updateKey/insérer/supprimer. Alors que Fibonacci regroupe les mises à jour ensemble jusqu'à l'extraction suivante, plus le " lot " est grand, plus il est efficace. "
- il y a une structure de données appelée une" Queue de Brodal " dont je ne suis pas sûr d'avoir entendu parler avant qui semble avoir des comportements de complexité temporelle au moins aussi bons que les tas de Fibonacci. ici ' s un tableau agréable avec une comparaison des complexités de temps pour diverses opérations pour différentes variétés de tas.
- sur une question à savoir s'il existe des applications de Fibonacci ou tas binomial , answerers seulement donné des exemples de tas binomial.
1 réponses
à ma connaissance, il n'y a pas d'applications majeures qui utilisent réellement les tas de Fibonacci ou les files D'attente de Brodal.
les tas de Fibonacci ont été initialement conçus pour satisfaire un besoin théorique plutôt que pratique: accélérer asymptotiquement L'algorithme des chemins Les plus courts de Dijkstra. La file D'attente Brodal (et la structure de données fonctionnelle correspondante) ont été conçues de la même manière pour répondre à des garanties théoriques, en particulier, pour répondre à une question ouverte de longue date à savoir si il a été possible de faire correspondre les limites de temps D'un tas de Fibonacci avec des garanties du pire cas plutôt que des garanties amorties. En ce sens, les structures de données n'ont pas été développées pour répondre à des besoins pratiques, mais plutôt pour faire avancer notre compréhension théorique des limites de l'efficacité algorithmique. Pour autant que je sache, il n'y a pas d'algorithmes actuels dans lesquels il serait préférable d'utiliser une file D'attente Brodal sur un tas de Fibonacci.
comme l'indiquent d'autres réponses, les facteurs constants cachés dans un tas de Fibonacci ou une file D'attente de Brodal sont très élevés. Ils ont besoin de beaucoup de pointeurs connectés dans beaucoup de listes liées compliquées et, par conséquent, ont absolument terrible localité de référence, surtout par rapport à un tas binaire standard. Cela signifie qu'ils sont susceptibles d'effectuer pire dans la pratique étant donné les effets de mise en cache à moins que vous avez des algorithmes qui ont besoin d'un nombre colossalement élevé d'opérations de diminution-clé. Il y a des cas où cela se produit (les réponses liées parlez-en de quelques-uns, par exemple), mais traitez-les comme des circonstances hautement spécialisées plutôt que comme des cas d'usage courant. Si vous travaillez sur d'énormes graphiques, il est plus courant d'utiliser d'autres techniques pour améliorer l'efficacité, comme l'utilisation d'algorithmes d'approximation pour le problème en question, de meilleures heuristiques, ou des algorithmes qui utilisent des propriétés spécifiques des données sous-jacentes.
Espérons que cette aide!