Question d'optimisation d'algo

Version imprimable

29/03/2007, 16h03
snoopo

Question d'optimisation d'algo[Rectification]

Salut,
Il a une question que je pose à propos des tableaux. D'après vous qu'est qui est mieux utiliser 2 tableaux simples ou un tableau à double entrée.
Vous allez s'en doute me dire que ça dépend des circonstances et aussi comment est énoncé le sujet. Mais supposons ce cas. J'ai fait un algo ou je dois compter combien de fois un chiffre est apparu. Pour cela j'ai créé un tableau constant(qui contient, allez 5 chiffres) et un autre tableau appellé fréquence. Mais je me demande s'il n'est pas préférable d'utiliser un tableau à double entrée.
Question optimisation laquelle sera la meilleur solution ?
Merci :mrgreen:
29/03/2007, 16h20
pseudocode

Citation:

Envoyé par snoopo

Vous allez s'en doute me dire que ça dépend des circonstances et aussi comment est énoncé le sujet.

Ca depend surtout de ce que represente ton tableau. Pour representer une matrice, un tableau a double entrée ca semble plus naturel.

Ca depend aussi du langage (performance d'accès aleatoire/iteraif, mémoire, ...)
29/03/2007, 17h05
parp1
Moi je sais qu'en python j'utilise le plus souvent possible les tableaux a une entre pour les images. Pour un simple seuillage c'est plus rapide de faire :
Code:

1 2 3 for i=0,hauteur*largeur: if tab[i]>seuil : tab[i]=255 i++
que de faire :
Code:

1 2 3 4 5 6 for i =0 ;hauteur: for j = 0 ; largeur: if tab[i][j]>seuil :tab[i][j]=255 j++ i++
Apres pour ce qui est convolution amincissement s'il y a une solution 1D faites moi signe parcque je suis preneur....

C'est a toi de voire... la taille des images.... etc
30/03/2007, 14h22
snoopo

hmmm ... d'accord.
J'ai bien ce que je pensais. Je crois que je vais rester sur mon idée originale.
30/03/2007, 14h40
pseudocode

Citation:

Envoyé par parp1

Moi je sais qu'en python j'utilise le plus souvent possible les tableaux a une entre pour les images.

Il y a rapide et rapide :mrgreen:

- Plus rapide a coder, car moins de code a ecrire.

- Plus rapide a executer, car parallelisable.

Par exemple pour répartir des calculs sur une image, c'est mieux de faire une liste de petits tableaux 2D.
30/03/2007, 14h53
souviron34

mais comme on sait pas plus sur ton problème, on aura bien du mal à te conforter par rapport à ton "idée originale", pusiqu'on la connaît pas, ni le problème ... :aie:
31/03/2007, 11h48
snoopo

Citation:

souviron34 a écrit :
mais comme on sait pas plus sur ton problème, on aura bien du mal à te conforter par rapport à ton "idée originale", pusiqu'on la connaît pas, ni le problème ...

Ben enfin compte, il s'agit d'un algo ou il faut rendre la monnaie. On a des billets de 50,20,10,5,2. Puis afficher combien de fois ces chiffres sont apparus.
Ce que j'ai fait c'est iniatiliser un tab const qui recoit les valeurs 50,20,10,etc.. et un autre tableau qui compte pour chacun d'eux le nombre de fois ils sont apparus.
Je me demandais s'il n'était pas préférable de faire tout ceci dans un tableau à double dim pour une question d'optimisation d'algo.
31/03/2007, 13h28
souviron34

Bon ben par rapport à ce problème, non c'est pas mieux d'avoir un tableau à 2 dims.

En fait, tu fais un histogramme.

Donc soit 2 tableaux (quelque soit le problème tu ne parcoures que 1 fois le nombre max), soit un tableau de structures (ce que je ferais) :

structure billet

int valeur
int nb
31/03/2007, 17h13
Trap D

Si c'est pour rendre la monnaie, ce fil peut t'intéresser.
11/04/2007, 16h13
snoopo

Désolé de remonter un topic résolu mais je voulais en avoir le coeur net concernant. J'ai discuté avec le prof, pour lui utiliser un tableau à 2 dimensions est la meilleur solution. D'une part pourquoi faire 2 fois le meme traitement alors qu'avec un tableau à double dimension on fait cela en un seul traitement. D'autre part, 2 tableaux à 1 dim prennent plus de place quelque soit le langage, 2 indexations dans l'espace mémoire au lieu d'une seul pour le double dim.
Voila, voila qu'est que vous en pensez ?
11/04/2007, 16h35
mchk0123

Entre ton prof et toi, vous pouvez trés bien avoir raison tous les 2. Tout dépend à quelle question on répond :

- améliorer la lisibilité du code ?
- améliorer l'occupation en mémoire ?
- améliorer la vitesse d'exécution ?

Malheureusement il n'existe pas de solution meilleure pour les 3 questions.

Je penses que dans ton cas tu devrais suivre les intuitions de ton prof., je penses que s'il te conseille de faire comme ça c'est parce que dans la suite de tes études et dans le milieu professionnel cela te sera plus utile.

N'oublie pas qu'il peut te poser d'autres questions toujours sur le même exercice. Donc la solution qu'il te propose est peut-être pour te faciliter la tâche pour la suite.
12/04/2007, 16h35
femtosa

Citation:

Envoyé par snoopo

D'autre part, 2 tableaux à 1 dim prennent plus de place quelque soit le langage, 2 indexations dans l'espace mémoire au lieu d'une seul pour le double dim.

8O

Je ne comprends pas quand tu dis 2 indexations dans l'espace mémoire ...

En C par exemple, j'ai toujours cru qu'un tableau à 2 dimensions était strictement égale à un tableau à 1 dimension (en termes d'espace mémoire utilisé !) :!:

Me trompe-je ... :question:
12/04/2007, 18h29
pseudocode

Citation:

Envoyé par snoopo

Désolé de remonter un topic résolu mais je voulais en avoir le coeur net concernant. J'ai discuté avec le prof, pour lui utiliser un tableau à 2 dimensions est la meilleur solution.

j'ai tendance a me mefier quand on parle de "LA solution", universellement meilleur que toutes les autre... :roll:

Citation:

D'une part pourquoi faire 2 fois le meme traitement alors qu'avec un tableau à double dimension on fait cela en un seul traitement.

Il y a plein de raisons de preferer faire 2 fois un traitement simple, plutot qu'une seule fois un traitement complexe.

La parallelisation: Hyper-threading, multi-core, distributed computing, grid computing, ... sans parler des hardware dédiés (DSP et autres).

La simplicité: C'est plus simple de faire une composition de 2 transformées de fourier 1D, que d'en faire une seule en 2D.

Citation:

D'autre part, 2 tableaux à 1 dim prennent plus de place quelque soit le langage, 2 indexations dans l'espace mémoire au lieu d'une seul pour le double dim.

Deja pas en C, c'est equivalent. C'est meme plus rapide d'acceder a un tableau 1D (indice = offset) qu'a un 2D ( indice = offsetY * SizeX + OffsetX ).

Enfin bref, il n'y a pas de "meilleur solution universelle".
12/04/2007, 19h46
mchk0123

Citation:

Envoyé par pseudocode

La parallelisation: Hyper-threading, multi-core, distributed computing, grid computing, ... sans parler des hardware dédiés (DSP et autres).

Là c'est un autre monde ;)
12/04/2007, 21h21
pseudocode

Citation:

Envoyé par mchk0123

Là c'est un autre monde ;)

Un monde pas si loin... le processeur multi-core est le "standard" des PC actuel. Autant commencer a écrire du code parallelisable.
15/04/2007, 10h10
mchk0123

C'est juste que si tu analyse bien la question d'origine : qu'est ce qui est plus rapide : 1 tableau à double entrée par opposé à 2 tableaux à simples entrée, on est à des années lumières de notions comme le multithreading multicore ...

Mais je suis tout à fait d'accord avec toi pour dire que dés aujourd'hui les solutions multithreadées et multicores sont disponibles et les développeurs doivent faire avec.