Je suis à la recherche d'informations sur la façon de mettre en œuvre binaire des tas de manière efficace. Je me sens comme il devrait y avoir un article de nice, quelque part sur la mise en œuvre des tas de manière efficace, mais je n'ai pas trouvé un. En fait, j'ai été incapable de trouver toutes les ressources sur la question de l' efficacité de la mise en œuvre au-delà des notions de base comme le stockage en tas dans un tableau. Je suis à la recherche pour les techniques pour faire un rapide tas binaire au-delà de celles que je décris ci-dessous.
J'ai déjà écrit une implémentation C++ est plus rapide que Microsoft Visual C++et GCC est std::priority_queue ou de l'utilisation de std::make_heap, std::push_heap et std::pop_heap. Voici les techniques que j'ai déjà couvert dans mon œuvre. Je l'ai seulement avec les 2 derniers moi-même, bien que je doute que ce sont de nouvelles idées:
(Edit: ajout d'une section sur l'optimisation de la mémoire)
Commencer les index à 1Regarder le Wikipedia de mise en œuvre de notes pour les binaires des tas. Si le tas est la racine est mis à l'index 0, alors les formules pour les parents, à gauche de l'enfant et de droit de l'enfant du nœud d'indice n sont respectivement (n-1)/2, 2n+1 et 2n+2. Si vous utilisez une base de 1 tableau puis les formules de devenir le plus simple n/2, 2n et 2n + 1. Donc, parent et à gauche de l'enfant sont plus efficaces lors de l'utilisation d'un 1-tableau. Si p pointe vers un 0 tableau et q = p - 1, alors nous pouvons accéder p[0] q[1] donc, il n'y a pas de frais généraux à l'aide d'un 1-tableau. Faire pop/suppression de déplacer l'élément vers le bas de segment de mémoire avant de le remplacer avec de la feuille
Pop sur un segment de mémoire est souvent décrite par le remplacement de l'élément le plus à gauche en bas de la feuille, puis en les déplaçant vers le bas jusqu'à ce que le segment de la propriété est restaurée. Cela nécessite 2 comparaisons par niveau, que nous allons par la, et nous sommes susceptibles d'aller très loin sur le tas depuis que nous avons déménagé une feuille au-dessus de la masse. Donc, nous devrions nous attendre à un peu moins de 2 log n comparaisons.
Au lieu de cela, on peut laisser un trou dans le tas où l'élément a été. Ensuite, nous passons ce trou en bas du tas par itérative en mouvement le plus grand enfant. Cela nécessite seulement 1 comparaison par niveau que nous allons passé. De cette façon, le trou va devenir une feuille. À ce stade, nous pouvons nous déplacer le plus à droite en bas de la feuille dans la position du trou et de se déplacer que d'une valeur jusqu'à ce que le segment de la propriété est restaurée. Puisque la valeur, nous avons déménagé était une feuille nous ne nous attendons pas à aller très loin vers le haut de l'arbre. Donc, nous devrions nous attendre à un peu plus de log n comparaisons, ce qui est mieux qu'avant.
Soutien remplacez-hautSupposons que vous souhaitez supprimer le max élément et également d'insérer un nouvel élément. Ensuite, vous pouvez effectuer l'enlèvement/pop implémentations décrit ci-dessus, mais au lieu de se déplacer le plus à droite en bas de la feuille, vous utilisez la nouvelle valeur que vous souhaitez insérer/push. (Quand la plupart des opérations de ce genre, j'ai trouvé qu'un tournoi arbre est mieux qu'un tas, mais sinon, le tas est un peu mieux.) Faire sizeof(T) d'une puissance de 2
Le parent, à gauche de l'enfant et de droit de l'enfant de formules de travail sur les index et ils ne peuvent pas être réalisés de travailler directement sur les valeurs de pointeur. Donc, nous allons travailler avec des index et qui implique la recherche de valeurs p[i] dans une matrice p à partir d'un index-je. Si p est un T* et i est un entier, alors
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i
et le compilateur doit effectuer ce calcul pour obtenir p[i]. sizeof(T) est une constante de compilation, et la multiplication peut être fait de manière plus efficace si sizeof(T) est une puissance de deux. Mon œuvre a obtenu plus rapidement par l'ajout de 8 octets de remplissage pour augmenter sizeof(T) de 24 à 32. Réduction de l'efficacité du cache signifie probablement que ce n'est pas une victoire pour suffisamment grands ensembles de données.
Pré-multiplier les indicesC'était un de 23% d'augmentation de la performance sur mon jeu de données. La seule chose que nous jamais faire avec un indice autre que de trouver un parent, à gauche de l'enfant et de droit de l'enfant est de regarder l'index dans un tableau. Donc, si nous gardons la trace de j = sizeof(T) * i au lieu d'un indice i, alors on pourrait faire une recherche p[i] sans la multiplication qui est par ailleurs implicite dans l'évaluation de p[i] parce que
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j
Puis la gauche-l'enfant et le droit de l'enfant formules pour j-valeurs deviennent respectivement les 2*j et 2*j + sizeof(T). Le parent formule est un peu plus compliqué, et je n'ai pas trouvé un moyen de faire d'autres que de la conversion de la j-valeur à une valeur et à l'arrière de la sorte:
parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)
Si sizeof(T) est une puissance de 2, alors cela permettra de compiler pour 2 équipes. C'est 1 de plus que l'habituelle parent à l'aide des indices de je. Cependant nous avons ensuite enregistrer 1 de l'opération sur la recherche. Donc l'effet net est que de trouver le parent prend la même quantité de temps de cette façon, tandis que la recherche de la gauche-l'enfant et le droit de l'enfant devient de plus en plus vite.
Optimisation de la mémoireLes réponses de TokenMacGuy et templatetypedef point de la mémoire en fonction des optimisations qui permettent de réduire les défauts de cache. Pour les très grands ensembles de données ou peu utilisée files d'attente de priorité, les pièces de la file d'attente peut être transférée sur le disque par le système d'exploitation. Dans ce cas, il vaut mieux ajouter beaucoup de frais généraux pour une utilisation optimale de la cache, car la permutation à partir du disque est très lent. Mes données s'intègre facilement dans la mémoire et est en usage continu, de sorte qu'aucune partie de la file d'attente sera susceptible d'être échangé sur le disque. Je soupçonne que c'est le cas pour la plupart des utilisations de files d'attente de priorité.
Il y a d'autres files d'attente de priorité qui sont conçus pour faire une meilleure utilisation du cache du PROCESSEUR. Par exemple, un 4-tas doit avoir moins de défauts de cache et le montant des frais généraux supplémentaires n'est pas tant que ça. LaMarca et Ladner rapport, en 1996, qu'ils obtiennent 75% d'amélioration des performances de va aligné 4-tas. Cependant, Hendriks rapports, en 2010, que:
QuestionLes améliorations apportées à l'implicite tas suggéré par LaMarca et Ladner [17] afin d'améliorer la localité des données et de réduire les défauts de cache ont également été testés. Nous avons mis en œuvre un four-way tas, qui montre en effet un peu plus de consistance que le segment de mémoire pour très biaisée des données d'entrée, mais seulement pour les très grandes tailles de file d'attente. De très grandes tailles de file d'attente sont mieux traités par le hiérarchique tas.
Il n'y a plus techniques que ceux-ci?
