[Défi] Le Défi Delphi n°5 : Le Sudoku solver

Version imprimable

Voir 40 message(s) de cette discussion en une page

22/07/2009, 09h00
FullSpeed

Gentil TROLL

Pour que tu passes une bonne fin de semaine
je vais te donner un chrono reel

Je travaille avec Escargot donc tous mes chronos la concerne:
Mais je t'interdis de te jeter dans le fleuve rouge...
Suivant vos bons conseil j'utilise
QueryPerformanceCounter(endTime64);

Est ce que tu sais que si le temps est sous le millième de seconde le compteur passe en notation scientifique?
Il est a priori pas possible de descendre sous 0,0004 secondes soit 4 milliemes de seconde le chrono passe en notation scientifique
J'allais oublié: sans ASM ni Multitraitement: Pascal pur

Et oui 50 ans avant de m'appeler FULLSPEED

Mais rassures toi toujours en admiration devant tes arbres (pas les bonzaïs)

Ensuite pour ta notation scientifique, je ne sais pas de quoi tu parle ... moi il a une précision de 0.3µs au mieux !
Ce qui n'est pas loin des 200ns théorique !

Code:

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
const
  MAX_COUNTER = 1000000;
var
   TickPerSec: Int64;
  I: Integer;
  Sum: Int64;
  Counters: array of Int64;
  Delta: array of Int64;
begin
  SetLength(Counters, MAX_COUNTER);
  SetLength(Delta, MAX_COUNTER);
 
  QueryPerformanceFrequency(TickPerSec);
  for I := 0 to MAX_COUNTER - 1 do
    QueryPerformanceCounter(Counters[I]);
 
  for I := 0 to MAX_COUNTER - 2 do
    Delta[I] := Counters[I + 1] - Counters[I];
 
  Sum := 0;
  for I := 0 to MAX_COUNTER - 2 do
    Inc(Sum, Delta[I]);
 
  ShowMessage(FloatToStr(Sum / MAX_COUNTER ));
  ShowMessage(FloatToStr(Sum / MAX_COUNTER / TickPerSec * 1000000) + ' µs');
end;

J'adore les arbres, surtout quand ils sont fruitiers :mouarf:

Citation:

Envoyé par ShaiLeTroll

Ensuite pour ta notation scientifique, je ne sais pas de quoi tu parle ... moi il a une précision de 0.3µs au mieux !
Ce qui n'est pas loin des 200ns théorique !

Code:

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
const
  MAX_COUNTER = 1000000;
var
   TickPerSec: Int64;
  I: Integer;
  Sum: Int64;
  Counters: array of Int64;
  Delta: array of Int64;
begin
  SetLength(Counters, MAX_COUNTER);
  SetLength(Delta, MAX_COUNTER);
 
  QueryPerformanceFrequency(TickPerSec);
  for I := 0 to MAX_COUNTER - 1 do
    QueryPerformanceCounter(Counters[I]);
 
  for I := 0 to MAX_COUNTER - 2 do
    Delta[I] := Counters[I + 1] - Counters[I];
 
  Sum := 0;
  for I := 0 to MAX_COUNTER - 2 do
    Inc(Sum, Delta[I]);
 
  ShowMessage(FloatToStr(Sum / MAX_COUNTER ));
  ShowMessage(FloatToStr(Sum / MAX_COUNTER / TickPerSec * 1000000) + ' µs');
end;

Je préfère le faire comme ça :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
var
  debut, fin, freq : int64;
  i : integer;
begin
  QueryPerformanceCounter(Debut);
  for i := 0 to 1000 do
  begin
  end;
 
  QueryPerformanceCounter(Fin);
  QueryPerformanceFrequency(freq);
 
  ShowMessage(Format('%0.4f ms', [(Fin-debut)*1000 / freq]));
end;

22/07/2009, 13h52
Franck SORIANO

Citation:

Envoyé par ShaiLeTroll

Vous essayez tous de faire du Multi-Thread, moi avec mon P4, ça serait juste une catastrophe, car le calcul ce n'est que des opérations logiques ou mathématiques, il n'y a pas d'accès à des ressources lentes comme DD, Périphériques, ... du coup, windows, il va pas change vos threads de core sans arrêt, ... j'ai connu ça avec EasyPHP 1.8 et des Octo-Core, il passait plus de temps à lutter contre Windows pour le positionnement des threads qu'à exécuter la requête qui allait plus vite sur un mono-core, un comble non ?

Toute la difficulté pour multi-threader la résolution, c'est de trouver un algo qui s'y prête bien et qui sache s'adapter en fonction du nombre de CPU de la machine hôte.
Ma solution actuelle, fonctionnerait très bien sur un mono-CPU. La résolution est trop rapide pour que windows fasse une préemption. Donc sans multi-coeur, le premier thread prendrait la main et la garderait jusqu'à la fin. La résolution serait terminée avant même que le deuxième thread n'est été activé une seule fois !

J'ai en tête un autre algo qui se multi-threadrait très bien, tout en tirant réellement parti de tous les CPU disponnibles sur la machine. Ces perfs devraient même être assez constantes d'une grille à l'autre.
Mais je suis un peu fleimard pour essayer de l'implémenter. Et j'ai peur qu'il n'ait un temps minimal de résolution beaucoup plus important que ma solution actuelle !

Citation:
Envoyé par Franck SORIANO
Je préfère le faire comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 var debut, fin, freq : int64; i : integer; begin QueryPerformanceCounter(Debut); for i := 0 to 1000 do begin end; QueryPerformanceCounter(Fin); QueryPerformanceFrequency(freq); ShowMessage(Format('%0.4f ms', [(Fin-debut)*1000 / freq])); end;
Cela teste quoi ? le temps pour une boucle for de 0 à 1000, cela n'a rien à voir avec le code que j'ai soumis qui mesure la précision minimale de QueryPerformanceCounter, je répondais à FullSpeed sur son histoire de 0.4 ms de précision et l'histoire de notation scientifique ... alors que le calcul est au moins sur 15 digit significative alors que l'on a besoin d'une précision de µs qui nécessite que 7 à 10 digit !

j'ai encaspulé QueryPerformance dans des fonctions perso ...
Code:

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 29 30 31 32 33 34 35 36 37 38 procedure GetBeginTime(var Value: Int64); begin QueryPerformanceCounter(Value); end; function GetElapsedTimeMilliSec(var BeginTime: Int64): Cardinal; var EndTime, TickPerSec: Int64; begin QueryPerformanceCounter(EndTime); QueryPerformanceFrequency(TickPerSec); Result := Round((EndTime - BeginTime) / TickPerSec * 1000); // 1000 ms = 1s end; function GetElapsedTimeMicroSec(var BeginTime: Int64): Cardinal; // Plus d'une Heure ! var EndTime, TickPerSec: Int64; begin QueryPerformanceCounter(EndTime); QueryPerformanceFrequency(TickPerSec); Result := Round((EndTime - BeginTime) / TickPerSec * 1000000); // 1000000 µs = 1000 ms = 1s end; ... var debut: int64; i : integer; begin GetBeginTime(Debut); for i := 0 to 1000 do begin end; ShowMessage(Format('%d ms', GetElapsedTimeMilliSec(Debut)])); end;
Effectivement, on arrive vite à un effet perverse avec le Multi-thread dont la mise à en place coûte à la base un peu de temps ... ma solution est largement assez lente mais absoluement pas threadable :mouarf:

22/07/2009, 19h29
FullSpeed

Precision?

Citation:

Envoyé par Franck SORIANO

Toute la difficulté pour multi-threader la résolution, c'est de trouver un algo qui s'y prête bien et qui sache s'adapter en fonction du nombre de CPU de la machine hôte.
!

Je comprenbds de cela que on peut choisir et déterminer sur quel coeur un traitement doit etre executer; C'est bien cela?
Pour moi c'est du ressort de l'OS ou du pros. Meme pour une tread on ne peut pas etre sur que les coeurs sont utilmisé?

Question pour les forts en theme:

Si on a trouve un calcul qui donne comme resultat la liste des révélés d'une grille a-t-on en réalité une méthode pour les placer?

mon calcul me donne 30 valeurs et dans celles ci iol y a les X reveles.

Boris
22/07/2009, 19h32
Franck SORIANO

Citation:

Envoyé par ShaiLeTroll

Cela teste quoi ? le temps pour une boucle for de 0 à 1000,

Je montrais comment mesurer un temps (celui de la boucle for) et afficher ce temps avec tous les chiffres significatifs de la mesure, sans que Delphi ne bascule vers un affichage en notation scientifique !

Citation:

Envoyé par ShaiLeTroll

cela n'a rien à voir avec le code que j'ai soumis qui mesure la précision minimale de QueryPerformanceCounter

Désolé mais tu ne mesures absolument pas la précision de QueryPerformanceCounter :
Dans un premier temps, tu mesures des dates dans Counters[i].

Puis tu calcules :

Citation:

Delta[i] = Counters[i+1] - Counters[i]

Et tu fais la somme :

Citation:

Sum = Delta[0] + Delta[1] + Delta[2] ....

Soit :

Citation:

Sum = (Counters[1] - Counters[0]) + (Counters[2] - Counters[1]) + (Counters[3] - Counters[2])...

Tous les termes se simplifient deux à deux, pour ne donner que :

Citation:

Sum = Counters[MAX_COUNTER - 1] - Counters[0]

que tu divises par le nombre de lecture.

Au final, tu as uniquement mesuré le temps moyen d'exécution de QueryPerformanceCounter avec la boucle.

Si tu n'es toujours pas convaincu, prend ton code et remplace QueryPerformanceCounter par GetTickCount. Ajoute quelques 0 à MAX_COUNTER pour que le test dure plus de 15 ms et regarde qu'elle est la précision que tu penses avoir calculée.
Tu vas la trouver encore bien meilleure que QueryPerformanceCounter !

Si tu veux mettre en évidence l'incertitude sur la mesure de la date avec QueryPerformanceCounter, il faut que tu échantillonnes QueryPerformanceCounter à une fréquence au moins deux fois plus élevée que la fréquence de variation de QueryPerformanceCounter (théorème de Shanon). Tu dois alors montrer que pendant plusieurs mesures successives tu avais la même valeur, et que d'un coup, elle a basculé vers une autre.
Tu pourras ainsi calculer statistiquement, la taille moyenne de l'escalier et l'amplitude des variations de cette taille.
De cette façon, tu vérifieras réellement l'incertitude de la mesure !

C'est faisable avec GetTickCount. Mais pour QueryPerformanceCounter, tu vas te rendre compte que son horloge est plus rapide que la lecture du compteur !

EDIT: Il y a qu'en même un truc que je trouve marrant, c'est que ma machine doit être plus rapide que la tienne, par contre avec ton code, j'obtiens une valeur de 0.6 au lieu des 0.3 que tu dis avoir.
22/07/2009, 19h43
Franck SORIANO

Citation:

Envoyé par FullSpeed

Je comprenbds de cela que on peut choisir et déterminer sur quel coeur un traitement doit etre executer; C'est bien cela?
Pour moi c'est du ressort de l'OS ou du pros. Meme pour une tread on ne peut pas etre sur que les coeurs sont utilmisé?

Ce n'était pas mon propos.

Mais effectivement, on peut demander à l'OS d'executer un Thread sur un CPU particulier à l'aide de SetThreadAffinityMask, et autres fonctions similaires.
Mais j'ai du mal à voir dans quel cas ça peut servir à autre chose qu'à ralentir le traitement. En principe, Windows va utiliser tous les CPU disponibles pour exécuter un maximum de thread activable simultanément. Jouer avec ce genre de chose aura surtout pour effet qu'un thread ne sera pas activé alors qu'il y a des CPU disponibles parce qu'on lui a seulement autorisé l'exécution sur le CPU qui est en cours d'utilisation !

CPU

Je posais la question par simple curiosité pas pour mon solveur
J'avoue me perdre dans vos chronos voivi le mien. Il est correct?
Code:

1 2 3 4 5 6 7 QueryPerformanceFrequency(frequency64); QueryPerformanceCounter(startTime64); Boris_Solver(pb); QueryPerformanceCounter(endTime64); elapsedSeconds := (endTime64 - startTime64) / frequency64;
Je l'ai trouve sur le net.

Pour revevir au defit il me semble que tout le monde a ecrit une
routine pour calculer les candidats d'une case
On pourrait peut être mettre en commun ces recherches
Cette routine joue un rôle important sur la vitesse mais pas surla logique

Je veux bien être le premier a publier son code et à affronter les critiques

Boris

23/07/2009, 09h30
Franck SORIANO

Citation:

Envoyé par FullSpeed

Je l'ai trouve sur le net.

Ce code fait le calcul en seconde. Si tu veux avoir une meilleure précision, il vaut mieux commencer par multiplier par 1000 ou 1000000 pour avoir une durée en milliseconde ou microseconde.

Citation:

Envoyé par FullSpeed

Pour revevir au defit il me semble que tout le monde a ecrit une
routine pour calculer les candidats d'une case
On pourrait peut être mettre en commun ces recherches
Cette routine joue un rôle important sur la vitesse mais pas surla logique

Certainement pas :aie: !

C'est un défi, pas un travail collaboratif. Je supprimerai ce genre de post à vu.
23/07/2009, 12h37
FullSpeed

Code source

C'était pour te donner une chance:ccool:
(Je multiplie par 10000 pour voir)
23/07/2009, 12h55
Franck SORIANO

Citation:

Envoyé par FullSpeed

C'était pour te donner une chance:ccool:)

Tu n'as pas l'air de réaliser que j'organise le défi, je n'y participe pas.
Même si je publierai ma solution, je ne suis en compétition avec personne.
23/07/2009, 17h15
mick605

Citation:

Envoyé par FullSpeed

Pour revevir au defit il me semble que tout le monde a ecrit une
routine pour calculer les candidats d'une case
On pourrait peut être mettre en commun ces recherches
Cette routine joue un rôle important sur la vitesse mais pas surla logique

Je veux bien être le premier a publier son code et à affronter les critiques

Je suis d'accord ... APRES le défi !!!! Ce qui serait bien, c'est qu'a la fin, on sorte un solveur en équipe, le plus performant qu'il soit ! La on aurait un truc du tonnerre !

En plus, [SPOIL] je n'utilise pas de "routine pour calculer les candidats d'une case" ... [/SPOIL] ;)
23/07/2009, 18h18
FullSpeed

Collaboration

Il m" a fallut quend meme beaucoup de travail poiur faire uine routine qui acccelere mon ccode et rlantisse le votre:!

Je pense qu'il, faut etre plus ambicieux: il y a des competences, il y aurta de l'experience on peut attaquer un jeu comlplet avec generateur: i n'y en a pas.
Les logiociels , a ma connaissance, utilsent des collections pas de generation
pour des raisons techniques que nous pourrions essayez de solutionner.

Boris
23/07/2009, 19h00
mick605

Citation:

Envoyé par FullSpeed

Je pense qu'il faut être plus ambitieux : il y a des competences, il y aura de l'experience, on peut attaquer un jeu complet avec générateur : il n'y en a pas.
Les logiciels, à ma connaissance, utilisent des collections, pas de generation
pour des raisons techniques que nous pourrions essayez de solutionner.

Ouais, je suis d'accord. Parce que, quitte a faire un défi, autant en tirer quelque chose de concret a la fin ...

En plus, ce serait mon premier projet collectif ;)
23/07/2009, 20h29
Cl@udius

Citation:

Envoyé par mick605

En plus, ce serait mon premier projet collectif ;)

C'est surement une bonne idée, mais ces échanges sont prématurés. N'oublions pas le cadre de ce défi, comme l'a rappelé Franck précédemment.
Pour l'instant chacun pour soi et Dieu pour tous. ;)
Ensuite nous verrons...
23/07/2009, 20h32
mick605

Bien sur, le défi d'abord !

Pas question d'échanger quoi que ce soit avant la fin du défi ! Au fait, c'est quand ? J'espere que c'est pas bientot, parce que la je peux pas bosser sur le défi ! En tout cas, il me tarde de voir tout les résultats !
23/07/2009, 20h43
Franck SORIANO

Ce n'est pas encore rassure-toi.

On vous préviendra suffisamment longtemps à l'avance.
24/07/2009, 08h04
FullSpeed

Moderateurs

Il est parfaitement logique sue les moderateurs du forum ne puissent pas concourir mais c'est aussi dommage : il y a quelques pointures qu'il aurait ete enrichissant de de mettre au travail sous la pression. Le stress obligeant- a aller plus loin..:D

Boris

PS je met Franck en dehors bien sur il est organisateur et animateur.
24/07/2009, 10h04
Pascal Fonteneau

Hello

de retour de vacances

Juste une petite chose

Citation:

Je pense qu'il, faut etre plus ambicieux: il y a des competences, il y aurta de l'experience on peut attaquer un jeu comlplet avec generateur: i n'y en a pas.
Les logiociels , a ma connaissance, utilsent des collections pas de generation

Ma solution propose un générateur, c'est assez simple a réaliser pour ceux qui ont choisi de résoudre les grilles par la logique

Voir 40 message(s) de cette discussion en une page