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.

[liberforce]

Oui, c'est l'insertion avant/après un élément connu (pour lequel tu as déjà un pointeur) qui est rapide. Mais en général pour l'insertion, tu sais déjà après ou avant qui tu veux mettre le nouvel élément... On est d'accord que si tu veux faire un append (rajouter un élément à la fin de la liste) et que tu n'as un pointeur que sur le début de la liste tu as une complexité O (n).

C'est pour ça qu'en général quand tu dois ajouter plein d'éléments à la suite dans une liste dans un ordre précis, tu fais un g_list_prepend (pour les ajouter en début de liste, opération en temps constant), puis un g_list_reverse qui retourne la liste (le premier élément devient le dernier et inversement).

Le tableau a en revanche toujours une pénalité si tu n'ajoutes pas ton nouvel élément à la suite des autres...

[gerald3d]

Finalement je peux utiliser le framework g_qsort_with_data(); de la glib je pense.
J'initialise 3 tableaux triés avec cette fonction. Qu'en pensez-vous?

[teuf13]

C'est pour ça qu'en général quand tu dois ajouter plein d'éléments à la suite dans une liste dans un ordre précis, tu fais un g_list_prepend (pour les ajouter en début de liste, opération en temps constant), puis un g_list_reverse qui retourne la liste (le premier élément devient le dernier et inversement).

Si ta liste est initialement vide...

[liberforce]

Finalement je peux utiliser le framework g_qsort_with_data(); de la glib je pense.
J'initialise 3 tableaux triés avec cette fonction. Qu'en pensez-vous?

Ce serait un bon choix si tu avais besoin d'une information particulière et relative pour faire ton tri (d'où le g_qsort_with_data). Or d'après ce que j'ai compris, ce n'est pas le cas, puisque tu veux juste la valeur médiane de chaque canal RGB. Tu as donc juste à créer le tableau, le trier, puis trouver la médiane au milieu du tableau (dont tu connais la taille). qsort sera plus efficace.

Au passage, ce n'est pas ce qu'on appelle un framework.

[liberforce]

Si ta liste est initialement vide...

Certes, ce qui est le cas ici, c'est pour ça que je ne l'ai pas précisé. Mais si le nombre d'éléments est très grand, il peut même être intéressant de retourner la liste une première fois, faire des prepend, puis la retourner une seconde fois.