C++

[Concours No 3] A vos cerveaux !

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 3 4 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [Concours No 3] A vos cerveaux !

Ummon

Reprise du message précédent :
Et voila, encore une fois : il vaut mieux un code de haut niveau bien pensé plutot que du bidouillage de bas niveau (assembleur). (je vais me faire taper mais c pas grave)

Publicité

NeKoFuchikoma

Je pose le code de tentacle après avoir intégré ses remarques et enlevé des petits trucs en trop (pas de zéro ni de 100000 dans la liste), mon nouveau score tombe à 180ms autant en faire profiter :

Code :

#include <stdio.h>
#include <windows.h>
#define TABLE_LENGTH 100000
int main(int argc, char* argv[])
{
SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
int i, incr;
for (unsigned short p = 0; p < 10; p++) {
DWORD dwTimeBefore = GetTickCount (); // Bon je commence pas au début m'en voudrez pas :p
unsigned int count[10] = {0}; // Statistiques finales
unsigned short tmpCount[TABLE_LENGTH] = {0}; // Statistiques intermédiaires
int error; // Correction du nombre de 0
unsigned long lValue, lTmpValue;
unsigned long j, tmpJ;
error = 0;
for (i = 0, lValue = 0; i < 5000000; i++) {
lValue = (( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
lTmpValue = lValue;
/////////////////////////////////////////////////////////////////////////////////////////
if (lTmpValue >= TABLE_LENGTH) {
incr = lTmpValue % TABLE_LENGTH;
lTmpValue /= TABLE_LENGTH;
// Incrémentation de 'error' en fonction du nb de 0 à gauche (sur 5 chiffres)
if (incr < 10000) {
error++;
if (incr < 1000) {
error ++;
if (incr < 100) {
error ++;
if (incr < 10) {
error ++;
if (incr == 0) {
error ++;
}
}
}
}
}
} else {
incr = lTmpValue;
lTmpValue = 0;
}
tmpCount[incr]++;
incr = lTmpValue;
tmpCount[incr]++;
/////////////////////////////////////////////////////////////////////////////////
//}
}
// Calcul statistiques finales
for (j = 0; j < TABLE_LENGTH; j++) {
incr = tmpCount[j];
tmpJ = j;
while (tmpJ > 0) {
count[tmpJ%10] += incr;
tmpJ /= 10;
}
}
count[0] += error; // Correction du nombre de 0
printf ("\ntest %d : %d ms\n", p, GetTickCount() - dwTimeBefore);
// Affichage statistiques
for (i = 0; i < 10; i++) {
printf ("%d - %d occurences\n", i, count[i]);
}
}
return 0;
}

:lol:

A+
:: NeKo ::

Message édité par NeKoFuchikoma le 24-06-2004 à 16:00:18

christophe_d13

L'efficacité à tout prix.

De mon côté, entre deux lignes de codes à mon boulot, j'ai encore cogité. Il existe un moyen de se passer de la division et du modulo sans pour autant manipuler autant de pointeur comme je l'avais fait...
Dés que j'aurais plus de temps je m'en occupe.

Ceci dit, en assembleur il est possible qu'avec la manipulation de pointeurs, on soit plus rapide.

Les temps progresses et tant mieux !
En plus, vous trichez un peu avec Windows en passant en TC. Mais c'est autorisé puisque pas spécifié dans le problème.

Tentacle

Neko on peut encore fait ceci mais ça n'apporte pas grand chose :

Code :

for (i = 0, lValue = 0; i < 5000000; i++) {
lValue = (( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
lTmpValue = lValue;
if (lTmpValue >= TABLE_LENGTH) {
incr = lTmpValue % TABLE_LENGTH;
lTmpValue /= TABLE_LENGTH;
// Incrémentation de 'error' en fonction du nb de 0 à gauche (sur 5 chiffres)
if (incr < 10000) {
error++;
if (incr < 1000) {
error ++;
if (incr < 100) {
error ++;
if (incr < 10) {
error ++;
if (incr == 0) {
error ++;
}
}
}
}
}
tmpCount[incr]++;
}
tmpCount[lTmpValue]++;
}

Je pense aussi qu'en assembleur il doit y avoir moyen d'aller plus vite, l'algo ne suffit pas.

christophe_d13: que veux-tu dire par TC ? le GetTickCount ? il vaudrait mieux utiliser quoi ?

Message édité par Tentacle le 24-06-2004 à 16:23:58

NeKoFuchikoma

ah oui bien vu tentacle ! :lol:

Pour l'assembleur j'ai un collegue (qui se prend pour un compilo) qui s'amuse en ce moment à adapter la technique de tentacle en asm mais pour l'instant, son prog met 250ms pour faire le calcul...

edit: le code asm tombe à 240ms ça descend ça descend
edit2: je viens de comprendre TC = Time Critical
désolé christophe j'avais pas envie de fermer toutes mes applis :jap:

A+
:: NeKo ::

Message édité par NeKoFuchikoma le 24-06-2004 à 16:40:38

antp

Super Administrateur
Champion des excuses bidons

christophe_d13 a écrit :

En plus, vous trichez un peu avec Windows en passant en TC. Mais c'est autorisé puisque pas spécifié dans le problème.

vu que c'est testé sur des machines différentes on n'est plus à ça près, non ?

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

Tentacle

et puis de toute facon j'obtiens le même résultat sans cela ...

Mais sinon on va pas demander à christophe_d13 de tester chez lui chaque algo

NeKoFuchikoma

allez moi je vais me cacher :sweat:

voici le code de mon collegue :

Code :

#include <stdio.h>
#include <windows.h>
#define TABLE_LENGTH 100000
unsigned long res[10] = {
4454792 ,
6919549 ,
4821073 ,
4474832 ,
4473815 ,
4457929 ,
4454968 ,
4451157 ,
4450771 ,
4455972 };
int main(int argc, char* argv[])
{
Sleep(500);
SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
for(unsigned short p = 0; p < 10; p++)
{
DWORD dwTimeBefore = GetTickCount ();
unsigned int count[10] = {0}; // Statistiques finales
unsigned short tmpCount[TABLE_LENGTH] = {0}; // Statistiques intermédiaires
int i, incr;
unsigned long lValue;
unsigned long j, tmpJ;
unsigned short* ptab = &tmpCount[0];
// for (i = 0, lValue = 0; i < 5000000; i++) {
// lValue = (( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
// /!\ asm visual studio
__asm {
mov edi, ptab
xor ecx, ecx
xor esi, esi
push ebp
mov ebp, 5000000
label_for:
mov edx, 1664525
mov eax, esi
mul edx
add eax, 1013904223
and eax, 7fffffffh
mov esi, eax
mov ebx, TABLE_LENGTH
cmp eax, ebx
jb label_else
xor edx, edx
div ebx
cmp edx, 10000
jae lbl1
inc ecx
cmp edx, 1000
jae lbl1
inc ecx
cmp edx, 100
jae lbl1
inc ecx
cmp edx, 10
jae lbl1
inc ecx
and edx, edx
jnz lbl1
inc ecx
lbl1:
inc word ptr [edi + 2 * edx]
inc word ptr [edi + 2 * eax]
dec ebp
jnz label_for
jmp label_the_end
label_else:
mov edx, eax
inc word ptr [edi]
inc word ptr [edi + 2 * edx]
dec ebp
jnz label_for
jmp label_the_end
inc word ptr [edi + 2 * edx]
inc word ptr [edi + 2 * eax]
dec ebp
jnz label_for
label_the_end:
pop ebp
add count[0], ecx
}
// }
// Calcul statistiques finales
for (j = 0; j < TABLE_LENGTH; j++) {
incr = tmpCount[j];
tmpJ = j;
while (tmpJ > 0) {
count[tmpJ%10] += incr;
tmpJ /= 10;
}
}
printf ("%d ms\n", GetTickCount() - dwTimeBefore);
// Affichage statistiques
for (i = 0; i < 10; i++) {
printf ("%d - %d occurences [%s]\n", i, count[i], (res[i]==count[i])?("true " ):("false" ));
}
}
return 0;
}

résultat sur ma machine 170ms :heink:

à vous de tester les différents algo chez vous si vous souhaitez comparer

A+
:: NeKo ::

Tentacle

Christophe a raison, on peut se séparer du modulo ... et d'ailleurs on est bête de pas y avoir pensé :

Code :

for (i = 0, lValue = 0; i < 5000000; i++) {
lValue = (( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
lTmpValue = lValue;
if (lTmpValue >= TABLE_LENGTH) {
lTmpValue /= TABLE_LENGTH;
incr = lValue - lTmpValue * TABLE_LENGTH;
// Incrémentation de 'error' en fonction du nb de 0 à gauche (sur 5 chiffres)
if (incr < 10000) {
error++;
if (incr < 1000) {
error ++;
if (incr < 100) {
error ++;
if (incr < 10) {
error ++;
if (incr == 0) {
error ++;
}
}
}
}
}
tmpCount[incr]++;
}
tmpCount[lTmpValue]++;
}

=> 125ms en pointe

en fait ça sert à rien de faire une division et un modulo vu que ce dernier est obtenable à partir de la division : a mod b = a - E(a / b) * b

Neko: tu pourrais le mettre en assembleur ?

NeKoFuchikoma

Terrible, mais jusqu'ou ça va descendre :bounce:

Le reste est donnée lorsque l'on fait une division assembleur du coup on n'utilise pas d'instruction supplémentaire...

Pour infos sans le modulo, je tombe à 130ms et mon pote viens de se jetter par la fenêtre :lol:

A+
:: NeKo ::

Publicité

red faction

Vu les temps dexecutions qui deviennent de + en + cours, il ne vaudrait pas mieux utiliser qqch de plus precis comme QueryPerformanceCounter ???

NeKoFuchikoma

Bon demain on remplace quelques éléments dans le code asm, ce soir je deviens :pt1cable:

A+
:: NeKo :: :hello:

Message édité par NeKoFuchikoma le 24-06-2004 à 17:58:56

christophe_d13

L'efficacité à tout prix.

Si vous voulez, je vous donne un code d'une ligne pour faire une division, mais sans division... ça vous dit ?
Un indice : Juste en faisant une multiplication et un décalage...

red faction> On pourrait également boucler 10 ou 20 fois sur le traîtement et obtenir une moyenne.

Tentacle

Red Faction: soit, mais vu qu'on a tous des ordis différents on peut difficilement comparer. Sur 100 essais, j'obtiens 122.893169 ms.

Christophe_d13: attends je vais essayer de trouver

Evadream -jbd-

christophe_d13 > attends un peu, ca m'excite les neurones

Tentacle

c'est bon j'ai trouvé, j'avais déjà cherché sur cette voie hier soir mais je ne voyais pas comment en sortir le modulo, mais pour extraire le résultat de la division c'est impéccable !! J'essais de suite.

christophe_d13

L'efficacité à tout prix.

Dans quelques jours, je prendrai chaque source et je ferai un test complet.

Message édité par christophe_d13 le 24-06-2004 à 18:31:30

christophe_d13

L'efficacité à tout prix.

Je vois également des trucs rigolos dans les algos :
J'ai précisé dans le problème que la valeur aléatoire va de 0 à 2^31-1. Donc vérifiez bien que le zéro marche !

Code :

for (i=0;i<5000000;i++)
{
lValue = i;
//Votre code
//....
}

Tentacle

la valeur 0 doit-elle ajouter 1 point pour le nombre de 0 alors ?

Edit: la méthode alternative pour la division me donne un temps supérieur pour le moment ... c'est peut la mauvaise méthode

Message édité par Tentacle le 24-06-2004 à 18:59:44

christophe_d13

L'efficacité à tout prix.

Et bien, c'est logique, puisque l'on ne compte que les zéros réellement présent. Et le zéro ne dispose que d'un seul chiffre.

Ton code passe à 78ms avec la suppression de la division.

christophe_d13

L'efficacité à tout prix.

Le seul hic du code c'est le fait que les stats se fassent dans des valeurs de 16 bits. Si la valeur aléatoire est toujours la même, il y a dépassement. ça marche pour la graine 0 et l'algo de Knutz, mais je ne l'ai posé que pour que chacun est la même suite aléatoire :

Cela permet à tous d'avoir la même série de nombres et une bonne rapidité de fabrication du nombre aléatoire.
Le travail d'analyse peut également inclure la fabrication même de ce nombre aléatoire...

Cela dit, les résultats seront pris en compte.

Tentacle

Bon déjà, j'ai pas du trouver la bonne méthode pour la division où je l'ai mal exploitée
Pour le zéro, à la limite ça fait une addition supplémentaire tout à la fin.

Pour les stats en 16bits, je sais que ça risque le dépassement mais dans notre cas ça marche, c'est pour ça que je l'ai laissé. En fait si je passe en 32bits, j'ai des temps désastreux apparement dû parce que le tableau devient trop gros (le traitement est apparement différent ... histoire du cache ?).

Est-ce important ?

NeKoFuchikoma

Citation :

Si vous voulez, je vous donne un code d'une ligne pour faire une division, mais sans division... ça vous dit ?

Merci bien christophe mais on va la retrouver :sweat: c'était un truc avec une multiplication d'un nombre négatif magique et un décalage d'apres ce que j'ai pu sortir de g++

Bon j'espere que demain le score ne se sera pas trop envolé :lol:

A+
:: NeKo ::

Evadream -jbd-

J'ai rien trouvé qui me donne qqchose de mieux (en reprenant ton code Tentacle) en essayant de remplacer la division par multiplication + decalage, je dois mal m'y prendre Je ne suis pas contre une solution [:ddr555]

Tentacle

de mon côté je fais, par exemple pour une division par 10, (int)(n * 1.6) >> 4
(1.6 = 16/10 = 2^4/10)
Ca marche mais l'opération sur des réels est trop lente

Evadream -jbd-

Moi je multipliais par 104858 et divisait par 2^20 avec un décalage, mais comment dire, je sens que c'est pas çà.

darkoli

Le Petit Dinosaure Bleu

Tentacle a écrit :

de mon côté je fais, par exemple pour une division par 10, (int)(n * 1.6) >> 4
(1.6 = 16/10 = 2^4/10)
Ca marche mais l'opération sur des réels est trop lente

Et il y a aussi la converion entier=>réel=>entier qui doit être longue.

Joel F

Real men use unique_ptr

pourquoi vous ne travaillais pas en entier tt du long ?

red faction

ce serait bien qd on aura pratiquement fini loptimisation du prog de faire une compte rendu avec les diffrentes instruction et leur temps dexecution (ou du moins les classer suivant cette valeur)

Ummon

Avouez que je vous aie tous bluffé avec mon temps d'exécution de 10min :sol:

christophe_d13

L'efficacité à tout prix.

Je vous donne la solution pour une division par 100000.
Vous prenez la valeur sur 32 bits et vous la multipliez par un autre 32 bits : 351843721. Le nombre résultant est un 64 bits. Vous faites un décalage à droite de 45 bits si vous traîtez le bloc de 64 bits ou simplement de 13 bits avec le bloc supérieur de 32 bits.

Code :

ulValueH = (unsigned long)(((__int64)lValue * (__int64)351843721)>>45);

On fait l'erreur de calcul (il y en a une) est reportée dans les bits inférieur...
351843721/2^45 = 1,0000000003174136509187519550323e-5
L'erreur est extrèment faible...

En ASM, cela nous donne...

Code :

mov eax, 351843721
imul lValue //edx:eax = eax * lValue
shr edx, 13 //On garde uniquement edx, ainsi on ne décale que de 13 et pas de 45.
mov ulValueH, edx //Le résultat se trouve dans edx...

Dommage que peut de gens s'interresse à ce genre de technique...

Et pourquoi on multiplie par cette valeur ? et pourquoi on décale de 45 ? Cherchez un peu !

Message édité par christophe_d13 le 24-06-2004 à 23:24:08

darkoli

Le Petit Dinosaure Bleu

Tiens j'ai essayé de faire la même chose avec la division par 10 mais il y avait une perte trop importante, pour diviser N par 10 je faisais N = (N>>16)+(N>>32)+(N>>128) ce qui correspondait à N / ~9.84615384615. Mais je n'avais pas eu l'idée de le faire pour la découpe des nombres (/ et % 100000)!

Par contre le gain est à peine de 10% sur ma machine : ~240ms.
=> Athlon XP 2100+, DevCPP, XP.
Je teste demain matin sur mon P4 1.7Ghz (boulot).

darkoli

Le Petit Dinosaure Bleu

Bon voilà j'ai viré la division et j'obtiens une durée d'envrion ~160ms (Algo de base ~1830ms).

Le nombre de division est passé de 47414858 à 488889 soit ~97x moins et idem pour le modulo ! Mais le temps de traitement a été divisé seulement par 10 !

Code :

void cas_opti4(void)
{
/* Chronometrage */
time_t tdebut=0;
time_t tfin=0;
clock_t cdebut=0;
clock_t cfin=0;
/* Traitement */
int i=0;
int v=0;
int v1=0;
int v_old=0;
short int table[100000];
int decompte[10];
int nb_zeros=0;
/* Statistiques */
int nb_divisions=0;
int nb_modulos=0;
/* Initialisation */
memset(table, 0, sizeof table);
memset(decompte, 0, sizeof decompte);
/* Debut */
tdebut=time(NULL);
cdebut=clock();
/* Traitement */
for (i=0;i<5000000;i++)
{
v = ((1664525 * v_old) + 1013904223) & 0x7FFFFFFF;
/* fprintf(stdout, "v = %d.\n", v);*/
v_old=v;
if (v > 100000)
{
asm("movl $351843721, %eax" );
asm("imull %0"::"r"(v)); /* edx:eax = eax * v */
asm("shr $13, %edx" ); /* On garde uniquement edx, ainsi on ne décale que de 13 et pas de 45. */
asm("movl %%edx, %0":"=r"(v)::"%eax" );
v1=v_old-(v*100000);
table[v1]++;
if (v1 < 10000)
{
nb_zeros++;
if (v1 < 1000)
{
nb_zeros++;
if (v1 < 100)
{
nb_zeros++;
if (v1 < 10)
{
nb_zeros++;
if (v1 == 0) nb_zeros++;
}
}
}
}
}
/* fprintf(stdout, "v1 = %d, v2 = %d.\n", v, v1);*/
table[v]++;
}
decompte[0]=nb_zeros;
for (i=1;i<100000;i++)
{
v1=table[i];
if (v1 < 1) continue;
v=i;
/* fprintf(stdout, "%d = x%d.\n", i, v1);*/
while (v > 0)
{
decompte[v%10]+=v1;
/* nb_modulos++;*/
v=v/10;
/* nb_divisions++;*/
}
}
/* Fin */
tfin=time(NULL);
cfin=clock();
/* Bilan */
fprintf(stdout, "Duree : %.fms (~%ds).\n", ((double)(cfin-cdebut)/(double)CLOCKS_PER_SEC)*1000, tfin-tdebut);
/*
for (i=0;i<10;i++) fprintf(stdout, "%d = x%d.\n", i, decompte[i]);
fprintf(stdout, "Nombre de divisions = %d.\n", nb_divisions);
fprintf(stdout, "Nombre de modulos = %d.\n", nb_modulos);
*/
/* Fin */
return;
}

Le type des entier pour le tableau table est très important et cela permet de diviser par 4 le temps de traitement (de ~800ms à ~200ms) ! :ouch:

Processeur : P4 1.7Ghz
Os : Linux Debian testing.
Compilateur : gcc 3.3.4.

Message édité par darkoli le 25-06-2004 à 09:54:07

NeKoFuchikoma

Pour infos :
A ma grande surprise, il semblerai que Visual Studio 7.1 ai optimisé les divisions comme un grand car je tourne à présent entre 115 et 109ms sur mon P4m 1.3Ghz ...
Avec g++ je suis en pointe à 130ms.

edit qui ne sert pas à grand chose: 100ms à 110ms en repassant en TC :lol:

A+
:: NeKo ::

Message édité par NeKoFuchikoma le 25-06-2004 à 10:01:29

Yttrium

Furtif

Il faudrait encore jeter un oeil du côté des SSE. Je n'en suis pas sûr, mais il me semble qu'il y a quelques instructions qui permettent plusieurs opérations sur entiers par cycle.

Et ces 'if' imbriqués... Ne sont-ils pas des candidats pour CMOV ?

Et il reste encore éventuellement l'Hyper-Threading.

Non ?

Yttrium

Furtif

Military technology.
Not for office or personal use.
Made in HFR.

christophe_d13

L'efficacité à tout prix.

Les if imbriqués peuvent laisser place à des cmp/setxx/add

Yttrium

Furtif

Y a-t-il une liste de nombre de cycle par opération pour les instruction asm (sur p4) ?

christophe_d13

L'efficacité à tout prix.

Va voir les docs Intel ou AMD.
Il n'y a pas que les opérations par cycle, il y aussi la latence. Car les opérations sont pipelinées.

christophe_d13

L'efficacité à tout prix.

C'est une mauvaise idée de mettre le code en ASM directement.
Il vaut mieux laisser le compilateur réarranger le code lui-même ou tout faire en ASM.

Code :

ulValueH = (unsigned long)(((__int64)lValue * (__int64)351843721)>>45);

PS: Ce concours au final ne sert pas à grand chose (pour ce problème), il serait peut-être plus interressant dans l'avenir de proposer des problèmes plus utiles (des problèmes que l'on rencontre souvent par exemple).
On pourrait également faire 1 ou 2 concours par mois ?

Tentacle

darkoli a écrit :

Le type des entier pour le tableau table est très important et cela permet de diviser par 4 le temps de traitement (de ~800ms à ~200ms) ! :ouch:

C'est ce que j'avais remarqué aussi. Si on passe en int, les meilleurs performances étaient obtenus en divisant par 10000 ce qui faisait un calcul supplémentaire. En 100000, malgré l'opération en moins, le temps d'exécution était trop augmenté, d'où le fait de passer en short int.

Publicité

Page : 1 2 3 4

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

C++

[Concours No 3] A vos cerveaux !

Sujets relatifs
Le concours de programmation ICFP 2004 a commencé	[Concours] Recherche de doublons dans une séquence
[java/algo] Concours - implémenter une itf simple de gestion d'agenda.	[IA] petite idée de concours
concours de code	[C++] Concours de code : new test en cours, proposez votre solution !
Concours programmation	[PHP] Comment organiser un concours
organiser un concours .	[Concours] Votre Requête MySQL la plus complexe
Plus de sujets relatifs à : [Concours No 3] A vos cerveaux !

Page générée en 0.144 secondes