Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
5456 connectés 

 
 


 Mot :   Pseudo :  
 
 Page :   1  2  3  4
Page Suivante
Page Précédente
Bas de page 
Auteur Sujet :

[Concours No 3] A vos cerveaux !

n°774174
Evadream -​jbd-
Posté le 23-06-2004 à 12:44:58  profilanswer
 

Reprise du message précédent :

Harkonnen a écrit :

[:cupra]


 
[:ddr555]

mood
Publicité
Posté le 23-06-2004 à 12:44:58  profilanswer
 

n°774176
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 23-06-2004 à 12:48:49  profilanswer
 

si je le fais en assembleur, en RING 0, et avec une mesure de temps à base de RDTSC, je suis dans les clous du concours ou pas ? :whistle:

n°774178
the real m​oins moins
Posté le 23-06-2004 à 12:49:57  profilanswer
 

tant que tu n'essaies pas de poster tes résultats sur le forum avec ton soft ...


---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?
n°774180
printf
Baston !
Posté le 23-06-2004 à 12:51:01  profilanswer
 

Drapooooo.


---------------
Un matin je me lèverai et il fera beau.
n°774188
R3g
fonctionnaire certifié ITIL
Posté le 23-06-2004 à 13:06:09  profilanswer
 

Dites c'est sympa votre truc mais on juge quoi là ? parce que si le but c'est de faire du code rapide, ce serait peut-être une bonne idée de comparer les programmes avec le même compilo et sur la même machine, histoire que ça veuille dire quelquechose ?


---------------
Au royaume des sourds, les borgnes sont sourds.
n°774225
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 13:44:32  profilanswer
 

Harkonnen> T'es pas obligé d'être en Ring0 pour faire RDTSC.
R3g> Relis ce que j'ai posté au début du topic. Une fois que tout le monde aura posté ses codes, je pourrais faire les comparaisons.

n°774240
NeKoFuchik​oma
Posté le 23-06-2004 à 13:58:21  profilanswer
 

Salut  :hello:  
 
Compilé avec g++, j'arrive à descendre jusqu'a 460 en release sur mon portable (Centrino P4m 1.3Ghz donc un cache L2 de 1024Ko) et seulement 1562 avec Visual 7.1  :sweat: .
Mais bon j'ai déroulé un peu la boucle principale pour réduire le nombre de test du for :) et je vous passe le temps de compilation Enorme  :sleep:  
 
 
A+
:: NeKo ::
 

n°774274
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 14:14:24  profilanswer
 

J'ai encore un peu progressé...
 
Release : J'arrive en pointe à 234ms et 250ms de façon régulière.
Debug : J'arrive à 984ms.
 
Voici le code :

Code :
  1. // ConcoursHFR03.cpp : Defines the entry point for the console application.
  2. //
  4. #include <windows.h>
  5. #include <stdio.h>
  6. #include <conio.h>
  7. #include <stdlib.h>
  8. #include <malloc.h>
  10. #define MACRO_CHIFFRE_DIV10(x,y)   y = x/10; \
  11.                                    lReste = x - ((y<<3)+(y<<1)); \
  12.                                    lTableauResultatOccurences[lReste]++;
  14. #define MACRO_CHIFFRE_LUT10(x,y)    y = plDivideBy10[x]; \
  15.                                     (*plReste[x])++;
  17.                                  
  19. int main ( int argc, char * argv[] )
  20. {
  21.     long i, j, lValue, lTestLoop;
  22.     long lTableauResultatOccurences[10];
  23.     long lReste;
  24.     long lRenaming1, lRenaming2;
  25.     DWORD dwTC1, dwTC2;
  26.     long *plDivideBy10;
  27.     long **plReste;
  29.     //Boucle pour tester plusieurs fois l'algo
  30.     for (lTestLoop=0;lTestLoop<20;lTestLoop++)
  31.     {
  33.         //Uniquement sous Visual C++
  34.         dwTC1 = GetTickCount ( );
  37.         //Initialisation des deux LUT (80Ko en mémoire... Une partie est dans le cache L1, le reste dans le L2)
  38.         plDivideBy10    = (long  *)malloc ( (10000 * sizeof(long)) + (10000 * sizeof(long *)) );
  39.         plReste         = (long **)&(plDivideBy10[10000]);
  40.         for (i=0;i<10000;)
  41.         {
  42.             j = i/10;
  43.             for (lValue=0;lValue<10;lValue++,i++)
  44.             {
  45.                 plDivideBy10[i] = j;
  46.                 plReste[i] = &lTableauResultatOccurences[lValue];
  47.             }
  48.         }
  50.         memset ( lTableauResultatOccurences, 0, sizeof(lTableauResultatOccurences) );
  52.         for (i=0,lValue=0;i<5000000;i++)
  53.         {
  54.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  55.        
  56.             if (lValue>=1000000000)
  57.             {
  58.                 //Si le nombre est de 10 chiffres (53,5% des cas)
  59.                 MACRO_CHIFFRE_DIV10(lValue,lRenaming2);
  60.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  61.                 MACRO_CHIFFRE_DIV10(lRenaming1,lRenaming2);
  62.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  63.                 MACRO_CHIFFRE_DIV10(lRenaming1,lRenaming2);
  64.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  65.                 MACRO_CHIFFRE_LUT10(lRenaming1,lRenaming2);
  66.                 MACRO_CHIFFRE_LUT10(lRenaming2,lRenaming1);
  67.                 MACRO_CHIFFRE_LUT10(lRenaming1,lRenaming2);
  68.                 MACRO_CHIFFRE_LUT10(lRenaming2,lRenaming1);
  69.             }
  70.             else if (lValue>=100000000)
  71.             {
  72.                 //Si le nombre est de 9 chiffres (41,9% des cas)
  73.                 MACRO_CHIFFRE_DIV10(lValue,lRenaming2);
  74.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  75.                 MACRO_CHIFFRE_DIV10(lRenaming1,lRenaming2);
  76.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  77.                 MACRO_CHIFFRE_DIV10(lRenaming1,lRenaming2);
  78.                 MACRO_CHIFFRE_LUT10(lRenaming2,lRenaming1);
  79.                 MACRO_CHIFFRE_LUT10(lRenaming1,lRenaming2);
  80.                 MACRO_CHIFFRE_LUT10(lRenaming2,lRenaming1);
  81.                 MACRO_CHIFFRE_LUT10(lRenaming1,lRenaming2);
  82.             }
  83.             else
  84.             {
  85.                 //Si le nombre occupe jusqu'à 8 chiffres (4,6% des cas)
  86.                 MACRO_CHIFFRE_DIV10(lValue,lRenaming2);
  87.                 if (!lRenaming2) continue;
  88.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  89.                 if (!lRenaming1) continue;
  90.                 MACRO_CHIFFRE_DIV10(lRenaming1,lRenaming2);
  91.                 if (!lRenaming2) continue;
  92.                 MACRO_CHIFFRE_DIV10(lRenaming2,lRenaming1);
  93.                 if (!lRenaming1) continue;
  94.                 MACRO_CHIFFRE_LUT10(lRenaming1,lRenaming2);
  95.                 if (!lRenaming2) continue;
  96.                 MACRO_CHIFFRE_LUT10(lRenaming2,lRenaming1);
  97.                 if (!lRenaming1) continue;
  98.                 MACRO_CHIFFRE_LUT10(lRenaming1,lRenaming2);
  99.                 if (!lRenaming2) continue;
  100.                 MACRO_CHIFFRE_LUT10(lRenaming2,lRenaming1);
  101.             }
  102.         }
  104.         free ( plDivideBy10 );
  106.         //Uniquement sous Visual C++
  107.         dwTC2 = GetTickCount ( );
  108.         printf ( "Durée de traîtement : %d ms\n", dwTC2 - dwTC1 );
  110.     }
  112.     for (i=0;i<10;i++)
  113.     {
  114.         printf ( "%d - %d occurence", i, lTableauResultatOccurences[i] );
  115.         if (lTableauResultatOccurences[i]>1) printf ( "s" );
  116.         printf ( "\n" );
  117.     }
  118. return 0;
  119. }


Message édité par christophe_d13 le 23-06-2004 à 14:17:22
n°774289
NeKoFuchik​oma
Posté le 23-06-2004 à 14:22:14  profilanswer
 

Tres jolie  :jap:  
 
A+
:: NeKo ::

n°774291
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 14:23:49  profilanswer
 

Neko> Peux-tu l'essaye sur ta machine ?

mood
Publicité
Posté le 23-06-2004 à 14:23:49  profilanswer
 

n°774301
NeKoFuchik​oma
Posté le 23-06-2004 à 14:29:43  profilanswer
 

christophe> au plus bas je tombe à 361 avec ton code. Bravo :D  c'est plutot futé l'optimisation en fonction des stats de sortie.  :jap:  
 
A+
:: NeKo ::


Message édité par NeKoFuchikoma le 23-06-2004 à 14:30:30
n°774325
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 14:43:50  profilanswer
 

J'espère que d'autres feront mieux.
Ce que je peux dire, c'est que ceux qui ont la critique facile ne font produisent pas grand chose. Alors au lieu de causer, réfléchisser !


Message édité par christophe_d13 le 23-06-2004 à 14:57:51
n°774382
Flyounet_5​7
difficile à dire :/
Posté le 23-06-2004 à 15:20:01  profilanswer
 

avec ton code christophe_d13 j'ai 765ms au plus bas, avec un Athlon XP 1700+


Message édité par Flyounet_57 le 23-06-2004 à 15:20:38
n°774397
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 15:25:43  profilanswer
 

Flyounet_57> C'est un peu logique, ton bus est à 133MHz, et tu as une fréquence inférieure (le cache est normalement ok). En calculant grosso modo les perfs, tu dois être à 350ms. Bizarre...
Quel est ton compilateur ? Version ? OS ?
 
J'ai hésité à mettre mon code... J'aurais dû attendre plus longtemps que chacun ponde avec ses idées.

n°774438
darkoli
Le Petit Dinosaure Bleu
Posté le 23-06-2004 à 15:43:46  profilanswer
 

christophe_d13 a écrit :

Flyounet_57> C'est un peu logique, ton bus est à 133MHz, et tu as une fréquence inférieure (le cache est normalement ok). En calculant grosso modo les perfs, tu dois être à 350ms. Bizarre...
Quel est ton compilateur ? Version ? OS ?
 
J'ai hésité à mettre mon code... J'aurais dû attendre plus longtemps que chacun ponde avec ses idées.

Honnêtement je sèche, je n'ai pas d'idées (à par celle de lire le dernier chiffre et de faire ensuite un décalage).

n°774601
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 17:09:11  profilanswer
 

Pour ma part, j'ai mes petites idées...

n°774647
Flyounet_5​7
difficile à dire :/
Posté le 23-06-2004 à 17:43:48  profilanswer
 

christophe_d13 a écrit :

Flyounet_57> C'est un peu logique, ton bus est à 133MHz, et tu as une fréquence inférieure (le cache est normalement ok). En calculant grosso modo les perfs, tu dois être à 350ms. Bizarre...
Quel est ton compilateur ? Version ? OS ?


OS : Win Xp Famille
j'ai compilé via DevC++ 4.9.8.0 donc c'est Mingw  
et j'avais rien qui tournait en même temps
je retesterais direct apres un reboot tout à l'heure pour voir

n°774650
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 17:49:31  profilanswer
 

darkoli> Il y a un moyen de se passer de la division par 10 et de son reste. Le problème, c'est en C/C++ il faut forcément deux opérations, alors qu'en ASM, une seule suffit. Faut cogiter...

n°774840
blackgodde​ss
vive le troll !
Posté le 23-06-2004 à 20:32:35  profilanswer
 

puisqu'on a pas parlé du temps de compilation, voici une solution avec des teamplates. J'ai essayé pour 1000, le temps est à 0 ms avec ma 1ere solution comme avec celle-ci.
par contre deja pour 1000, le temps de compilation est tres long. je ne sais pas si c'est compilable pour les 5000000...
qu'en pensez-vous ?
 

Code :
  1. #include <iostream>
  2. #include <windows.h>
  3. using namespace std;
  5. #define tab_param int tab0, int tab1, int tab2, int tab3, int tab4, int tab5, int tab6, int tab7, int tab8, int tab9
  6. #define tab_val tab0, tab1,  tab2,  tab3,  tab4,  tab5,  tab6,  tab7,  tab8,  tab9
  7. #define tab_init 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  9. #pragma warning( disable : 4307 ) // dépassement de capacité au calcul des params template
  11. // mesure du temps
  12.   class time
  13.   {
  14.      DWORD ticks;
  15.     public:
  16.    
  17.      time()
  18.      {
  19.         ticks = GetTickCount();
  20.      }
  21.      
  22.  friend ostream & operator << (ostream & os, const time & t);
  23.   };
  24.  
  25.   ostream & operator << (ostream & os, const time & t)
  26.   {
  27.      os << GetTickCount() - t.ticks << " ms";
  28.      return os;
  29.   }
  31.   time *t;
  33. // remplissage du tableau
  34. template<tab_param, unsigned long value, unsigned long count, unsigned long val, int where>
  35. struct add_tab
  36. {
  37. static void go() {}
  38. };
  40. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  41. struct add_tab<tab_val, value, count, val, 0>
  42. {
  43. static void go()
  44. {
  45.  chiffres<tab0+1, tab1,  tab2,  tab3,  tab4,  tab5,  tab6,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  46. }
  47. };
  49. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  50. struct add_tab<tab_val, value, count, val, 1>
  51. {
  52. static void go()
  53. {
  54.  chiffres<tab0, tab1+1,  tab2,  tab3,  tab4,  tab5,  tab6,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  55. }
  56. };
  58. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  59. struct add_tab<tab_val, value, count, val, 2>
  60. {
  61. static void go()
  62. {
  63.  chiffres<tab0, tab1,  tab2+1,  tab3,  tab4,  tab5,  tab6,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  64. }
  65. };
  67. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  68. struct add_tab<tab_val, value, count, val, 3>
  69. {
  70. static void go()
  71. {
  72.  chiffres<tab0, tab1,  tab2,  tab3+1,  tab4,  tab5,  tab6,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  73. }
  74. };
  76. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  77. struct add_tab<tab_val, value, count, val, 4>
  78. {
  79. static void go()
  80. {
  81.  chiffres<tab0, tab1,  tab2,  tab3,  tab4+1,  tab5,  tab6,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  82. }
  83. };
  85. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  86. struct add_tab<tab_val, value, count, val, 5>
  87. {
  88. static void go()
  89. {
  90.  chiffres<tab0, tab1,  tab2,  tab3,  tab4,  tab5+1,  tab6,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  91. }
  92. };
  94. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  95. struct add_tab<tab_val, value, count, val, 6>
  96. {
  97. static void go()
  98. {
  99.  chiffres<tab0, tab1,  tab2,  tab3,  tab4,  tab5,  tab6+1,  tab7,  tab8,  tab9 , value, count, val / 10>::go();
  100. }
  101. };
  103. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  104. struct add_tab<tab_val, value, count, val, 7>
  105. {
  106. static void go()
  107. {
  108.  chiffres<tab0, tab1,  tab2,  tab3,  tab4,  tab5,  tab6,  tab7+1,  tab8,  tab9 , value, count, val / 10>::go();
  109. }
  110. };
  112. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  113. struct add_tab<tab_val, value, count, val, 8>
  114. {
  115. static void go()
  116. {
  117.  chiffres<tab0, tab1,  tab2,  tab3,  tab4,  tab5,  tab6,  tab7,  tab8+1,  tab9 , value, count, val / 10>::go();
  118. }
  119. };
  121. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  122. struct add_tab<tab_val, value, count, val, 9>
  123. {
  124. static void go()
  125. {
  126.  chiffres<tab0, tab1,  tab2,  tab3,  tab4,  tab5,  tab6,  tab7,  tab8,  tab9+1 , value, count, val / 10>::go();
  127. }
  128. };
  130. //décomposition en chiffres
  131. template<tab_param, unsigned long value, unsigned long count, unsigned long val>
  132. struct chiffres
  133. {
  134. static void go()
  135. {
  136.  //++tab[val % 10];
  137.  //chiffres<tab_val, value, val / 10>::go();
  138.  add_tab<tab_val, value, count, val, val%10>::go();
  139. }
  140. };
  142. template<tab_param, unsigned long value, unsigned long count>
  143. struct chiffres<tab_val, value, count, 0>
  144. {
  145. static void go()
  146. {
  147.  algo<tab_val, ( ( 1664525 * value ) + 1013904223 ) & 0x7FFFFFFF, count-1>::go();
  148. }
  149. };
  152. // algo de génération de lValue
  153. template<tab_param, unsigned long value, unsigned long count>
  154. struct algo
  155. {
  156. static void go()
  157. {
  158.  chiffres<tab_val, value, count, value>::go();
  159. }
  160. };
  162. template<tab_param, unsigned long value>
  163. struct algo<tab_val, value, 0>
  164. {
  165. static void go()
  166. {
  167.  cout << "temps écoulé : " << *t << '\n';
  169.  cout << "0 : " << tab0 << " occurences\n";
  170.  cout << "1 : " << tab1 << " occurences\n";
  171.  cout << "2 : " << tab2 << " occurences\n";
  172.  cout << "3 : " << tab3 << " occurences\n";
  173.  cout << "4 : " << tab4 << " occurences\n";
  174.  cout << "5 : " << tab5 << " occurences\n";
  175.  cout << "6 : " << tab6 << " occurences\n";
  176.  cout << "7 : " << tab7 << " occurences\n";
  177.  cout << "8 : " << tab8 << " occurences\n";
  178.  cout << "9 : " << tab9 << " occurences\n";
  179. }
  180. };
  182. int main()
  183. {
  184. t=new time();
  186. algo<tab_init, ( 1013904223 ) & 0x7FFFFFFF, 5000000>::go();
  188. delete t;
  189. cin.ignore();
  190. }


---------------
-( BlackGoddess )-
n°774913
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 21:40:56  profilanswer
 

J'ai mis au point mon nouvel ago en quelques minutes... (sans gros travail d'optimisation C).
Résultat très interressant en comparant avec l'ancien :
Ancien algo (basé sur la division 10/LUT10)
Debug : 1000ms
Release : 250ms
 
Nouvel algo (basé sur une autre approche)
Debug : 875ms (14% plus rapide)
Release : 343ms (37% plus lent)
 
Je regarde encore 2 ou 3 trucs dessus et j'arrête pour ce soir.


Message édité par christophe_d13 le 23-06-2004 à 21:43:28
n°774951
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 23-06-2004 à 22:31:52  profilanswer
 

putain, j'en chie pour arriver à faire un modulo rapide en asm sans utiliser de div [:ddr555]


---------------
J'ai un string dans l'array (Paris Hilton)
n°774986
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 23:00:40  profilanswer
 

Ben voilà un algo assez performant en debug et release et tout ça en C pur et dur...
 
Attention, c'est super tordu !
Par contre, il n'y a aucun modulo ni division dans la boucle principale.

Code :
  1. // ConcoursHFR03.cpp : Defines the entry point for the console application.
  2. //
  4. #include <windows.h>
  5. #include <stdio.h>
  6. #include <conio.h>
  7. #include <stdlib.h>
  8. #include <malloc.h>
  9. #include <math.h>
  11. #define MACRO_plCVBCalc()   plCVB0 = &(lConvertion8bits_vers_base10[0][ lValue     &255][0]); \
  12.                             plCVB1 = &(lConvertion8bits_vers_base10[0][(lValue>> 8)&255][1]); \
  13.                             plCVB2 = &(lConvertion8bits_vers_base10[0][(lValue>>16)&255][2]); \
  14.                             plCVB3 = &(lConvertion8bits_vers_base10[0][(lValue>>24)    ][3]);
  16. #define MACRO_lSumAdx()     lSum[0] = plCVB0[   0]+plCVB1[   0]+plCVB2[   0]+plCVB3[   0]; \
  17.                             lSum[1] = plCVB0[1024]+plCVB1[1024]+plCVB2[1024]+plCVB3[1024]; \
  18.                             lSum[2] = plCVB0[2048]+plCVB1[2048]+plCVB2[2048]+plCVB3[2048]; \
  19.                             lSum[3] = plCVB0[3072]+plCVB1[3072]+plCVB2[3072]+plCVB3[3072]; \
  20.                             lSum[4] = plCVB0[4096]+plCVB1[4096]+plCVB2[4096]+plCVB3[4096]; \
  21.                             lSum[5] = plCVB0[5120]+plCVB1[5120]+plCVB2[5120]+plCVB3[5120]; \
  22.                             lSum[6] = plCVB0[6144]+plCVB1[6144]+plCVB2[6144]+plCVB3[6144]; \
  23.                             lSum[7] = plCVB0[7168]+plCVB1[7168]+plCVB2[7168]+plCVB3[7168]; \
  24.                             lSum[8] = plCVB0[8192]+plCVB1[8192]+plCVB2[8192]+plCVB3[8192]; \
  25.                             lSum[9] = plCVB0[9216]+plCVB1[9216]+plCVB2[9216]+plCVB3[9216];
  27. #define MACRO_plSumCalc()   lSum[1] += lPostAddDixaine[ lSum[0] ]; \
  28.                             (*plPostAddUnite[  lSum[0] ])++; \
  29.                             lSum[2] += lPostAddDixaine[ lSum[1] ]; \
  30.                             plSum[1] = plPostAddUnite[  lSum[1] ]; \
  31.                             lSum[3] += lPostAddDixaine[ lSum[2] ]; \
  32.                             plSum[2] = plPostAddUnite[  lSum[2] ]; \
  33.                             lSum[4] += lPostAddDixaine[ lSum[3] ]; \
  34.                             plSum[3] = plPostAddUnite[  lSum[3] ]; \
  35.                             lSum[5] += lPostAddDixaine[ lSum[4] ]; \
  36.                             plSum[4] = plPostAddUnite[  lSum[4] ]; \
  37.                             lSum[6] += lPostAddDixaine[ lSum[5] ]; \
  38.                             plSum[5] = plPostAddUnite[  lSum[5] ]; \
  39.                             lSum[7] += lPostAddDixaine[ lSum[6] ]; \
  40.                             plSum[6] = plPostAddUnite[  lSum[6] ]; \
  41.                             lSum[8] += lPostAddDixaine[ lSum[7] ]; \
  42.                             plSum[7] = plPostAddUnite[  lSum[7] ]; \
  43.                             plSum[8] = plPostAddUnite[  lSum[8] ];
  44.                            
  46. #define MACRO_StatOccurences()  if (lValue>=100000000)                      \
  47.                                 {                                           \
  48.                                     (*plSum[1])++;                          \
  49.                                     (*plSum[2])++;                          \
  50.                                     (*plSum[3])++;                          \
  51.                                     (*plSum[4])++;                          \
  52.                                     (*plSum[5])++;                          \
  53.                                     (*plSum[6])++;                          \
  54.                                     (*plSum[7])++;                          \
  55.                                     (*plSum[8])++;                          \
  56.                                                                             \
  57.                                     if (lValue>=1000000000)                 \
  58.                                         (*plPostAddUnite[ lSum[9] + lPostAddDixaine[ lSum[8] ] ])++; \
  59.                                 }                                           \
  60.                                 else if (lValue<100000000)                  \
  61.                                 {                                           \
  62.                                     for (j=7,k=0;j>=1;j--)                  \
  63.                                     {                                       \
  64.                                         if (k) (*plSum[j])++;               \
  65.                                         else                                \
  66.                                         {                                   \
  67.                                             if (plSum[j]!=&(lTableauResultatOccurences[0]))\
  68.                                             {                               \
  69.                                                 (*plSum[j])++;              \
  70.                                                 k=1;                        \
  71.                                             }                               \
  72.                                         }                                   \
  73.                                     }                                       \
  74.                                 }
  78. int main ( int argc, char * argv[] )
  79. {
  80.     long i, j, k, lValue, lTestLoop;
  81.     long lTableauResultatOccurences[10];
  82.     DWORD dwTC1, dwTC2;
  83.     char szTmp[16];
  84.     long lSum[10];
  85.     long *plSum[10];
  86.     long lConvertion8bits_vers_base10[10][256][4]; //40960 octets
  87.     long *plCVB0, * plCVB1, * plCVB2, * plCVB3;
  88.     long *plPostAddUnite[64];
  89.     long lPostAddDixaine[64];
  91.     //Boucle pour tester plusieurs fois l'algo
  92.     for (lTestLoop=0;lTestLoop<20;lTestLoop++)
  93.     {
  95.         //Uniquement sous Visual C++
  96.         dwTC1 = GetTickCount ( );
  98.         //LUT de pre-convesion 32 bits => 10 digits
  99.         for (i=0;i<4;i++)
  100.         {
  101.             for (j=0;j<256;j++)
  102.             {
  103.                 lValue = j<<(i*8);
  104.                 sprintf ( szTmp, "%010u", lValue );
  105.                 for (k=0;k<10;k++)
  106.                     lConvertion8bits_vers_base10[k][j][i] = szTmp[9-k]-48;
  107.             }
  108.         }
  110.         //LUT de post-conversion 32 bits => 10 digits
  111.         for (i=0;i<46;i++)
  112.         {
  113.             plPostAddUnite[i] = &(lTableauResultatOccurences[i%10]);
  114.             lPostAddDixaine[i] = i/10;
  115.         }
  117.         memset ( lTableauResultatOccurences, 0, sizeof(lTableauResultatOccurences) );
  119.         for (i=0,lValue=0;i<1250000;i++)
  120.         {
  121.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  122.             MACRO_plCVBCalc();
  123.             MACRO_lSumAdx();
  124.             MACRO_plSumCalc();
  125.             MACRO_StatOccurences();
  126.            
  127.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  128.             MACRO_plCVBCalc();
  129.             MACRO_lSumAdx();
  130.             MACRO_plSumCalc();
  131.             MACRO_StatOccurences();
  133.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  134.             MACRO_plCVBCalc();
  135.             MACRO_lSumAdx();
  136.             MACRO_plSumCalc();
  137.             MACRO_StatOccurences();
  139.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  140.             MACRO_plCVBCalc();
  141.             MACRO_lSumAdx();
  142.             MACRO_plSumCalc();
  143.             MACRO_StatOccurences();
  144.         }
  146.         //Uniquement sous Visual C++
  147.         dwTC2 = GetTickCount ( );
  148.         printf ( "Durée de traîtement : %d ms\n", dwTC2 - dwTC1 );
  150.     }
  152.     for (i=0;i<10;i++)
  153.     {
  154.         printf ( "%d - %d occurence", i, lTableauResultatOccurences[i] );
  155.         if (lTableauResultatOccurences[i]>1) printf ( "s" );
  156.         printf ( "\n" );
  157.     }
  158. return 0;
  159. }


 
 
La vitesse maintenant :

Debug : 703ms
Release : 265ms


 
Ancien algo (basé sur la division 10/LUT10)  

Debug : 1000ms  
Release : 250ms


 
Le gain est important en Debug (+42%) mais plus lent en release (6%).


Message édité par christophe_d13 le 23-06-2004 à 23:03:29
n°774988
Joel F
Real men use unique_ptr
Posté le 23-06-2004 à 23:03:49  profilanswer
 

quel beau concours d'enculage de mouche :o

n°774992
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 23:07:06  profilanswer
 

Joel F> A toi de jouer...

n°775002
Joel F
Real men use unique_ptr
Posté le 23-06-2004 à 23:23:14  profilanswer
 

christophe_d13 a écrit :

Joel F> A toi de jouer...


 
j'ai autre chose à branler ... comparer des temps d'executions sur OS et machines hétéroclites n'apporte rien.
Sinon demain je lance ton bousin sur mon cluster de Mac et je tombe en dessous de 10 ms ...

n°775008
christophe​_d13
L'efficacité à tout prix.
Posté le 23-06-2004 à 23:33:45  profilanswer
 

L'intérêt est que chacun pose son code pour voir quel est le plus performant puisque qu'il suffit de le recompiler.
C'est tout l'intérêt d'un concours.
 
Cela prouve que l'on peut toujours faire mieux et que si les développeurs d'applis travaillaient un peu plus (si on leur donnaient plus de temps aussi), les programmes seraient plus performants et moins gourmands...
Tapez une lettre sous Word, c'est toujours 128Mo mininum sous WinXP... Et en plus, ça rame.
 
J'ai encore fait une variante de mon code :

Code :
  1. // ConcoursHFR03.cpp : Defines the entry point for the console application.
  2. //
  4. #include <windows.h>
  5. #include <stdio.h>
  6. #include <conio.h>
  7. #include <stdlib.h>
  8. #include <malloc.h>
  9. #include <math.h>
  11. #define MACRO_plCVBCalc()   plCVB0 = &(lConvertion8bits_vers_base10[0][ lValue     &255][0]); \
  12.                             plCVB1 = &(lConvertion8bits_vers_base10[0][(lValue>> 8)&255][1]); \
  13.                             plCVB2 = &(lConvertion8bits_vers_base10[0][(lValue>>16)&255][2]); \
  14.                             plCVB3 = &(lConvertion8bits_vers_base10[0][(lValue>>24)    ][3]);
  16. #define MACRO_lSumAdx()     lSum[0] = plCVB0[   0]+plCVB1[   0]+plCVB2[   0]+plCVB3[   0]; \
  17.                             lSum[1] = plCVB0[1024]+plCVB1[1024]+plCVB2[1024]+plCVB3[1024]; \
  18.                             lSum[2] = plCVB0[2048]+plCVB1[2048]+plCVB2[2048]+plCVB3[2048]; \
  19.                             lSum[3] = plCVB0[3072]+plCVB1[3072]+plCVB2[3072]+plCVB3[3072]; \
  20.                             lSum[4] = plCVB0[4096]+plCVB1[4096]+plCVB2[4096]+plCVB3[4096]; \
  21.                             lSum[5] = plCVB0[5120]+plCVB1[5120]+plCVB2[5120]+plCVB3[5120]; \
  22.                             lSum[6] = plCVB0[6144]+plCVB1[6144]+plCVB2[6144]+plCVB3[6144]; \
  23.                             lSum[7] = plCVB0[7168]+plCVB1[7168]+plCVB2[7168]+plCVB3[7168]; \
  24.                             lSum[8] = plCVB0[8192]+plCVB1[8192]+plCVB2[8192]+plCVB3[8192]; \
  25.                             lSum[9] = plCVB0[9216]+plCVB1[9216]+plCVB2[9216]+plCVB3[9216];
  26.                                
  27. #define MACRO_plSumCalc()   lSum[1] += lPostAddDixaine[ lSum[0] ]; \
  28.                             (*plPostAddUnite[  lSum[0] ])++; \
  29.                             lSum[2] += lPostAddDixaine[ lSum[1] ]; \
  30.                             (*plPostAddUnite[  lSum[1] ])++; \
  31.                             lSum[3] += lPostAddDixaine[ lSum[2] ]; \
  32.                             (*plPostAddUnite[  lSum[2] ])++; \
  33.                             lSum[4] += lPostAddDixaine[ lSum[3] ]; \
  34.                             (*plPostAddUnite[  lSum[3] ])++; \
  35.                             lSum[5] += lPostAddDixaine[ lSum[4] ]; \
  36.                             (*plPostAddUnite[  lSum[4] ])++; \
  37.                             lSum[6] += lPostAddDixaine[ lSum[5] ]; \
  38.                             (*plPostAddUnite[  lSum[5] ])++; \
  39.                             lSum[7] += lPostAddDixaine[ lSum[6] ]; \
  40.                             (*plPostAddUnite[  lSum[6] ])++; \
  41.                             lSum[8] += lPostAddDixaine[ lSum[7] ]; \
  42.                             (*plPostAddUnite[  lSum[7] ])++; \
  43.                             plSum[8] = plPostAddUnite[  lSum[8] ]; \
  44.                             (*plPostAddUnite[  lSum[8] ])++;
  46. #define MACRO_StatOccurences()  if (lValue>=1000000000)                                       \
  47.                                 {                                                             \
  48.                                     lTableauResultatOccurences[1]++;                          \
  49.                                     if (lValue>=2000000000)                                   \
  50.                                     {                                                         \
  51.                                         lTableauResultatOccurences[1]--;                      \
  52.                                         lTableauResultatOccurences[2]++;                      \
  53.                                     }                                                         \
  54.                                 }                                                             \
  55.                                 else if (lValue<100000000)                                    \
  56.                                 {                                                             \
  57.                                     for (j=8;j>=1;j--)                                        \
  58.                                     {                                                         \
  59.                                         if (lSum[j]) break;                                   \
  60.                                         else         lTableauResultatOccurences[0]--;         \
  61.                                     }                                                         \
  62.                                 }
  65. int main ( int argc, char * argv[] )
  66. {
  67.     long i, j, k, lValue, lTestLoop;
  68.     long lTableauResultatOccurences[10];
  69.     DWORD dwTC1, dwTC2;
  70.     char szTmp[16];
  71.     long lSum[10];
  72.     long *plSum[10];
  73.     long lConvertion8bits_vers_base10[10][256][4]; //40960 octets
  74.     long *plCVB0, * plCVB1, * plCVB2, * plCVB3;
  75.     long *plPostAddUnite[64];
  76.     long lPostAddDixaine[64];
  78.     //Boucle pour tester plusieurs fois l'algo
  79.     for (lTestLoop=0;lTestLoop<20;lTestLoop++)
  80.     {
  82.         //Uniquement sous Visual C++
  83.         dwTC1 = GetTickCount ( );
  85.         //LUT de pre-convesion 32 bits => 10 digits
  86.         for (i=0;i<4;i++)
  87.         {
  88.             for (j=0;j<256;j++)
  89.             {
  90.                 lValue = j<<(i*8);
  91.                 sprintf ( szTmp, "%010u", lValue );
  92.                 for (k=0;k<10;k++)
  93.                     lConvertion8bits_vers_base10[k][j][i] = szTmp[9-k]-48;
  94.             }
  95.         }
  97.         //LUT de post-conversion 32 bits => 10 digits
  98.         for (i=0;i<46;i++)
  99.         {
  100.             plPostAddUnite[i] = &(lTableauResultatOccurences[i%10]);
  101.             lPostAddDixaine[i] = i/10;
  102.         }
  104.         memset ( lTableauResultatOccurences, 0, sizeof(lTableauResultatOccurences) );
  105.         for (i=0,lValue=0;i<1250000;i++)
  106.         {
  107.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  108.             MACRO_plCVBCalc();
  109.             MACRO_lSumAdx();
  110.             MACRO_plSumCalc();
  111.             MACRO_StatOccurences();
  112.            
  113.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  114.             MACRO_plCVBCalc();
  115.             MACRO_lSumAdx();
  116.             MACRO_plSumCalc();
  117.             MACRO_StatOccurences();
  119.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  120.             MACRO_plCVBCalc();
  121.             MACRO_lSumAdx();
  122.             MACRO_plSumCalc();
  123.             MACRO_StatOccurences();
  125.             lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  126.             MACRO_plCVBCalc();
  127.             MACRO_lSumAdx();
  128.             MACRO_plSumCalc();
  129.             MACRO_StatOccurences();
  130.         }
  132.         //Uniquement sous Visual C++
  133.         dwTC2 = GetTickCount ( );
  134.         printf ( "Durée de traîtement : %d ms\n", dwTC2 - dwTC1 );
  136.     }
  138.     for (i=0;i<10;i++)
  139.     {
  140.         printf ( "%d - %d occurence", i, lTableauResultatOccurences[i] );
  141.         if (lTableauResultatOccurences[i]>1) printf ( "s" );
  142.         printf ( "\n" );
  143.     }
  144. return 0;
  145. }


Debug : 718ms
Release : 250ms


 
Up> Je vous laisse, assez plaisanté, je vais bosser... A demain.  :hello:


Message édité par christophe_d13 le 23-06-2004 à 23:56:52
n°775052
red factio​n
Posté le 23-06-2004 à 23:59:57  profilanswer
 

pour finir le code va tellement etre optimise que lensemble des define and co genera directement les resultats :D


Message édité par red faction le 24-06-2004 à 00:00:10
n°775062
the real m​oins moins
Posté le 24-06-2004 à 00:09:26  profilanswer
 

[:totoz]


---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?
n°775082
Tentacle
Posté le 24-06-2004 à 00:18:36  profilanswer
 

Sans grande prétention (surtout vu mes connaissances en C :/) :
 
en 66 lignes, sur un Athlon XP 2000+ soit 133*12 (je sais plus trop mais je suis actuellement à 1667Mhz) avec 768Mo de mémoire :
 

Debug : 656 à 672 ms
Release : 344 ms


 
J'arrive en fait à ne faire que max 2 modulos par nombre pseudo-aléatoire.
 
Edit: des pointes à 329ms
Re-Edit: j'ai Visual Studio 6.0


Message édité par Tentacle le 24-06-2004 à 00:23:36
n°775213
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 24-06-2004 à 09:14:31  profilanswer
 

1er essai, largement perfectible, non optimisé, bref une grosse merde...
 

Code :
  1. .586
  2. .model flat,stdcall
  3. option casemap:none
  5. include  kernel32.inc
  6. include  masm32.inc
  7. includelib kernel32.lib
  8. includelib masm32.lib
  10. .data
  11. tab DWORD 10 dup(0)
  12. ticks DWORD 0
  13. buffer DB  12
  15. .code
  16. start:
  18. mov eax,4C4B40h
  19. xor ebx,ebx
  20. push eax
  21. invoke GetTickCount
  22. mov ticks,eax
  23. pop eax
  25. theboucle:
  26. mov edx,ebx
  27. imul edx,edx,19660Dh
  28. add edx,3C6EF35Fh
  29. and edx,7FFFFFFFh
  30. mov ebx,edx
  31. push eax
  32. mov eax,ebx
  33. mov ecx,0Ah
  35. thewhile:
  36. xor edx,edx
  37. div ecx
  38. inc dword ptr tab[edx*4]
  39. cmp eax,0
  40. jg thewhile
  42. pop eax
  43. dec eax
  44. jge theboucle
  46. invoke GetTickCount
  47. sub eax,ticks
  48. mov     ticks,eax
  50. invoke dw2hex,ticks,ADDR buffer
  51. invoke StdOut,ADDR buffer
  53. ret
  55. end start


Temps (en hexa) : 455, soit 1109 ms, exactement le même temps que le 1er essai de BlackGoddess, sur Athlon XP 2500+, 512 Mo de RAM.
J'ai pas encore codé l'affichage du nombre d'occurences, mais j'ai vérifié la mémoire, c'est la même chose que les autres, mais bon, je m'en occupe :D
Dans la boucle thewhile, le gros goulet est constitué par l'instruction div, et l'instruction inc (qui écrit en mémoire), si j'arrive à les éviter, je pense faire un carton.
J'ai mon idée pour optimiser ce bordel, la suite au prochain épisode :D


---------------
J'ai un string dans l'array (Paris Hilton)
n°775263
Joel F
Real men use unique_ptr
Posté le 24-06-2004 à 09:41:41  profilanswer
 

red faction a écrit :

pour finir le code va tellement etre optimise que lensemble des define and co genera directement les resultats :D


 
meta programmation template [:aloy]

n°775281
SoWhatIn22
Posté le 24-06-2004 à 09:52:26  profilanswer
 

Joel F a écrit :

meta programmation template [:aloy]


dans le cas de ce programme, c'est vrai qu'on peut tout connaitre à la compilation puisque la suite de nombre à analyser est toujours la même. Par contre, si la graine de départ pour la génération des nombres n'était pas connue à la compilation, alors la meta programmation template ne pourra pas être d'un grand secours.

n°775307
blackgodde​ss
vive le troll !
Posté le 24-06-2004 à 10:10:13  profilanswer
 

Joel F a écrit :

meta programmation template [:aloy]


 
bin ... c ce que j'ai essayé de faire ... qq1 pourrait me dire si c'est juste ? (cf ci dessus)


---------------
-( BlackGoddess )-
n°775338
Ummon
Posté le 24-06-2004 à 10:21:57  profilanswer
 

L'histoire de mettre un peu de gaité parmi tous ces code assembleurs :
(PII400)

#!/usr/bin/ruby
 
t = Array::new(10)
10.times{|i| t[i] = 0 }
 
n = 0
5000000.times{
   n = ((1664525 * n) + 1013904223) & 0x7FFFFFFF
   n.to_s.each_byte{|m| t[m-48] += 1 }
}
 
p t


$time main.rb > out
 
real    14m14.053s
user    10m17.569s
sys     0m47.765s


$cat out
[4454792, 6919549, 4821073, 4474832, 4473815, 4457929, 4454968, 4451157, 4450771, 4455972]


 :whistle:


Message édité par Ummon le 24-06-2004 à 10:27:09
n°775341
christophe​_d13
L'efficacité à tout prix.
Posté le 24-06-2004 à 10:22:20  profilanswer
 

On pourrait tout à fait proposer à l'utilisateur de saisir la graine de départ ?
 
Qu'en pensez-vous ?
 
Je le rajoute au problème ?

n°775377
Tentacle
Posté le 24-06-2004 à 10:34:33  profilanswer
 


Debug : 422ms
Release: 203 à 219 ms


 
plus qu'un modulo par nombre.

n°775738
darkoli
Le Petit Dinosaure Bleu
Posté le 24-06-2004 à 13:56:59  profilanswer
 

Je me suis dit qu'en diminuant le nombre de divisions et de modulos ça devrait aller plus vite et bien non !
 
Méthode basique : 47 414 858 % et 47 414 858 / => 1940ms.
Méthode Optimisée : 5 488 889 % et 5 488 889 / => 2710ms. :sweat:
 
La méthode optimisée consiste simplement à faire une table précalculée pour les nombres entre 0 et 99999 dans laquelle je stocke le nombre de chiffres ainsi que les chiffres présents dans le nombre. Exemple pour le nombre "9457" la ligne #9457 contient [4,9,4,5,7,?].
 
Ensuite pour chaque nombre je fais un modulo 100000 (qui est peut être plus long qu'un modulo 10 :??:) et avec le résultat je mets à jour les decomptes avec une boucle qui parcourt les valeurs de la ligne correspondante et incrémente le decompte de 1 à chaque fois.

p=m%100000;
for (j=1;j<=table[p][0];j++) decompte[table[p][j]]++;


Message édité par darkoli le 24-06-2004 à 13:59:33
n°775767
Tentacle
Posté le 24-06-2004 à 14:05:13  profilanswer
 

J'utilise aussi un modulo 100000 ce qui me permet de ne faire qu'un modulo par nombre :
 

Code :
  1. #include <stdio.h>
  2. #include <windows.h>
  4. #define TABLE_LENGTH 100000
  6. int main(int argc, char* argv[])
  7. {
  8. DWORD dwTimeBefore = GetTickCount ();
  10. unsigned int count[10] = {0}; // Statistiques finales
  11. unsigned short tmpCount[TABLE_LENGTH] = {0}; // Statistiques intermédiaires
  12. int i, incr;
  13. int error; // Correction du nombre de 0
  14. unsigned long lValue, lTmpValue;
  15. unsigned long j, tmpJ;
  17. error = 0;
  18. for (i = 0, lValue = 0; i < 5000000; i++) {
  19.  lValue = (( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
  20.  lTmpValue = lValue;
  22.  while (lTmpValue > 0) {
  23.   if (lTmpValue >= TABLE_LENGTH) {
  24.    incr = lTmpValue % TABLE_LENGTH;
  25.    lTmpValue /= TABLE_LENGTH;
  27.    // Incrémentation de 'error' en fonction du nb de 0 à gauche (sur 5 chiffres)
  28.    if (incr < 10000) {
  29.     error++;
  30.     if (incr < 1000) {
  31.      error ++;
  32.      if (incr < 100) {
  33.       error ++;
  34.       if (incr < 10) {
  35.        error ++;
  36.        if (incr == 0) {
  37.         error ++;
  38.        }
  39.       }
  40.      }
  41.     }
  42.    }
  43.   } else {
  44.    incr = lTmpValue;
  45.    lTmpValue = 0;
  46.   }
  48.   tmpCount[incr]++;
  49.  }
  50. }
  52. // Calcul statistiques finales
  53. for (j = 0; j < TABLE_LENGTH; j++) {
  54.  incr = tmpCount[j];
  55.  tmpJ = j;
  56.  while (tmpJ > 0) {
  57.   count[tmpJ%10] += incr;
  58.   tmpJ /= 10;
  59.  }
  60. }
  61. count[0] += error; // Correction du nombre de 0
  63. printf ("%d ms\n", GetTickCount() - dwTimeBefore);
  65. // Affichage statistiques
  66. for (i = 0; i < 10; i++) {
  67.  printf ("%d - %d occurences\n", i, count[i]);
  68. }
  70. return 0;
  71. }


 
Je fais des statistiques temporaires et à la fin j'analyse chaque nombre de 0 à 99999 pour sortir les statistiques finales.
 
Le fait que le tableau de stats temporaires contiennent des unsigned short au lieu de unsigned int a aussi accélerer la chose (c'est une histoire de cache ?)
 
J'atteins ainsi 203ms en pointe sur mon Athlon XP2000+

n°775981
NeKoFuchik​oma
Posté le 24-06-2004 à 14:47:58  profilanswer
 

Bien joué tentacle avec ton code j'obtiens 240ms !
par contre ton while de calcul ne sert pas à grand chose (2 passe maxi)  
donc en le remplacant par :

Code :
  1. if (lTmpValue >= TABLE_LENGTH) {
  2.               incr = lTmpValue % TABLE_LENGTH;
  3.               lTmpValue /= TABLE_LENGTH;
  4.              
  5.               // Incrémentation de 'error' en fonction du nb de 0 à gauche (sur 5 chiffres)  
  6.               if (incr < 10000) {
  7.                  error++;
  8.                  if (incr < 1000) {
  9.                     error ++;
  10.                     if (incr < 100) {
  11.                        error ++;
  12.                        if (incr < 10) {
  13.                           error ++;
  14.                           if (incr == 0) {
  15.                              error ++;
  16.                           }
  17.                        }
  18.                     }
  19.                  }
  20.               }
  21.              } else {
  22.               incr = lTmpValue;
  23.               lTmpValue = 0;
  24.            }
  25.            
  26.            tmpCount[incr]++;
  27.          
  28.            if (lTmpValue >= TABLE_LENGTH) {
  29.               incr = lTmpValue % TABLE_LENGTH;
  30.               //lTmpValue /= TABLE_LENGTH;  
  31.              
  32.               // Incrémentation de 'error' en fonction du nb de 0 à gauche (sur 5 chiffres)  
  33.               if (incr < 10000) {
  34.                  error++;
  35.                  if (incr < 1000) {
  36.                     error ++;
  37.                     if (incr < 100) {
  38.                        error ++;
  39.                        if (incr < 10) {
  40.                           error ++;
  41.                           if (incr == 0) {
  42.                              error ++;
  43.                           }
  44.                        }
  45.                     }
  46.                  }
  47.               }
  48.              } else {
  49.               incr = lTmpValue; 
  50.            }
  51.            
  52.            tmpCount[incr]++;


 
je tombe à 200ms  :D  
 
A+
:: NeKo ::


Message édité par NeKoFuchikoma le 24-06-2004 à 14:54:41
n°776053
Tentacle
Posté le 24-06-2004 à 14:58:48  profilanswer
 

oui je sais qu'il ne sert à rien, mais j'ai pas pensé qu'en l'enlevant on pouvait gagner autant. En fait je l'avais laissé car je testais plusieurs valeurs de TABLE_LENGTH (même si le reste du code ne s'adapte pas trop ... c'est du bidouillage de toute façon).
En fait quand tmpCount était encore un tableau de unsigned int, TABLE_LENGTH = 10000 donnait le meilleur resultat ce qui nécéssitait 2 modulos. Ca m'étonnait d'aileurs que perdre du temps avec 100000 (avec 1 modulo donc) alors je me suis dit que c'était peut-être la taille du tableau d'où le unsigned short.
 
Tu pourrais d'ailleurs aussi enlevé le test (lTmpValue >= TABLE_LENGTH) pour la 2eme passe vu qu'il ne sera (à priori) jamais vérifié.
Tu as d'ailleurs oublié un test vu qu'on ne doit pas faire la 2eme passe si lTmpValue == 0;
 
De mon côté j'arrive à 187 à 203ms
 
Edit: merci de la remarque :jap:


Message édité par Tentacle le 24-06-2004 à 14:59:08
n°776111
Ummon
Posté le 24-06-2004 à 15:12:01  profilanswer
 

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)

mood
Publicité
Posté le   profilanswer
 

 Page :   1  2  3  4
Page Suivante
Page Précédente
Haut de page 

Aller à :
Ajouter une réponse
 

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 !

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.324 secondes

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)