Videos streaming images jeux et buzz
Connexion






Perdu le mot de passe ?

Inscrivez-vous maintenant !
Menu Principal
Communauté


(1) 2 »


-bNj-
[Programmation] Tri de tableau rapide
 0  #1
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
Voilà je cherche un algo ou un code de tri de tableau (int). Je cherche l'algo le plus rapide car je viens de m'apercevoir que la fonction Array.Sort en c# est extrement lente et sa convient pas du tout à mes besoins. Si quelqu'un à quelque chose d'interessant à me proposer je suis prenneur en attendant je continue mes recherches 😉

bNj

Contribution le : 20/01/2005 16:03
Signaler

-bNj-
 0  #2
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
bon ben en fait je viens de trouver => http://www-ipst.u-strasbg.fr/ipst/deug-ti/aide-c/tris/trirapid.htm#rapid (très bon site d'ailleurs) 😛

Contribution le : 20/01/2005 16:08
Signaler

Kinos
 0  #3
Je viens d'arriver
Inscrit: 16/10/2004 16:54
Post(s): 90
Tu peux aussi chercher l'algo Quicksort sur le net (tri avec pivot) trés connu...

Contribution le : 20/01/2005 17:02
Signaler

Mad_Donkey
 0  #4
Je masterise !
Inscrit: 16/01/2005 18:41
Post(s): 3004
et autre recommandation: n'utilise JAMAIS les fonctions standard de MS
surtout en .NET elles sont horriblement lentes et gourmandes en ressources 😉

Contribution le : 20/01/2005 17:11
Signaler

Peckos
 0  #5
Je suis accro
Inscrit: 16/01/2005 11:03
Post(s): 650
Je peut t'en faire une si tu veut ^^ je commence la programmation en C, je pense que il y aurai plus rapide mais pas sur 🙂

Contribution le : 20/01/2005 17:24
Signaler

-bNj-
 0  #6
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
ok Kinos je vais matter çà !
Merci pour vos réponses et en effet la fonction .NET Array.Sort est gourmande en ressource et lente puisqu'avec l'algo issu du lien si dessus j'ai gagné 10 secondes de traitement.
Pour info j'ai codé un programme en C# qui réalise le filtre antipoussière de Photoshop (filtre médian).
Le but de mon projet étant d'inserer des cotes sur une image.

Contribution le : 20/01/2005 17:56
Signaler

-bNj-
 0  #7
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
Citation :

Peckos a écrit:
Je peut t'en faire une si tu veut ^^ je commence la programmation en C, je pense que il y aurai plus rapide mais pas sur :)


balance ton code je vais le tester 😃

Contribution le : 20/01/2005 17:56
Signaler

Peckos
 0  #8
Je suis accro
Inscrit: 16/01/2005 11:03
Post(s): 650
Bah il me faudrait plus de detail, enfin je peut te faire une fonction il me faut juste les parametres que tu m'enverais ou des conneries dans le genre.
Tri de quoi?
Quel ordre? du plus petit au plus grand?
En faite il faudrait le tableau, et le nombre de poste.
C'est un tableau dynamique?
Moi je connais pour le tri que le balayage optimisé, je peut te faire un dessin pour t'expliquer mais y a surment plus rapide 🙂

Contribution le : 20/01/2005 22:31
Signaler

-bNj-
 0  #9
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
je souhaite trier un tableau de int avec 81 elements. Ordre croissant. Là je viens de de tester un nouvel algo de tri, le tri par insertion s'avère plus rapide que le tri shell la différence et d'environ 2 secondes sur une image de 2000 * 1300. Déjà gagné 12 secondes par rapport à la fonction Array.Sort 😃

Contribution le : 20/01/2005 23:04
Signaler

Peckos
 0  #10
Je suis accro
Inscrit: 16/01/2005 11:03
Post(s): 650
Bon bah j'ai fait ca, je sais meme pas si ca marche, mais essaye toujours, c'est une fonction qui recoi un tableau et un entier (nbp qui designe le nombre de poste rempli dans ce tableau, mais si ton tableau est toujours rempli enleve )
Et de toute facon tu as surment trouvé mieux, surtout que je ne sais meme pas si elle marche la fonction :



void TRIOP ( int T[] , int nbp )
{
int i , min , j , k ;

for ( i = 0 ; i < 81 ; i ++ )
{
for ( j = i + 1 , min = T[i] ; j < 81 ;j ++ )
{
if ( min > T[j] )
min = T[j] ;
k = j ;
}
T[k] = T[i] ;
T[i] = min ;
}
}

Contribution le : 21/01/2005 09:37
Signaler

Kinos
 0  #11
Je viens d'arriver
Inscrit: 16/10/2004 16:54
Post(s): 90
Citation :

-bNj- a écrit:
je souhaite trier un tableau de int avec 81 elements. Ordre croissant. Là je viens de de tester un nouvel algo de tri, le tri par insertion s'avère plus rapide que le tri shell la différence et d'environ 2 secondes sur une image de 2000 * 1300. Déjà gagné 12 secondes par rapport à la fonction Array.Sort :-D


Quoi ?? T'as gagné 12 secondes ??!! Mais combien de temps il prend (maintenant) pour trier ? Je pense qu'avec QuickSort, tu vas descendre facilement en dessous d'1 s pr trier 81 entiers... (en C, C++) Sachant que tu codes en C# et que je n'ai jamais codé/testé le C#, je peux pas te dire la différence de rapidité...

Tiens au fait, je t'ai trouve une implementation en C# ici:
http://en.wikipedia.org/wiki/Quicksort_implementations#C.23

Contribution le : 21/01/2005 10:01
Signaler

FrancoHab
 0  #12
Je m'installe
Inscrit: 02/11/2004 10:43
Post(s): 103
euh... comment est-ce possible de gagner 12 secondes en optimisant un algorithme de tri sur un tableau de seulement 81 éléments? 12 secondes, c'est une éternité pour un algorithme aussi basique qu'on algorithme de tri...

De plus, le gain de temps que procure un algo tel que le quicksort, ou le heapsort, ne commentce à être intéressant qu'avec de très grands tableaux à trier...

Contribution le : 21/01/2005 10:37
Signaler

Koreus
 0  #13
Webhamster
Inscrit: 03/07/2002 23:58
Post(s): 75328
Karma: 36947
Rien ne vaut le bubble sort ! 😃

Contribution le : 21/01/2005 10:47
_________________
Signaler

GrosBill
 0  #14
Je poste trop
Inscrit: 02/05/2004 21:49
Post(s): 12717
Karma: 77
Mais quelle idée de vouloir optimiser son code 🔨 🔨

Contribution le : 21/01/2005 11:02
_________________
Signaler

Kinos
 0  #15
Je viens d'arriver
Inscrit: 16/10/2004 16:54
Post(s): 90
Citation :

FrancoHab a écrit:
euh... comment est-ce possible de gagner 12 secondes en optimisant un algorithme de tri sur un tableau de seulement 81 éléments? 12 secondes, c'est une éternité pour un algorithme aussi basique qu'on algorithme de tri...


Je suis d'accord avec toi... j'sais pas ce qu'il a fait pour en arriver là 😉
Citation :

FrancoHab a écrit (suite):

De plus, le gain de temps que procure un algo tel que le quicksort, ou le heapsort, ne commentce à être intéressant qu'avec de très grands tableaux à trier...



C'est vrai, de plus, QuickSort est plus ch... à coder (Bon mais je lui ai dégoté un source en c#, alors, autant le réutiliser).

Citation :

Koreus a écrit:
Rien ne vaut le bubble sort ! 😃


Bubble Sort Powa 😃 !!!
Argh !! Non !! Meme sur des petits tris, juste par principe, ne pas utiliser le tri à bulles 😃 !!
Contribution le : 21/01/2005 11:26
Signaler

Peckos
 0  #16
Je suis accro
Inscrit: 16/01/2005 11:03
Post(s): 650
Mais c'est quoi tous ces tris? lol

Contribution le : 21/01/2005 11:58
Signaler

-bNj-
 0  #17
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
Citation :

FrancoHab a écrit:
euh... comment est-ce possible de gagner 12 secondes en optimisant un algorithme de tri sur un tableau de seulement 81 éléments? 12 secondes, c'est une éternité pour un algorithme aussi basique qu'on algorithme de tri...

De plus, le gain de temps que procure un algo tel que le quicksort, ou le heapsort, ne commentce à être intéressant qu'avec de très grands tableaux à trier...



parce que ma fonction tri est appellée (2000-8)*(1300-8) fois *3 (car je traite chaque couleurs de pixel RGB) 😃 2000*1300 c'est la résolution de l'image et le -8 parce que j'utilise une matrice 9*9 pour le filtrage.
Le principe d'un filtrage d'image c'est deplacer une matrice sur une image de faire un calcul avec les pixels de cette matrice et de remplacer la valeur du pixel du milieu de la matrice par ce calcul.

Contribution le : 21/01/2005 13:10
Signaler

FrancoHab
 0  #18
Je m'installe
Inscrit: 02/11/2004 10:43
Post(s): 103
Citation :
parce que ma fonction tri est appellée (2000*1300)-8 fois 2000*1300 c'est la résolution de l'image et le -8 parce que j'utilise une matrice 9*9 pour le filtrage.


ok, je comprends mieux... Mais je te conseille quand meme de ne pas utiliser le quicksort, car il est globalement moins efficace qu'un tri classique (par insertion par ex) sur des petits tableaux (car le gain de temps ne compense pas la place mémoire supplémentaire requise due aux appels récursifs...)

Si tu veux vraiment optimiser ton prog, je te conseillerai plutot de rendre les (2000*1300) tris parallèles (tu profitera ainsi de l'avantage des multi-processeurs ou de l'hyperthreading..)

Contribution le : 21/01/2005 14:16
Signaler

-bNj-
 0  #19
Je masterise !
Inscrit: 18/05/2004 23:15
Post(s): 4549
je pense que je vais rester sur ma fonction de tri par insertion. Voiçi la fonction :

public static byte tri(int[] t, int N)
{
for(int i = 1; i < N; i++)
{
int j=i;
int v=t[i];
while((j>0) && (v<t[j-1]))
{
t[j] = t[j-1];
j=j-1;
}
t[j]=v;
}

return (byte)t[40];
}

Par contre là je teste pour traiter directement une image en niveaux de gris plutot qu'une image couleur. Ainsi je vais diviser mon travail par 3 puisque je n'aurai plus la composante rouge,verte et bleu a traiter séparement. Car en niveaux de gris une image à les même valeurs pour le rouge vert et bleu. 😃
Je vais tester 😉

[Edit]
je passe sous la barre des 8 secondes avec la méthode çi dessus, çà me suffit amplement merc à tous 😉

Contribution le : 21/01/2005 16:57
Signaler

Peckos
 0  #20
Je suis accro
Inscrit: 16/01/2005 11:03
Post(s): 650
Il n'y a pas de quoi.
D'ailleur, tu a fait quoi comme etude?

Contribution le : 21/01/2005 20:06
Signaler


 Haut   Précédent   Suivant
(1) 2 »






Si vous êtes l'auteur d'un élément de ce site, vous pouvez si vous le souhaitez, le modifier ou le supprimer
Merci de me contacter par mail. Déclaré à la CNIL N°1031721.