Discussion :

[gorgonite]

pour un petit million d'entiers

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m1.934s
user    0m1.914s
sys     0m0.014s

ma machine... Centrino 1.8Ghz


[EDIT]j'avais oublié d'écrire le résultat sur le disque... ça m'étonnait d'être aussi bon [/EDIT]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m3.068s
user    0m3.013s
sys     0m0.049s

pour infos, il s'agit d'un programme en ocaml, compilé avec ocamlopt sans optimisations...

ps: si quelqu'un connait ces options, je suis preneur

[Jean-Marc.Bourguet]

Il faudrait un moyen de comparer dans les mêmes conditions pour avoir une idée d'où on se situe. Malheureusement, c'est difficile de faire ça et de participer en même temps.

Peut-être quelque chose à mettre en place par les organisateurs?

[gorgonite]

pour un petit million d'entiers

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m1.934s
user    0m1.914s
sys     0m0.014s

ma machine... Centrino 1.8Ghz


[EDIT]j'avais oublié d'écrire le résultat sur le disque... ça m'étonnait d'être aussi bon [/EDIT]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m3.068s
user    0m3.013s
sys     0m0.049s

pour infos, il s'agit d'un programme en ocaml, compilé avec ocamlopt sans optimisations...

ps: si quelqu'un connait ces options, je suis preneur

soyons joueur... je l'ai refait en C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m0.904s
user    0m0.864s
sys     0m0.027s

[EDIT]quelques raffinements heuristiques sur le choix du pivot du quicksort[/EDIT]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m0.543s
user    0m0.517s
sys     0m0.021s

[davcha]

Il faudrait un moyen de comparer dans les mêmes conditions pour avoir une idée d'où on se situe. Malheureusement, c'est difficile de faire ça et de participer en même temps.

Peut-être quelque chose à mettre en place par les organisateurs?

Si on veut comparer dans les mêmes conditions, à mon avis, l'idéal est encore de divulguer les sources, non ?

De cette manière chacun pourra comparer lui-même. Bon par contre, c'est peut-être pas l'idéal pour le concours, effectivement.

[Jean-Marc.Bourguet]

[EDIT]quelques raffinements heuristiques sur le choix du pivot du quicksort[/EDIT]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m0.543s
user    0m0.517s
sys     0m0.021s

Je m'étonne un peu des différences... nous sommes d'accord qu'il s'agit bien d'entiers non signés sur 64 bits? Tes temps sont proches de ce que j'optiens en 32 bits.

[gorgonite]

Je m'étonne un peu des différences... nous sommes d'accord qu'il s'agit bien d'entiers non signés sur 64 bits? Tes temps sont proches de ce que j'optiens en 32 bits.

j'ai déconné... l'algo ne marche plus, mais il va vite

j'avais pas vérifié désolé


[EDIT]

je repars de zéro
voici mon nouvel algo en C...


[EDIT2]

semblerait que je sois pas en 64bits...

[EDIT3]

je suis enfin en 64bits... et les résultats sont en fait médiocres

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m1.227s
user    0m1.186s
sys     0m0.038s

[EDIT4]

je suis revenu au quicksort

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m0.876s
user    0m0.845s
sys     0m0.027s

[EDIT5]
j'avais oublié le non-signé... mais ça ne changeait rien aux perfs
pour me faire pardonner, un petit Makefile

[EDIT6]
pour infos, j'ai trouvé un tri qui semble pouvoir largement battre ces perfs... le flashSort ; mais je n'arrive pas à le faire trier
pourtant il ne semble y avoir de contre-indications

il tournait en 0.6 seconde


[EDIT7]
un nouvel algorithme... bien plus efficace

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
real    0m0.342s
user    0m0.318s
sys     0m0.019s

j'avoue c'est une variante du tri par dénombrement, et j'ai supposé que tous les termes étaient entre 0 et 10millions...

[Jean-Marc.Bourguet]

j'avoue c'est une variante du tri par dénombrement, et j'ai supposé que tous les termes étaient entre 0 et 10millions...

Le plus petit nombre dans mon jeux de donnée aléatoire de 1M nombres est 19207989919375

[gorgonite]

Le plus petit nombre dans mon jeux de donnée aléatoire de 1M nombres est 19207989919375

c'était juste une blague...


au fait, je n'ai pas vu d'autre temps

[Jean-Marc.Bourguet]

au fait, je n'ai pas vu d'autre temps

Ça va venir... j'ai encore un peu de tuning à faire. J'ai amélioré un petit peu le mien... Tiens pour avoir une base de comparaison, je vais aussi mesurer sur ma machine le programme que tu as donné.

[gorgonite]

Ça va venir... j'ai encore un peu de tuning à faire. J'ai amélioré un petit peu le mien... Tiens pour avoir une base de comparaison, je vais aussi mesurer sur ma machine le programme que tu as donné.

pas la peine... je me ferais battre à plat de couture

[Jean-Marc.Bourguet]

Ça va venir... j'ai encore un peu de tuning à faire. J'ai amélioré un petit peu le mien... Tiens pour avoir une base de comparaison, je vais aussi mesurer sur ma machine le programme que tu as donné.

Voilà, mon meilleur programme pour le moment fait 1.24s (et celui de Gorgonite où j'ai utilisé strtoull à la place de atoi fait 3.85s). C'est la moyenne sur 100 mesures, elles s'étalent de 1.19 à 1.32s.

Pour le moment, je suis un peut déçu... pas tant par le temps mais par la méthode avec laquelle je l'ai optenu. J'ai encore une ou deux idées à tester, j'espère que j'arriverai à battre ce temps.

[gorgonite]

Voilà, mon meilleur programme pour le moment fait 1.24s (et celui de Gorgonite où j'ai utilisé strtoull à la place de atoi fait 3.85s). C'est la moyenne sur 100 mesures, elles s'étalent de 1.19 à 1.32s.

je me suis fait défoncé... mais pire que ce que j'imaginais

ps: quel langage ?


ben je vais me le refaire en asm

[Jean-Marc.Bourguet]

je me suis fait défoncé... mais pire que ce que j'imaginais

Il y a un truc

ps: quel langage ?

C++.

(Oops, j'édite à la place de citer... je restaure le message originel de mémoire)

[gorgonite]

essayez mon denumsort, svp

même si je ne m'attends pas à être vraiment meilleur

[Jean-Marc.Bourguet]

essayez mon denumsort, svp

Je n'ai que 512M sur cette machine, pas les 128E (oui exa) nécessaires pour allouer ton tableau

[gorgonite]

Je n'ai que 512M sur cette machine, pas les 128E (oui exa) nécessaires pour allouer ton tableau

nan... c'est fait dynamiquement en fonction du max


bon, je sais; fallait pas supposer qu'on resterait "petit"

[davcha]

Que donne ce tri-ci sur ta machine, Jean-Marc ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef unsigned long long uint64;
#define N 1000000

void triR(uint64 src[N],uint64 dst[N],const int r){
	int count[256];
	int offset[256];
	int i;
	memset(count,0,256*sizeof(int));
	for(i = 0 ; i < N ; i++)
		count[(unsigned char)(src[i]>>(r*8))]++;
	offset[0] = 0;
	for(i = 1 ; i < 256 ; i++)
		offset[i] = offset[i-1] + count[i-1];
	for(i = 0 ; i < N ; i++){
		unsigned char c = (unsigned char)(src[i]>>(r*8));
		dst[offset[c]++] = src[i];
	}
}

void tri(uint64 src[N]){
	int r;
	uint64 *dst = (uint64 *)calloc(N,sizeof(uint64));
	for(r = 0 ; r < 4 ; r+=2){
		triR(src,dst,r);
		triR(dst,src,r+1);
	}
	free(dst);
}

[Jean-Marc.Bourguet]

Il y a un truc

Le truc, c'est de commencer par mesurer où on passe du temps. ce n'est pas dans le tri, c'est dans les IO qui prenaient 95% du temps de mon premier essai... donc je n'ai pas cherché beaucoup à optimiser le tri (j'ai utilisé std::sort qui était meilleur que tout ce que j'ai pu pondre moi-même jusqu'à présent) et j'ai travaillé les IO.

[Jean-Marc.Bourguet]

Que donne ce tri-ci sur ta machine, Jean-Marc ?

Tu peux me donner le programme complet? (Voir mon message précédant pourquoi)

[davcha]

Ca n'aurait pas grand intérêt, dans la mesure où je ne me suis intéressé qu'au tri, pas aux fonctions d'entrée/sortie.
Le programme ne lit, ni n'écrit dans aucun fichier, il se contente de créer un tableau d'entiers aléatoires et ensuite de le trier.

Je sais que je n'ai pas vraiment suivi les règles du concours, mais j'ai trouvé qu'il y avait peu d'intérêt à mesurer l'ensemble du programme plutôt que la fonction de tri en elle-même.

Sinon, je me serais contenté de std::sort, de la même manière, ce qui a peu d'intérêt ici, en définitive, je trouve.

edit: Voici les temps d'execution sur mon PC (athlon 3500+) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 0 : 0.118335 secondes
 1 : 0.126519 secondes
 2 : 0.122668 secondes
 3 : 0.123776 secondes
 4 : 0.122356 secondes
 5 : 0.156145 secondes
 6 : 0.123517 secondes
 7 : 0.121815 secondes
 8 : 0.123974 secondes
 9 : 0.123846 secondes
10 : 0.124706 secondes
11 : 0.127132 secondes
12 : 0.125489 secondes
13 : 0.124941 secondes
14 : 0.124597 secondes
15 : 0.125829 secondes
16 : 0.127000 secondes
17 : 0.126491 secondes
18 : 0.133492 secondes
19 : 0.140701 secondes

Et std::sort pour comparer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 0 : 0.184440 secondes
 1 : 0.202455 secondes
 2 : 0.185304 secondes
 3 : 0.184254 secondes
 4 : 0.181522 secondes
 5 : 0.181740 secondes
 6 : 0.179801 secondes
 7 : 0.180836 secondes
 8 : 0.178824 secondes
 9 : 0.186089 secondes
10 : 0.189696 secondes
11 : 0.189787 secondes
12 : 0.186746 secondes
13 : 0.188582 secondes
14 : 0.197642 secondes
15 : 0.208448 secondes
16 : 0.197789 secondes
17 : 0.182029 secondes
18 : 0.185098 secondes
19 : 0.187793 secondes