Discussion :

[bazoga]

Bonjour,

cher pro, je veux trouver un algorithme qui renvoi le maximum d'un tas, j'ai trouvé une solution (naïve:parcourir l'arbre en comparant à chaque fois le nœud avec le max), mais il m'apparait que cette solution n'est pas optimale en effet le nombre de comparaison effectué est égale à la taille de l'arbre, or je sais très bien que le max est exclusivement parmi les feuilles de l'arbre.

svp aidez moi à trouver la réponse


Rappel:
Un tas est un arbre binaire où un entier est associé à chaque noeud avec les propriétés suivantes: il est quasi complet (tous les niveaux sont remplis sauf éventuellement le dernier où tous les éléments sont rangés à gauche) et la valeur d'un noeud est inférieure ou égale à celles de tous ses fils.

[pseudocode]

Je ne pense pas qu'il y ait une méthode miracle pour trouver le max d'un tas-minimum, ni le min d'un tas-maximum.

[SpiceGuid]

+1
Par contre il existe des structures de tas-min-max, qui sont à la fois un tas-min et un tas-max.

[bazoga]

Bonjour,

Je ne pense pas qu'il y ait une méthode miracle pour trouver le max d'un tas-minimum, ni le min d'un tas-maximum.

Donc a votre avis, il suffit de parcourir l'arbre et trouver le max ==> complexité O(taille) ?!!

Merci pour vos réponse

[SpiceGuid]

Tu as l'air d'oublier une caractéristique essentielle des arbres complets: le nombre de noeuds est égal au nombre de feuilles - 1.

Du coup, sur un arbre quasi-complet, O(taille) ou O(feuilles), c'est bonnet-blanc et blanc-bonnet.

Par contre mon message veux bien dire que ça n'est pas optimal, si tu as autant besoin du max que du min alors il faut opter pour un tas-min-max au lieu d'un simple tas-min.

[edfed]

il n'existe surement pas d'algorithme magique pour cette operation, mais il existe des instructions SSE/SSE2/SSE4.1/AVX pour le faire plus vite sur les CPU X86, il faut s'en assurer en verifiant leur presence grace à CPUID.

si l'algo doit etre appliqué pour un de ces processeurs, il sera bon d'imposer leur utilisation au compilateur.

PMAXSB, PMAXUB, PMAXSW, PMAXUW, PMAXSD et PMAXUD permettent de comparer des octets, des word ou des dword simultanément par paires afin de detecter le maximum.
PMAXSB permet de comparer 8 paires d'octets signés en une seule fois sur les registres SSE 128 bits, et 32 octets sur les registres AVX 256 bits.

il faut d'abord extraire toutes les valeurs à comparer, puis les mettre sous forme de listes de 16 ou 32 octets (si ce sont des octets) avant d'effectuer l'operation.

pour les word (16 bits) et dword (32 bits) le nombre de comparaisons simultanés sera moindre, mais toujours plus qu'une comparaison unique.

il existe la meme chose pour le MIN.

PMINxx, avec xx=SB, UB, SW, UW, SD, UD.