La structure des données impact sur l'algorithme à choisir. Une structure simple peut faire en sorte qu'un algo n2 soit plus rapide qu'un log(n). (le cas typique est le trie à bulle d'une liste déjà "bien" trié) : genre un bète tableau indexé par un entier peut être bien plus rapide qu'un hash ou qu'un arbre binaire, si la structure est à haute densité on ne perd pas trop de place.
En général, les études d'algorithmes que l'on lit dans les livres considèrent que tout acces mémoire est à cout constant. Or un caches miss c'est de 20 à 200 cycles de perdu.
La structure de donné permet d'augmenter un peu la localité statique des données (genre écrire tab[100][3] et non tab[3][100] si on utilise les 3 élèments de suite à chaque fois)
un autre conceil : ne jamais utiliser de pointeur !! il faut utiliser un tableau. Les const aident aussi le compilo.
[^] # Re: break, goto...
Posté par Nicolas Boulay (site web personnel) . En réponse au journal Informatique : Optimisation, minimisation, projet. Évalué à 1.
La structure des données impact sur l'algorithme à choisir. Une structure simple peut faire en sorte qu'un algo n2 soit plus rapide qu'un log(n). (le cas typique est le trie à bulle d'une liste déjà "bien" trié) : genre un bète tableau indexé par un entier peut être bien plus rapide qu'un hash ou qu'un arbre binaire, si la structure est à haute densité on ne perd pas trop de place.
En général, les études d'algorithmes que l'on lit dans les livres considèrent que tout acces mémoire est à cout constant. Or un caches miss c'est de 20 à 200 cycles de perdu.
La structure de donné permet d'augmenter un peu la localité statique des données (genre écrire tab[100][3] et non tab[3][100] si on utilise les 3 élèments de suite à chaque fois)
un autre conceil : ne jamais utiliser de pointeur !! il faut utiliser un tableau. Les const aident aussi le compilo.
"La première sécurité est la liberté"