| -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 :
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 :
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): 75377
Karma: 36948 |
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 :
Je suis d'accord avec toi... j'sais pas ce qu'il a fait pour en arriver là Citation :
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 :
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 :
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
|
|
|