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 !

christophe_d13

L'efficacité à tout prix.

Je propose un nouveau petit concours du code le plus rapide. Plus simple que le précédent pour que tout le monde puisse y participer.
Ce topic est posté dans les zones : C, C++ et ASM.
D'ailleurs, pendant que j'y pense, ce serait bien d'avoir une sous-catégorie Concours !
Y a-t-il un modo dans la salle ?

ça m'aurait permis d'éviter de flooder en zone C et ASM. Désolé.

On dispose d'un générateur de nombre aléatoire générant une suite de 5.000.000 valeurs entières (positives) allant de 0 à 2^31-1 suivant :

Code :

for (i=0,lValue=0;i<5000000;i++)
{
lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
//La valeur aléatoire est dans lValue
//...
}

Il s'agit de comptabiliser l'occurence des chiffres composants les nombres. Attention, on ne comptera pas le zéro précédent la valeur !

Un exemple pour 3 nombres : 484230, 6232, 89054620

Durée de traîtement : 32ms
0 - 3 occurences
1 - 0 occurence
2 - 4 occurences
3 - 2 occurences
4 - 3 occurences
5 - 1 occurence
6 - 2 occurences
7 - 0 occurence
8 - 2 occurences
9 - 1 occurence

Limitation dans le programme
- Tout est possible, la mesure de temps doit se faire entre le début du main et juste avant l'affichage des résultats.
Pour les résultats, un tableau de 10 entiers (de longueur 4 ou 8 octets) doit être rempli.

Limitation en mémoire
- Mémoire occupée limitée à 64Mo.

Limitation pour le langage
1 - Uniquement en C ou C++ sans aucune optimisation de la part du compilateur.
2 - Uniquement en C ou C++ avec les optimisations maximales du compilateur.
3 - Pour ceux qui veulent faire de l'assembleur (avec ou sans C/C++ mélangé), il faudra également fournir un code en C ou C++ (voir 1 ou 2). Donc sortir au moins 2 programmes (ASM et C/C++).

La cible
- Pour ma part, j'ai a ma disposition deux AthlonXP (Un Thoroughbred à 180MHz*12 avec 512Mo et un Barton à 180MHz*12 avec 1Go) sous Windows XP et un Pentium III-600 (133MHz*4 avec 128Mo).
- Il est possible de tester sur d'autres configurations.
- J'ai a ma disposition Visual C++ Service Pack 6 + Processor Pack 2 et DJGPP 2.01 (uniquement sous Windows 98SE).

Les performances
- Je ferais un récap pour les 3 cibles pour ceux qui sortirons en C/C++ sans optimisation et avec.
- Pour les programmes en assembleur, j'essayerais de les faire tourner sur les 3 plate-formes.

A vos cerveaux !

Message édité par christophe_d13 le 23-06-2004 à 09:53:48

Publicité

black_lord

Truth speaks from peacefulness

[:abnocte invictus]

---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me

skeye

t'as oublié un 0!

---------------
Can't buy what I want because it's free -

christophe_d13

L'efficacité à tout prix.

skeye> Bien vue ! T'as été plus rapide que moi pour la relecture.

Taz

bisounours-codeur

« Uniquement en C ou C++ sans aucune optimisation de la part du compilateur. » c'est complètement bidon ton truc ... si tu désactives l'inlining, c'est même pas là peine de faire quoi que ce soit, sans parler des noop que rajoute les compilos dans tous les sens en mode debug

christophe_d13

L'efficacité à tout prix.

Taz> On a tous des compilateurs différents. Cela montrera les performance de l'analyse et pas forcément du code.
Pour l'optimisation, il reste l'assembleur !

antp

Super Administrateur
Champion des excuses bidons

christophe_d13 a écrit :

D'ailleurs, pendant que j'y pense, ce serait bien d'avoir une sous-catégorie Concours !
Y a-t-il un modo dans la salle ?

non, pas assez de topic à ce sujet

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

docmaboul

christophe_d13 a écrit :

Taz> On a tous des compilateurs différents. Cela montrera les performance de l'analyse et pas forcément du code.
Pour l'optimisation, il reste l'assembleur !

Cela n'a aucun sens de parler d'assembleur tout en désactivant les optimisations du compilo pour le C ou le C++.

Taz

bisounours-codeur

christophe_d13 a écrit :

Taz> On a tous des compilateurs différents. Cela montrera les performance de l'analyse et pas forcément du code.
Pour l'optimisation, il reste l'assembleur !

ça montrera rien du tout. c'est bidon ton truc

jagstang

Pa Capona ಠ_ಠ

[:drapo] quand même

---------------
What if I were smiling and running into your arms? Would you see then what I see now?

Publicité

christophe_d13

L'efficacité à tout prix.

C'est ouvert à tout le monde... Et je n'oblige personne a participer. Si cela ne t'interresse pas, libre à toi de faire ton choix.
Mais tu peux toujours nous sortir un code avec les optimisations si cela peut te faire plaisir.

Rien que pour vous faire plaisir, j'élargi la cible.

blackgoddess

vive le troll !

Pour les résultats, un tableau de 8 entiers doit être rempli.

8 entiers ? pas 10 ?

---------------
-( BlackGoddess )-

Taz

bisounours-codeur

ce que tu comprends pas c'est que ton histoire bidon de désactiver les optimisations est pire : certains compilateurs ne considère pas certaine choses comme des optimisations, donc si tu laisses pas sa chance à chaque compilateur de faire son mieux, tu accrois encore plus les différences. à jamais

christophe_d13

L'efficacité à tout prix.

BlackGoddess> Bien lu ! Corrigé, merci. Je m'étais trompé, Désolé.

christophe_d13

L'efficacité à tout prix.

Taz> Sors-nous un programme et on verra la différence entre o0 et o3 sous DJGPP et entre Od et O2 sous Visual C++.

el muchacho

Comfortably Numb

Bizarre, j'ai l'impression d'avoir déjà vu ça qq part...

http://forum.hardware.fr/forum2.ph [...] =0&subcat=
:pfff:
edit : j'avais pas vu qu'on ne compte que les chiffres. L'algo est trivial, donc ça n'a aucun intérêt.

Message édité par el muchacho le 23-06-2004 à 10:27:44

black_lord

Truth speaks from peacefulness

christophe_d13 a écrit :

Taz> Sors-nous un programme et on verra la différence entre o0 et o3 sous DJGPP et entre Od et O2 sous Visual C++.

taz utilise GCC [:aloy]

---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me

kadreg

profil: Utilisateur

black_lord a écrit :

taz utilise GCC [:aloy]

d'ailleurs, à cause de taz, gcc de faire du C++

---------------
brisez les rêves des gens, il en restera toujours quelque chose... -- laissez moi troller sur discu !

skeye

kadreg a écrit :

d'ailleurs, à cause de taz, gcc de faire du C++

[:xp1700]

---------------
Can't buy what I want because it's free -

christophe_d13

L'efficacité à tout prix.

el muchaco> Il ne marche pas le lien...
Mais si c'est à quoi je pense, j'ai repris l'idée du générateur de Knutz et j'ai fais un problème plus simple. Peut-être trop simple puisque dans le problème, ce qui va causer la lenteur ne sera pas forcément l'analyse, mais la bande passante... Cela dit, l'algo doit quand même être bien fait.

Sous VC++ 6.0 SP5 avec un Barton à 180x12 et WinAmp en tâche de fond : (4 essais et j'ai pris le temps le plus court)
- Debug = 7047ms (/Od)
- Release = 5781ms (/O2)

Up> Le code est très simple, mais sans aucune analyse.

Message édité par christophe_d13 le 23-06-2004 à 10:19:09

black_lord

Truth speaks from peacefulness

kadreg a écrit :

d'ailleurs, à cause de taz, gcc de faire du C++

:lol: le niveau vient de grimper d'un coup là !

---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me

blackgoddess

vive le troll !

(jme suis juste permis de mettre une windowserie pour mesurer le temps.)

compilé sous vc++7.1, p4 2.4 :

Code :

#include <windows.h>
#include <iostream>
using namespace std;
class time
{
DWORD ticks;
public:
time()
{
ticks = GetTickCount();
}
friend ostream & operator << (ostream & os, const time & t);
};
ostream & operator << (ostream & os, const time & t)
{
os << GetTickCount() - t.ticks << " ms";
return os;
}
int main()
{
time t;
int i;
unsigned long lValue;
unsigned long val;
int tab[10] = {0};
for (i=0,lValue=0;i<5000000;i++)
{
lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
val = lValue;
while(val > 0)
{
++tab[val % 10];
val /= 10;
}
}
cout << "temps écoulé : " << t << '\n';
for(int i=0; i<10; ++i)
{
cout << i << " : " << tab[i] << " occurences\n";
}
cin.ignore();
}

résultats :

debug :

temps ÚcoulÚ : 3421 ms
0 : 4454792 occurences
1 : 6919549 occurences
2 : 4821073 occurences
3 : 4474832 occurences
4 : 4473815 occurences
5 : 4457929 occurences
6 : 4454968 occurences
7 : 4451157 occurences
8 : 4450771 occurences
9 : 4455972 occurences

release :

temps ÚcoulÚ : 1109 ms
0 : 4454792 occurences
1 : 6919549 occurences
2 : 4821073 occurences
3 : 4474832 occurences
4 : 4473815 occurences
5 : 4457929 occurences
6 : 4454968 occurences
7 : 4451157 occurences
8 : 4450771 occurences
9 : 4455972 occurences

---------------
-( BlackGoddess )-

christophe_d13

L'efficacité à tout prix.

C'est bien partie...
Je repasserai plus tard. Je crois que tout le monde a compris; BlackGoddess en a fait la preuve.

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

el muchacho

Comfortably Numb

christophe_d13 a écrit :

Tu ne trouves pas que la ressemblance est frappante ?
http://forum.hardware.fr/forum2.ph [...] =0&subcat=

(lien corrigé)

Message édité par el muchacho le 23-06-2004 à 10:27:12

the real moins moins

et comment tu fais pour valider que les resultats sont corrects si tes 5000000 valeurs de départ sont aléatoires? ^^

---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?

christophe_d13

L'efficacité à tout prix.

el muchacho> Le problème est quand même différent puisque l'on ne compte pas l'occurence des nombres, mais des chiffres.
J'en avais un autre dans l'idée, mais je voulais faire simple et proche de ce qui avait déjà été fait. Au prochain, je poserais mon idée. Simple mais avec un très fort potentiel d'analyse.

the real moins moins> La valeur de départ est de 0 (lValue=0 dans le for).

Message édité par christophe_d13 le 23-06-2004 à 10:48:25

Taiche

(╯°□°）╯︵ ┻━┻

J'pige pas en quoi la valeur va être aléatoire, perso :??:
Elle est 0 au début. OK. Tout ce que tu fais ensuite c'est des opérations dessus, donc tu finiras avec des constantes fixes et pas aléatoires, non ?
(ce que je veux dire c'est : pourquoi pas faire un bête rand() ?)

---------------
Everyone thinks of changing the world, but no one thinks of changing himself | It is the peculiar quality of a fool to perceive the faults of others and to forget his own | Early clumsiness is not a verdict, it’s an essential ingredient.

christophe_d13

L'efficacité à tout prix.

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...

the real moins moins

ouais enfin en bref ton input est pas aléatoire du tout

---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?

Taiche

(╯°□°）╯︵ ┻━┻

Bon alors comme chu con et que j'voulais absolument de l'aléatoire, voici mes résultats :

Citation :

e:\>java -cp E:\dev\ConcoursALaCon -Xnoclassgc ConcoursALaCon
1454 ms
Debug :
chiffres [0] = 59353
chiffres [1] = 48133
chiffres [2] = 78841
chiffres [3] = 49116
chiffres [4] = 69692
chiffres [5] = 49218
chiffres [6] = 30814
chiffres [7] = 90477
chiffres [8] = 29730
chiffres [9] = 59458

Utilisation de la JVM IBM 1.3.0 sur Windows 2000, avec un P4 2.4 GHz (y a plein de progs qui tournent en tâche de fond, j'vais pas vous faire la liste mais entre autres y a un clien DB2 et un serveur WebSphere).
Vala [:itm]

Message édité par Taiche le 23-06-2004 à 11:08:49

darkoli

Le Petit Dinosaure Bleu

Os : Linux Debian testing
Processeur : Intel(R) Pentium(R) 4 CPU 1.70GHz
Compilateur : gcc 3.3.4

Compilation sans paramètre (taille 12650 octets) :

Duree du traitement : 4300ms (~5s).
0 - 4454792 occurences.
1 - 6919549 occurences.
2 - 4821073 occurences.
3 - 4474832 occurences.
4 - 4473815 occurences.
5 - 4457929 occurences.
6 - 4454968 occurences.
7 - 4451157 occurences.
8 - 4450771 occurences.
9 - 4455972 occurences.

Compilation avec le paramètre "-O3" (taille 12482 octets) :

Duree du traitement : 1980ms (~2s).
0 - 4454792 occurences.
1 - 6919549 occurences.
2 - 4821073 occurences.
3 - 4474832 occurences.
4 - 4473815 occurences.
5 - 4457929 occurences.
6 - 4454968 occurences.
7 - 4451157 occurences.
8 - 4450771 occurences.
9 - 4455972 occurences.

christophe_d13

L'efficacité à tout prix.

the real moins moins> C'est le générateur congruentiel de Knutz. Tu trouveras via google plein d'infos sur l'aléatoire. Mais ce n'est pas le sujet ici.
Taiche> Peux-tu ajouter le code du générateur, sinon je ne pourrais pas le prendre en compte. Egalement, c'est 5 millions de répétitions.

black_lord

Truth speaks from peacefulness

christophe_d13 a écrit :

comment il parle à [:greg2]

---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me

darkoli

Le Petit Dinosaure Bleu

Taiche a écrit :

Bon alors comme chu con et que j'voulais absolument de l'aléatoire, voici mes résultats :

Citation :

Oui mais tu ne l'as pas faut sur une série de 5 000 000 valeurs variant entre 0 et (2^31)-1 ?

the real moins moins

on ne teste que la compilation :??:

---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?

Taiche

(╯°□°）╯︵ ┻━┻

the real moins moins a écrit :

on ne teste que la compilation :??:

Ba côté algo, j'vois pas trop c'qu'il y a de si marquant... non ?

Taiche

(╯°□°）╯︵ ┻━┻

Or donc, après un copier/coller d'un code foireux, voici la version "faussement aléatoire" :

Code :

public class ConcoursALaCon
{
public static void main(String[] args)
{
long start = System.currentTimeMillis();
long lValue = 0;
int[] chiffres = new int[10];
for (int i = 0;i < 5000000; i++)
{
//lValue = new Random().nextLong();
lValue = ( ( 1664525 * lValue ) + 1013904223 ) & 0x7FFFFFFF;
long gron = lValue;
while(gron > 0)
{
++chiffres[(int)(gron % 10)];
gron = gron / 10;
}
}
long end = System.currentTimeMillis();
System.out.println(end - start + " ms" );
System.out.println("Debug :" );
for(int i = 0;i < 10; i++)
System.out.println("chiffres [" + i + "] = " + chiffres[i]);
}
}

Compilation avec jikes 1.21 et l'option -target 1.3.

Résultats :

Citation :

e:\>java -cp E:\dev\ConcoursALaCon -Xnoclassgc ConcoursALaCon
1891 ms
Debug :
chiffres [0] = 4454792
chiffres [1] = 6919549
chiffres [2] = 4821073
chiffres [3] = 4474832
chiffres [4] = 4473815
chiffres [5] = 4457929
chiffres [6] = 4454968
chiffres [7] = 4451157
chiffres [8] = 4450771
chiffres [9] = 4455972

Désolé pour le faux résultat précédent qui était dû à un code foireux :jap:

christophe_d13

L'efficacité à tout prix.

Différence entre mon premier algo et le dernier :
Le source est en C pur sans aucune ligne en assembleur.

Algo de test (nul mais juste)
- Debug : 7047ms
- Release : 5781ms

Initial
- Debug : 1578ms
- Release : 343ms

Dernier (23/06/04 à 12h38)
- Debug : 1094ms
- Release : 281ms

Cible : AthlonXP Barton 12*180/1Go/nForce2 et WindowsXP avec WinAmp en tâche de fond.

Message édité par christophe_d13 le 23-06-2004 à 13:04:19

Harkonnen

Modérateur
Un modo pour les bannir tous

[:cupra]

Evadream -jbd-

Harkonnen a écrit :

[:cupra]

[:ddr555]

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.154 secondes