Mettre en temps constant

Version imprimable

Bonjour, je souhaite mettre cette implantation en temps constant :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type
  ABin = ^_CellABin;
  _CellABin =
    record
     _suivG, _suivD : ABin
    end;
 
function Hauteur (a : ABin) : integer;
begin
  if EstVide(a) then
    Hauteur := 0
  else
    Hauteur := 1 + max(Hauteur(SAGauche(a)), Hauteur(SADroit(a)))
end;

(toutes les fonctions utilisées dans hauteur sont supposées définies)

J'ai mis ça pour que ce soit en temps constant mais ça n'a pas l'air correct :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type
  ABin = ^_CellABin;
  _CellABin =
    record
     _suivG, _suivD : ABin;
     _haut : integer;
    end;
 
function Hauteur (a : ABin) : integer;
begin
  if EstVide(a) then
    Hauteur := 0
  else
    Hauteur := a^._haut;
end;

03/12/2011, 13h47
droggo

Woe,

Il est déconseillé de commencer les identifiants par _, c'est généralement réservé à l'implémentation du compilateur, et de toute manière, ça n'ajoute rien à la lisibilité, au contraire.

Pour le temps constant, c'est pratiquement impossible pour une fonction si courte, tant en code qu'en exécution. Ça va - entre autres - dépendre du processeur, du moment de l'appel (par exemple : le code est-il déjà dans la mémoire cache ? Est-il appelé dans une suite linéaire d'instructions ou après un saut ? ...).

De plus, le code lui-même implique que le temps d'exécution change selon le résultat du test :
Déjà, le processeur ne mettra pas le même temps pour arriver dans un cas ou l'autre, et là-dessus s'ajoute :

Code:

Hauteur := 0

ramené au code généré, il s'agit d'une affectation d'une valeur immédiate.

Code:

Hauteur := a^._haut;

alors qu'ici on a une indirection (usage d'un pointeur), d'où accès au pointeur suivi de l'accès à la valeur.
03/12/2011, 14h33
matdu27

Oui, c'est sûr que sa ne sera pas tout à fait le même temps si c'est égal à 0..
Mais est ce que c'est correct au moins ?