Discussion :

[gerald3d]

Petit problème.

Je dois charger une image I de taille (x,y). I est composéede trois composantes R,V,B. Je dois trier ces composantes par ordre croissant pour en extraire la médiane de chacune d'elle.

Ma première idée a été d'utiliser une GList (ou GSList, ca ne change rien au principe) puis je me suis dit que finalement les g_array feraient tout aussi bien l'affaire.

La question est donc : les g_array sont-ils plus appropriés pour ce genre de travail? A moins qu'une autre méthode mieux adaptée existe?

(Oui je sais là ca fait 2 questions, mais bon...)

[teuf13]

Un GArray, ou même un tout bête unsigned char * (enfin 3, 1 pour chaque composante) me paraissent plus appropriés qu'une GList

[gerald3d]

Disons pour approfondir que je me pose la question entre ces deux moyens parce qu'ils disposent tous les deux d'une fonction de tri toute faite. La roue étant déjà inventée...

[teuf13]

Une GList, c'est un peu du gâchis, tu vas allouer un élément de liste pour chaque pixel, ça va faire un beau paquet d'allocations au final, et les données vont être éparpillées un peu partout en mémoire (ce que le cache du processeur n'aime pas trop). Avec un tableau, tu feras une seule allocation, et tout sera au même endroit.

[liberforce]

Liste chaînée
Avantages
ajout/suppressions rapide d'éléments (temps constant)

Inconvénients
parcours des éléments lent
accès au n-ième élément lent (il faut parcourir la liste à partir du premier élément)

Tableau dynamique :
Avantages :
parcours des éléments rapide
accès au n-ième élément rapide

Inconvénients
insertion/suppression d'éléments lent

Là dans ton cas, tu connais déjà le nombre d'éléments que tu as à stocker, et tu peux les stocker tous à la suite. Une liste n'est pas adaptée.

Tu peux bien sûr utiliser un tableau dynamique comme GArray, et utiliser ses fonctions de tri, ou bien un tableau de taille fixe alloué par un simple g_new ou g_malloc, suivi d'un appel à la fonction qsort de la libc qui fait un tri de type quicksort.

http://fr.wikipedia.org/wiki/Liste_c...3%A9e#Principe
http://fr.wikipedia.org/wiki/Tableau...ces_et_limites

[teuf13]

Liste chaînée
Avantages
ajout/suppressions rapide d'éléments (temps constant)

Ajout/suppression rapide d'éléments : uniquement si c'est au début de la liste dans le cas des GList/GSList ou si on a déjà un pointeur sur l'élément après lequel on va ajouter/supprimer un élt (en gros). Sinon c'est linéaire avec la taille de la liste.