samedi 16 septembre 2000

Récursivité

RÉCURSIVITÉ

La récursivité est la caractéristique d'un programme ou d'une procédure de s'appeler par lui-même (au moins une fois). Grâce à la récursivité, on peut résoudre de façon simple et concie de nombreux problèmes informatiques. Du fait de cette puissance, faut faire attention, car ce point positif peut revenir contre nous. Le programme ou la procédure peut s'ils ont mal été programmés s'appeler indéfiniment et causer l'arrêt de la machine. Il faut donc bien faire attention à la condition d'arrêt qu'on utilise.

Factoriel

Nous allons débuter par les factoriels. Voici la définition de la récurence des factoriels
n! = n * (n-1) * (n-2) * ... * 1
l! = 1
La fonction factorielle sans l'utilisation de récursion

function Factorielle(number:integer):integer;
var
  factoriel,i:integer;
begin
  if number = 0 then factoriel := 0
  else
  begin
    factoriel := 1;
    for i := number downto 1 do
      factoriel := factoriel * i
  end;
  result := factoriel;
end;

La fonction factorielle avec la récursion

function factorielle_recursion( n: integer): integer;
begin
  if n <= 0 then
    factorielle_recursion := 1  
  else
  result := n * factorielle_recursion( n - 1 ); {return n*(n-1)! }
end;

On peut remarquer que la fonction des factoriels qui utilise la récursion est plus courte. La pile est grandement
utilisée puisque que chaque appel à la fonction créée à nouveau les variables... le tout est ajouté à la pile. La récursivité
est un gouffre pour la mémoire.

Fibonacci

Voici la définition de la récurence de Fibonacci
Fib(n) = Fib(n-1) + Fib(n-2) for n > 1
Fib(0) = 0
Fib(1) = 1

La fonction fibonacci sans la récursion

function fibonacci(n:integer):integer;
var 
 i, Un, Un_1, Un_2 : integer;
begin
  Un_1 := 1 ;
  Un_2 := 1 ;
  for i:=2 to n do
  begin
    Un := Un_1 + Un_2 ;
    Un_2 := Un_1 ;
    Un_1 := Un ;
  end;
  result := Un ;
end;
La fonction fibonacci avec la récursion

function fib( n: integer): integer;
begin
  if n <= 1 then
    fib := n 
  else
    fib := fib(n-1) + fib(n-2); 
end;

Vous allez vous rendre compte rapidement des différences de performances qu'il y a entre les deux versions de 
fibonacci, et ce, aussitôt qu'une valeur de 20 et plus sera attribuée à n.
Pour de plus amples renseignements sur la récursivité, rendez-vous à l'excellent tutoriel sur Chambily.

Hashage

HASHAGE

Le hachage est une méthode est une méthode pour entreposer des données dans un tableau, liste... Les recherches, insertion et les effacements de données sont très rapide. La complexité est théoriquement de O(1). Pour arriver à un tel résultat, chaque valeur doit avoir sa propre clé. Il y a une fonction de hashage qui retourne la position.
Dans cet exemple, nous dirons que Jean hashe 0, Paul hashe 1...

0 Jean Durocher
1 Paul Rivet
2
3
4 Sam Piq
5 Eric Melvin
Il faut avoir une fonction de hashage qui permet de placer chaque clé au bon endroit. Il faut aussi décider ce qu'on va faire lorsque deux clés hashe la même valeur.
type
  THash_Record = record
  cle   : integer;
  donne  : integer;
end;

const
  HASH_LENGTH = 100;

type
  THash_Table = array[0..HASH_LENGTH-1] of THash_Record;

function fonction_hash(cle : integer) : integer;
begin
  Hash_Function := cle MOD HASH_LENGTH;
end;

procedure Inserer( var hash : THash_table;rec  : THash_record);
begin
  hash[ fonction_hash(rec.cle) ] := rec;
end;

Telle que je l'ai souvent vu, j'ai décidé d'employer le modulo pour la fonction d'hashage.
Il est possible lors d'insertion d'enregistrement qu'il y ait des collisions.
C'est-à-dire que deux clés différentes retournent la même adresse avec la même fonction de haschage.
En pratique ça arrive rarement, mais faut tenir compte de cette situation.

Nous allons un peu modifier la structure de départ pour nous adapter à cette réalité. La technique ici utilisée est dite ouverte. C'est-à-dire que nous allons mettre les éléments qui hashent sur la même valeur dans une liste. Cette méthode est moins performante.
const
  HASH_LENGTH = 100;

type
  PHash_Record = ^THash_Record;
  THash_Record = record
    cle   : integer;
    donne  : integer;
    prochain  : PHash_Record; //pointeur sur le prochain élément
  end;

THash_Table = array[0..HASH_LENGTH-1] of PHash_Record;

procedure Inserer( var hash : THash_Table; rec  : THash_Record);
var
  hash_address : integer;
  item         : PHash_record;
begin
  hash_address := fonction_hash(rec.cle);
  new(item);
  item^ := rec;
  item^.prochain = hash[ hash_address ];
  hash[ hash_address ] := item;
end;

procedure Obtenir(hash : THash_Table;cle  : integer; var rec  : THash_Record);
var
  hash_address : integer;
  item         : PHash_record;
begin
  hash_address := fonction_hash(rec.cle);
  item := hash[ hash_address ];
  while (item <> nil) and (item^.cle <> cle) do
    item := item^.next;
  if (item<>nil) then //si dans la liste
    rec := item^
end;

Maintenant si une clé retourne la même adresse de hashage (élément du tableau),
nous insérons cette donnée dans la liste de cette donnée hashé.

Afin d'améliorer les performances, il est possible au lieu de mettre les éléments qui hashent sur la même valeur dans la liste, d'utiliser des fonctions quadratiques ou faire du double hashage.

Optimisation


OPTIMISATION

L'optimisation dans un logiciel doit être une des dernières étapes de son développement. Avant de penser à optimiser un logiciel, il faut d'abord s'assurer que celui ne contiendra pas de bug. Rien ne sert d'optimiser au maximum un logiciel qui fait des erreurs sans arrêt. Vaut mieux primer sur la stabilité que l'optimisation.

Type d'optimisation

Lorsqu'on veut optimiser un logiciel on peut soit augmenter sa vitesse ou réduite la taille du programme. Habituellement lorsqu'on augmente sa vitesse, sa taille augmentera et vice versa. Le meilleur des deux mondes ne peut pas réellement être réunis. On verra quelques astuces pour augmenter l'efficacité de nos programmes. Les routines les plus susceptibles d'être optimisées sont celles étant souvent appelées.
On peut dénombrer plusieurs étapes pour optimiser un programme, en voici quelques une.
  • Compilation
  • Goulots d'étranglement
  • Structure et algorithme
  • Assembleur

Compilation

Avant de commencer à optimiser notre programme, nous pouvons choisir les meilleures directives de compilation pour avoir des performances optimales.



La case optimization permet de rendre actif l'optimisation du programme.

Optimisation faite pas Delphi

Registre

Les variables souvent utilisées ainsi que les paramètres sont directement mis dans les registres afin d'avoir du code plus rapide. Le compilateur vérifie aussi la durée de vie. Il peut ainsi placer plusieurs variables qui ne sont pas utilisées simultanément dans un même registre.

Élimination de la pile

Lorsque c'est possible, les paramètres sont placés dans les registres. Les intérêts sont mentionnées ci-dessus. Du même coup, ça évite de créer une pile pour y mettre les valeurs temporairement. Les instructions de création, d'élimination, d'ajout et de suppression pour la pile sont ainsi inexistantes. Lorsque plus de 3 paramètres sont utilisés dans une procédure ou fonction, le compilateur doit créer une pile. Sachant cela, lorsqu'il est possible de ne pas utiliser des paramètres ou du moins réduire leurs usages, on économise aussi l'accès au registre et la création d'une pile.

Élimination de code

Delphi n'inclut pas dans l'exécutable le code inutile. On peut remarquer ce genre de code par des pastilles lorsqu'on compile.


Goulots d'étranglement

Outils

Divers outils sur le marché permette de voir les points où l'on pourrait améliorer le code de notre logiciel. Ce genre d'application ce nomme des profilings.
Ce genre d'application permet en général de trouver les fuites mémoires, de savoir combien de temps prend une fonction ou une procédure à se dérouler... Chaque produit emmène son lot de nouvelle fonctionnalité. Il y a même des produits qui permettent de savoir si les api fonctionneront sur win9x, nt 2000,linux...

Nom du programme Adresse web
Memory Sleuth et Sleuth QA Suite Memory Sleuth et Sleuth QA Suite
MemProof MemProof
QTime QTime
DUnit DUnit
BoundsChecker BoundsChecker
ProDelphi ProDelphi

Avec ce genre d'outils, on sera en mesure de savoir où notre programme passe beaucoup de temps dans notre code. Le programme pourra ainsi être beaucoup plus facilement optimisé lorsqu'on connaît d'où viennent ses lacunes.
Ce genre d'outils facile grandement la vie des programmeurs, je vous conseille fortement de les essayer.

Structure et algorithme

Après avoir identifié les pointent faibles du programme avec les profilers, on peut dès lors commencer à améliorer leurs codes. Lorsqu'on améliore les performances d'un algorithme, on augmente sa taille. On doit trouver l'algorithme qui fait défaut et en prendre un plus performant.

Structure

Instruction if

Il arrive souvent que des gens utilisent ce genre de code dans leurs programmes au lieu d'utiliser le else if.

 
IF Cours=0 THEN lblNom.caption := 'francais';
IF Cours=1 THEN lblNom.caption := 'chimie';

C'est plus rapide d'utiliser ceci
IF Cours = 0 THEN lblNom.caption := 'francais';
ELSE IF Cours =1 THEN lblNom.caption := 'chimie';
ELSE lblNom.caption := 'autre';

ou la structure du choix multiple

CASE Cours OF
  0 : lblNom.caption := 'francais';
  1 : lblNom.caption := 'chimie';
  ELSE lblNom.caption := 'autre';
END;

Souvent, les langages de programmation ont des moyens de faciliter la vie des programmeurs. Très souvent ces moyens sont pénalisants côté vitesse.
Lorsqu'on utilise l'instruction suivante pour un intervalle donnée, le code est plus compact, mais moins performant.


IF Chiffre IN [3, 9, 11] THEN lblChiffre.caption := 'impair';

C'est plus performant ce code là

IF Chiffre i = 3 THEN lblChiffre.caption := 'impair';
ELSE IF Chiffre = 9 lblChiffre.caption := 'impair';
ELSE IF Chiffre = 11 lblChiffre.caption := 'impair';

Instruction for

Mes professeurs de C me l'ont assez souvent répété, c'est la boucle à utiliser lorsqu'on connaît le nombre d'itération à exécuter. C'est la plus rapide des boucles.

Nombre

Si vous avez un processeur inférieur aux Pentium 2 ou AMD k6 2 essayés d'utiliser faire des chiffres entiers.
Les opérations sont ainsi plus rapides et simples et ça demandera moins d'espace.
Les générations de processeur supérieur ont une unité spéciale de traitement dédié au nombre à virgule. Les opérations seront ainsi plus rapide que sur des nombres entiers.
Donc dépendant du type de processeur que vous avez, utilisez le format le plus adéquat
Utilisez le type de données adéquat en sachant que les types de données 32 bits sont plus rapides que celle n'ayant que 16 bits. Si vous voulez économiser de l'espace utilisé le type de donné approprié sinon pour la vitesse privilégiée les types 32bits

Les types entiers

Type Intervalle Format/taille
Byte 0..255 non signé, 1 octet
Shortint -128..127 signé, 1 octet
Char 0..255 non signé, 1 octet
Widechar 0..65 535 non signé, 2 octets
Smallint -32 768..32 767 signé, 2 octets
Word 0..65 535 non signé, 2 octets
Longint -2147483648.. 2147483647 signé, 4 octets
Integer -2147483648.. 2147483647 signé, 4 octets
Cardinal 0..4 294 967 295 non signé, 4 octecs
Int64 -9 223 372 036 854 775 808..9 223 372 036 854 775 807 signé, 8 octect

Les types réels

Type Intervalle Taille en octets
Real 2.9 10-39..1.7 1038 6
Double 5.0 10-324..1.7 10308 8
Real 2.9 10-39..1.7 1038 6
Extended 1.9 10-4951..1.1 104932 10
Comp -263+1..263-1 8
Currency -922337203685477.5808..
922337203685477.5807
8

Évitez de mélanger des chiffres à virgules flottantes, car il y aura des conversions qui devront être faites et elles seront ajoutées à la pile ce qui peut prendre 3 à 4 fois plus de temps.
N'utilisez pas le type variant, il est très lent et prend beaucoup de place. Certes on peut lui mettre n'importe quel type de donnée dedans, mais vous perdez beaucoup avec lui. Il y a toujours moyen de ne pas l'utilisez.
Les opérations les plus rapides sont les additions/soustraction viennent ensuite la multiplication et finalement la division.
Fraction -> nombre décimal
34/2 = 34 *.5
34 *.5 sera plus rapide que son équivalent fractionnaire. Lorsqu'on connait le nombre d'avance, choisissez le nombre décimal plutôt que la fraction.
Division -> multiplication
x/y = x* 1/y

Cette transformation est simple, on doit seulement inverser y et faire une multiplication
67/3= 67 * .33

Lorsque les nombres sont infinis tel que 1/3 on perd un peu de la précision. Alors on peut
ajouter quelques chiffres après la virgule afin d'augmenter le degré de précision.

Les exposants peut être remplacés par une multiplication
5 exposant 3 est plus lent que faire 5*5*5

Opérateurs logiques

Lors d'opération a base 2, on peut aisément supprimer les divisions et multiplication
par des décalages de bit.

donc exemple pour faire une division
shr 1 = divise par 2
shr 2 = divise par 4
shr 3 = divise par 8
shr 4 = divise par 16
shr 5 = divise par 32
shr 6 = divise par 64
shr 7 = divise par 128
shr 8 = divise par 256
.....
au lieu de x/2 on peut faire x shr 2
donc exemple pour faire une multiplication
shl 1 = multiplie par 2
shl 2 = multiplie par 4
shl 3 = multiplie par 8
shl 4 = multiplie par 16
shl 5 = multiplie par 32
shl 6 = multiplie par 64
shl 7 = multiplie par 128
shl 8 = multiplie par 256
...
au lieu de x*2 on peut faire x shl 2

Privilièger round à trunc

Trunc fait quelques manipulations sur le FPU qui sont très coûteux en temps, il vaut mieux utiliser round.

Variable locale

Il est avantageux d'utiliser des variables locales puisqu'elles peuvent être entreposées dans les registres du processeur. Une telle manoeuvre accélère beaucoup le traitement des données. Un gain important peut être fait en utilisant de telles variables dans une boucle. Il est souvent avantageux de copier des données dans une variable locale avant de l'utiliser. Ainsi, le temps système de copier est compensé par la réutilisation prompte des données copiées. Il y a une exception à cette règle, c'est les tableaux avec une dimension constante. Les mètres globaux feront économiser un registre durant les calculs.

Pointeur variable

On peut utiliser à notre avantage des pointeurs comme référence sur des données temporaires. Ces données temporaires seront optimisées dans les registres.

Liste chaîné vs tableau

dans la plupart des cas, les listes gagnent puisque la multiplication est devenue plus rapide avec les processeurs de nouvelle génération. Pour des accès aléatoires, tableau demeure le plus rapide pour n'importe types de données avec plus de 5 éléments. Les tableaux sont gagnants pour les types de données simples et les listes pour les complexes.

Statique vs Dynamique

Il arrive souvent que nous devions grouper des données, nous faisons alors appel au tableau. Jusqu'à la version 3 Delphi, nous étions obligés de créer des tableaux statistiques. Ce genre de tableau a une dimension fixe, on ne peut pas le réduire ou l'agrandir. Pour être sur de ne pas manquer de place, il fallait créer un tableau d'une grandeur immense. Maintenant, on peut faire appel au tableau dynamique. Ce genre de tableau nous permet d'épargner de l'espace.
La création d'un tableau dynamique est beaucoup plus lent qu'un tableau statistique, mais l'accès y est beaucoup plus rapide

Les procédures et fonctions

Faire appel aux procédures et fonctions augmente l'efficacité et la lisibilité du code, mais entraîne aussi une perte de performance (très peu). On doit savoir que plusieurs opérations sont faites sur la pile lors d'un appel. On ne doit pas arrêter leurs utilisations pour autant.
Pour ma part j'ai comparé l'appel d'une fonction 1 million de fois et l'exécution 1 millions du même code sans fonction. Au final, je n'ai même pas gagné 2 secondes...
Un point où l'on peut gagner aisément de la performance est le passage de paramètre.
Le passage par valeur doit recopier les variables qu'on passe à la fonction et le temps varient selon le type de variable: bytes, integer, variant...
Le plus rapide demeure le passage par adresse puisque la copie de l'adresse de la variable est passée. On utilise donc directement la variable en question. L'adresse d'une variable nécessite beaucoup moins d'espace qu'une variable.

Routine imbriqué

Imbriquer des routines ensemble ajoute des manipulations sur la pile pour que les variables de la routine externe puissent voir celle à l'interne. Beaucoup de temps système est ainsi perdu. Mettre les routines au niveau de l'unité et ajouter des paramètres tend à résoudre ce problème

String

Initialition

Le type de chaîne par défaut, AnsiString est initialisé automatiquement à vide. Il est donc inutile de le refaire.

Shortstring

Évitez ce type de donnée, depuis la version 5 de Delphi, ils sont convertis en longstrings avant d'être manipulés. Du temps est perdu durant ces convertions.

Privilièger Delete à copy

Copy copiera toujours la chaîne de caractères entière. Alors que delete découpera juste la fin de la chaîne.

Caster en pchar

La solution la plus rapide et la plus simple pour caster une string en pchar est de caster un pointeur. p:=pointer(s);

Trie

De nombreux algorithmes de tri existent dont un des plus rapide est le quicksort. On peut accélérer davantage le tri en ne bougeant pas les données. On peut s'échanger l'adresse entre pointeurs. Allez-voir dans la section des tris pour en savoir davantage

Fichier

Graphique

Réduisez le nombre de couleurs. Si vous employez des JPEG, optimisez-les en les compressant. Les fichiers gif sont favorisés par les petites tailles et leurs qualités.

Musical

Les wav deviennent rapidement gros, une solution consiste à employer des fichiers mp3. Si vous n'avez pas de parole dans la musique, utilisez les fichiers midi. Ils sont très petits.

Assembleur

L'assembleur est le langage le plus près de la machine, le plus rapide, mais aussi le plus incompréhensible. En utilisant l'assembleur, on réduit la lisibilité du code. Ce revers de la médaille ne sera connu que par le programmeur. L'appel à l'assembleur devrait se faire lorsqu'on a réellement besoin de vitesse: recherche, tri, encoder... car ça exige plus de temps de développement qu'utiliser un langage comme le pascale ou le c. On peut aussi utiliser les fonctions spécifiques au processeur comme le mmx, sse, sse2 3dnow... Ce genre d'instruction permet d'augmenter sensiblement les performances d'un programme faisant beaucoup appel au calcul.

Comme mettre le focus sur un contrôle?


Comme mettre le focus sur un contrôle?

form1.ActiveControl := Edit1;

lundi 11 septembre 2000

Comment mettre une image sur un bouton?

Comment mettre une image sur un bouton?
var
  Bitmap, Bitmap2: TBitmap;
  MyHandle: THandle;
  Rec: TRect;
begin
  Bitmap:=TBitmap.Create;
  Bitmap2:=TBitmap.Create;
  Bitmap2.LoadFromFile('c:\a.bmp');
  Rec:=Rect(2, 2, Button1.Width-2, Button1.Height-2);
  MyHandle:=GetDC(Button1.Handle);
  Bitmap.Canvas.Handle:=MyHandle;
  Bitmap.Canvas.StretchDraw(Rec, Bitmap2);
end;