L’éxécution…
Je n’ai pas dit de trouver la solution mais de trouver une somme la plus proche possible de 500 en un temps limité (5mn). (On peut faire nettement mieux que 498.387973897…)
Il n’est pas possible d’énumérer toutes les possibilités ici…
@gege2061 : Merci pour votre coopération lol, plus sérieusement merci c’est sympa et intéressant.
@fran.b : Super c’est sympa d’avoir ajouter un petit exos et tu m’as donnée une idée. Sinon dis voir ta liste ne serait pas comprise plutôt entre 0 et 100 et non 50 ?
Ah oui j’en rajoute un petit qui pourrais être sympa car je l’ai fait en C je vous mettrais le code
après vos réponses,
Créer un algorithme permettant de générer une liste de mots à partir d’une suite de caractères prédéfini. L’objectif étant là, la performance le maximum de mot de 1 à 6 caractères en un temps minimum. Si vous pouvez pousser jusqu’à 8 ou plus amusez-vous.
voici la liste des caractères
[quote=“fran.b”]L’éxécution…
Je n’ai pas dit de trouver la solution mais de trouver une somme la plus proche possible de 500 en un temps limité (5mn). (On peut faire nettement mieux que 498.387973897…)
Il n’est pas possible d’énumérer toutes les possibilités ici…[/quote]
C’est une énumération des parties si je ne m’abuse, je coderais ça 
Pour voir les perfs que ça donne avec et sans optimisation.
@Ashgenesis > Générer des mots du dictionnaires ou autre ?
Pas forcément du dictionnaire, ça doit pouvoir être n’importe quel assemblage mais l’idée est là. L’algo n’est pas complexe là où ça devient plus complexe c’est pour l’optimisation.
[code]let liste= [“a”;“z”;“e”;“r”;“t”;“y”;“u”;“i”;“o”;“p”;“q”;“s”;
“d”;“f”;“g”;“h”;“j”;“k”;“l”;“m”;“w”;“x”;“c”;“v”;“b”;“n”;“A”;“Z”;
“E”;“R”;“T”;“Y”;“U”;“I”;“O”;“P”;“Q”;“S”;“D”;“F”;“G”;“H”;“J”;“K”;
“L”;“M”;“W”;“X”;“C”;“V”;“B”;“N”;“0”;“1”;“2”;“3”;“4”;“5”;“6”;“7”;“8”;“9”];;
let rajoute x l =
let rec boucle res l1 = function
| [] -> (x::l1)::res
| l2 -> (boucle (((List.rev l2)@(x::l1))::res) ((List.hd l2)::l1) (List.tl l2))
in boucle [] [] (List.rev l);;
let fabrique =
let rec boucle entete l = function
| 0 -> print_string (String.concat “” entete);print_newline ();
| _ when l = [] -> ()
| k -> (boucle entete (List.tl l) k);
(List.map (function x -> (boucle x (List.tl l)(k-1)))
(rajoute (List.hd l) entete));();
in boucle [];;
fabrique liste (int_of_string Sys.argv.(1));;[/code]
Ça affiche
[quote]$ ./Genere 8
98765432
89765432
87965432
87695432
87659432
87654932
87654392
87654329
97865432
79865432
78965432
78695432
78659432
78654932
78654392
78654329
97685432
79685432
76985432
76895432
76859432
76854932
76854392
…
[/quote]
et on a
[quote]francois@bling:~/Caml$ time (/tmp/Genere 2 > /dev/null)
real 0m0.018s
user 0m0.007s
sys 0m0.001s
francois@bling:~/Caml$ time (/tmp/Genere 3 > /dev/null)
real 0m0.869s
user 0m0.406s
sys 0m0.019s
francois@bling:~/Caml$ time (/tmp/Genere 4 > /dev/null)
real 0m55.205s
user 0m24.991s
sys 0m1.582s
[/quote]Explosif tout de même, la complexité est en (n!).binomial(l,n) où l = card(liste) et n le nombre de lettres voulues… soit en gros ici si l >> n, en l^n (62^n), le temps est multiplié par 62 à chaque rajout de 1 dans la longueur voulue.
On a bien 0,869*62=53,878 à comparer aux 55,205s réel.
Pour la somme de réels, en triant et en procédant de façon gloutonne on obtient 499.246198063525.
En supposant qu’on fasse un tri-fusion on doit être en n*log(n) niveau complexité (peu ou prou) sachant que la partie “somme gloutonne” se fait en une passe.
Il y a sans doute moyen d’optimiser parceque je suppose que si tu parles de “minutes” de temps d’execution un programme comme :
#!/usr/bin/perl -w
use strict;
use warnings;
use Data::Dumper;
my $fname = "sac.txt";
open(my $handle, "<" , $fname);
my @numbers = <$handle>;
my $max = 500;
@numbers = sort {$b <=> $a} @numbers;
my @sumlist;
my $cursum = 0;
for my $item (@numbers){
if($cursum + $item < $max){
push @sumlist, $item;
$cursum+=$item;
}
}
#print Dumper(@sumlist)."\n";
print $cursum;doit pouvoir être modifié pour faire mieux ^^. On n’est pas exactement dans le cas “scolaire” du knapsack d’une certaine façon puisqu’on a un sac “sans fond” et que la limite se trouve à la valeur de ce dernier et non pas, comme c’est proposé en général, par le nombre d’unités “emportables”.
On pourrait imaginer faire du backtracking et chercher des solutions “plus optimales” depuis celles-ci en reculant dans la liste des éléments utilisés je pense, mais flemme là tout de suite 
La manière gloutonne est une façon de faire mais ne donne pas la meilleure solution loin de là. Le coùut du tri est négligeable à coté des autres méthode.
Entre autres,
en 36s
(mais ça n’est pas la meilleure solution). Pour donner une indication, en se limitant à 5 minutes de calcul, j’ai trouvé
499.928271032=57.5346438343+17.0334454898+75.7969259544+20.9026319593
+62.9199411652+7.40644982461+52.8213197774+53.8651860445+31.8177186297
+30.7653326084+5.85383028871+68.3686480214+14.8421974342
real 4m52.506s
Sinon, en allant jusqu’à 1 heure, j’ai trouvé
499.964120742=6.85180377081+3.02292807563+11.3861047321+5.14089910613
+0.971225682395+2.89972820541+4.98373837349+34.7356876877+85.1318409761
+78.872384595+3.01480164877+81.1865528156+86.1719388021+95.5944862711
J’obtient 499.999969 en 30s.
Je trie la liste par ordre décroissant,
et j’utilise une méthode proche de la recherche exhaustive
en procédant avec une structure recursive classique
mais en prenant soin d’utiliser les nombres les plus gros d’abord.
Si il y en a que ça intéresse, je veux bien tenter une version multithread / multimachine en MPI.
Le code en C:
[code]#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define N (100) // Nombre de flottants a comparer
#define V (500.0) // Valeur dont la somme doit se rapprocher
#define COMPUTATION_TIME (30) // tps de calcul en s
/** Declarations **/
int main(void);
void init_tab(float tab[]);
void sort_tab(float tab[], int debut, int fin);
inline void swap(float *a, float *b);
void print_tab(float tab[]);
typedef unsigned char set_t[N/8 + ((N % 8 != 0) ? 1 : 0)];
typedef struct {
set_t values;
float sum;
} sum_data_t;
inline void set_add(set_t *s, int v);
inline void set_remove(set_t *s, int v);
inline void set_empty(set_t *s);
inline int set_present(set_t *s, int v);
void set_print(set_t *s, float tab[]);
sum_data_t find_sum(float tab[], sum_data_t data, int n, time_t tmax);
/** Definitions **/
int main(void)
{
float tab[N]; // Tableau contenant les reels a comparer
time_t t0 = time(NULL);
srand(t0);
time_t tmax = t0 + COMPUTATION_TIME;
init_tab(tab);
sort_tab(tab, 0, N-1);
print_tab(tab);
sum_data_t data = { .sum = 0 };
set_empty(&data.values);
data = find_sum(tab, data, 0, tmax);
printf(“somme”);
set_print(&data.values, tab);
printf(" = %f\n", data.sum);
return EXIT_SUCCESS;
}
void init_tab(float tab[])
{
int i;
for (i=0 ; i<N ; i++) {
tab[i] = (float) rand() / RAND_MAX * 50;
}
}
/**
- Trie un tableau de float par ordre decroissant
/
void sort_tab(float tab[], int debut, int fin)
{
/ quick sort */
if (debut >= fin) return;
/* le pivot est choisi au milieu du tableau /
int ip = (fin - debut) / 2 + debut; / indice pivot /
float vp = tab[ip]; / valeur pivot */
/* on echange le pivot avec la fin du tableau */
tab[ip] = tab[fin];
ip = fin;
int i = debut;
while (i < ip) {
if (tab[i] >= vp) {
i++;
} else {
tab[ip] = tab[i];
tab[i] = tab[ip - 1];
ip–;
}
}
tab[ip] = vp;
sort_tab(tab, debut, ip);
sort_tab(tab, ip + 1, fin);
}
inline void swap(float *a, float *b) {
float tmp = *a;
*a = *b;
*b = tmp;
}
void print_tab(float tab[]) {
int i;
for (i=0 ; i<N ; i++) {
printf("%f ", tab[i]);
}
putchar(’\n’);
}
inline void set_add(set_t *s, int v)
{
int i = v / 8; // indice
int d = v % 8; // decalage
(*s)[i] |= (unsigned char) 1 << d;
}
inline void set_remove(set_t *s, int v)
{
int i = v / 8; // indice
int d = v % 8; // decalage
(*s)[i] &= ~((unsigned char) 1 << d);
}
inline void set_empty(set_t *s)
{
int i;
for (i=0 ; i < sizeof *s ; i++) {
(*s)[i] = 0;
}
}
inline int set_present(set_t *s, int v)
{
int i = v / 8; // indice
int d = v % 8; // decalage
return ((*s)[i] & ((unsigned char) 1 << d)) ? 1 : 0;
}
void set_print(set_t *s, float tab[])
{
printf("{");
int i;
for (i=0 ; i<N ; i++) {
if (set_present(s, i)) printf("%f, “, tab[i]);
}
printf(”}");
}
sum_data_t find_sum(float tab[], sum_data_t data, int n, time_t tmax)
{
if ((n >= N) || (data.sum >= V)) return data;
sum_data_t d1 = data;
if (time(NULL) < tmax) {
d1.sum += tab[n];
set_add(&d1.values, n);
d1 = find_sum(tab, d1, n+1, tmax);
}
sum_data_t d2 = find_sum(tab, data, n+1, tmax);
if (d1.sum >= V) {
return d2;
} else {
if (d1.sum > d2.sum) return d1;
else return d2;
}
}[/code]
La trace :
time ./sad
48.874928 48.794579 48.766930 48.435478 48.288498 47.163425 46.923443 46.731804 46.233017 44.243988 43.889679 43.883499 43.871532 43.487438 43.335075 42.619370 42.190098 41.717640 40.901173 40.723492 40.360466 39.882793 39.285011 38.566193 38.459301 37.471668 37.239227 36.526993 36.275585 35.775795 34.299057 34.295807 34.038166 32.455868 31.889019 31.517603 30.793783 30.662928 30.346117 29.661764 29.352058 28.760130 28.170591 28.122038 28.070105 26.945034 26.606070 25.989651 25.926979 25.615543 24.136974 24.108459 23.388412 23.149200 23.126448 22.988241 22.182993 21.517275 19.631130 18.020473 16.989527 16.362711 15.745818 15.287122 15.065371 14.144320 14.046489 13.988007 13.662770 13.226750 12.838037 12.642454 11.782660 11.520141 11.147648 10.911448 10.879205 10.288710 9.706027 9.521898 8.517546 8.290475 7.903265 7.838439 7.057403 6.685324 6.605367 4.563943 4.522942 3.762777 3.495317 3.265114 2.970361 2.549328 2.526348 2.143126 1.871138 1.297340 0.684354 0.584297
somme{48.874928, 48.794579, 48.766930, 48.435478, 48.288498, 47.163425, 46.923443, 46.731804, 46.233017, 24.108459, 11.147648, 8.290475, 7.903265, 6.685324, 4.563943, 3.265114, 2.526348, 1.297340, } = 499.999969
./sad 19,11s user 10,46s system 99% cpu 29,752 total
Bon, à mon tour de poser un problème :
On a une carte de la galaxie avec les coordonnées dans l’espace (x, y, z) de systèmes planétaires.
Le but est de trouver les 2 systèmes les plus proches l’un de l’autre le plus rapidement possible.
Les coordonnées de la carte vont chacune de -1.10^6 à +1.10^6 sur chaque coordonnée
et il y a 10^5 planètes placées aléatoirement sur la carte.
Enjoy
[quote=“BBT1”]J’obtient 499.999969 en 30s.
Je trie la liste par ordre décroissant,
et j’utilise une méthode proche de la recherche exhaustive
en procédant avec une structure recursive classique
mais en prenant soin d’utiliser les nombres les plus gros d’abord.
Si il y en a que ça intéresse, je veux bien tenter une version multithread / multimachine en MPI…[/quote]
Je vais regarder ça mais utilise mes données (j’ai donné le lien) car là je ne peux pas comparer avec mes temps… (de plus je me suis gourré, c’est des valeurs entre 0 et 100.0) mais à vue de nez c’est plus efficace que ma méthode (je suis un peu déçu d’ailleurs 
)
Voilà le pgm que j’ai fait:
[code]type somme = {v:float;s:string};;
(* fusion de deux listes triées *)
let fusion =
let rec boucle resultat l1 l2 =
match l1,l2 with
| [],_ -> resultat@l2
| _,[] -> resultat@l1
| (a::ls1),(b::ls2) when (a.v < b.v) -> (boucle (resultat@[a]) ls1 l2)
| _,(b::ls2) -> (boucle (resultat@[b]) l1 ls2)
in boucle [];;
(* on enlève les elts > seuil *)
let tronque liste seuil =
let rec boucle resultat liste_en_cours =
match liste_en_cours with
| (a::suite) when (a.v <= seuil) -> (boucle (resultat@[a]) suite)
| _ -> resultat
in (boucle [] liste);;
let add e x = {v=x.v+.e;s=x.s^"+"^(string_of_float e)};;
let rajoute liste elt seuil =
(tronque (fusion liste (List.map (function x-> add elt x) liste)) seuil);;
(* on tronque la liste de telle manière que deux éléments consécutifs vérifient a’>(1+eps).a *)
let selection epsilon lst =
let rec boucle elt_en_cours liste_renvoyee liste =
match liste with
| [] -> liste_renvoyee
| a::suite when a.v>(1.0 +. epsilon)*.elt_en_cours
-> (boucle a.v (liste_renvoyee@[a]) suite)
| a::suite -> (boucle elt_en_cours liste_renvoyee suite)
in match lst with
| [] -> []
| a::suite -> (boucle a.v [a] suite);;
(* on ajoute les éléments les uns après les autres *)
let variante_eps_b epsilon lst somme =
let rec boucle liste reste n =
match reste with
| [] -> List.hd (List.rev liste)
| a::suite -> print_int n;print_newline ();
(boucle
(selection epsilon
(rajoute liste a somme))
suite (n-1))
in
(boucle [{v=0.0;s=“0”}] lst (List.length lst));;
let resolution_eps_b epsilon lst = (variante_eps_b
(epsilon /. (float_of_int (List.length lst)))
lst);;
(* pour faire une liste aléatoire *)
let rec rand_list borne = function
| 0 -> []
| n -> (Random.float borne)::(rand_list borne (n-1));;
let grosse_liste = [
76.6006173876 ;
53.2095327249 ;
62.8074649884 ;
6.11430589708 ;
…];;
76.3344025048 ;
99.8239434767 ];;
let res= (resolution_eps_b (float_of_string Sys.argv.(1)) grosse_liste (float_of_string Sys.argv.(2)))in
print_string ((string_of_float res.v)^"="^res.s);;
print_newline ();;
[/code]
Je ne conserve que les sommes suffisamment éloignés les unes des autres, ça garantit un algorithme en O(n²/eps) et en pratique en O(n/eps), ça garantit aussi la marge d’erreur faite mais avec ces données c’est moins efficace. Il serait peut être meilleur en prenant des données étalées et un seuil plus grand (Il faudrait faire un test…) mais je pense qu’il restera moins efficace que le tien:
Je trouve avec tes données
499.890758=0+46.731804+43.487438+38.566193+37.471668+36.526993+34.295807
+28.76013+28.122038+26.945034+25.926979+24.136974+22.182993+16.989527
+16.362711+15.745818+14.046489+13.988007+9.521898+6.685324+3.762777
+3.495317+2.970361+1.871138+1.29734
en 7mn et des brouettes.
Comme quoi une bonne heuristique est meilleure qu’une approximation même controlée en pratique (alors qu’en théorie non…)
Précision: ton algorithme est nettement meilleur dans les faits, j’ai essayé aussi avec la liste par ordre croissant:
Tout d’abord la victoire de Caml sur le C (en fait je pense qu’il doit y avoir un souci dans ton code, ça n’est pas normal cette différence de performance, il faudrait le vérifier mais je n’ai pas trop le temps):
Avec tes données, en 2s
[quote]500.=48.874928+48.794579+48.76693+48.435478+48.288498+47.163425
+46.923443+46.731804+46.233017+43.335075+14.046489+4.563943
+3.762777+3.495317+0.584297
real 0m2.016s
Les sommes successives trouvées:
francois@bling:~/Caml$ time ./Osacados2ibis 1.0 500.0
499.890404=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+44.243988+24.136974+1.29734
499.987628=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+44.243988+23.388412+2.143126
499.993659=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+44.243988+22.988241+2.549328
499.999823=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+44.243988+22.988241+1.871138+0.684354
499.999922=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+44.243988+10.879205+6.605367+4.563943+3.495317
499.99997=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+44.243988+9.706027+7.903265+3.265114+2.526348+2.143126
499.999971=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+43.889679+10.28871+8.290475+3.495317+2.526348+1.29734
499.999988=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+43.871532+11.147648+9.521898+3.265114+1.29734+0.684354
499.999996=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443
+46.731804+46.233017+43.487438+10.28871+6.685324+3.495317+3.265114+1.29734+0.684354 +0.584297
500.=0+48.874928+48.794579+48.76693+48.435478+48.288498+47.163425+46.923443+46.731804
+46.233017+43.335075+14.046489+4.563943+3.762777+3.495317+0.584297
[/quote]
Le programme:
[code]type somme = {v:float;s:string};;
(* tri d’une liste de réel )
let rec tri_rapide l =
let rec partage x l1 l2 = function
| [] -> (l1,l2)
| y::ll -> if x < y ( mettre > pour le tri décroissant *)
then (partage x l1 (y::l2) ll)
else (partage x (y::l1) l2 ll)
in match l with
| [] -> []
| x::ll -> let (l1,l2) = (partage x [] [] ll) in
(tri_rapide l1)@[x]@(tri_rapide l2);;
let maxi = ref {v=0.0;s=“0”};;
let temps = (float_of_string Sys.argv.(1));;
let traite s = if (s.v > (!maxi).v) then (
maxi:=s;print_float s.v;print_string ("="^s.s);print_newline ());;
let add e x = {v=x.v+.e;s=x.s^"+"^(string_of_float e)};;
let rec cherche sol reste butee = match reste with
| [] -> (traite sol);if (Sys.time () >= temps) then failwith “fini”
| a::suite when a > butee -> (cherche sol suite butee)
| a::suite -> ((cherche (add a sol) suite (butee -. a));
(cherche sol suite butee));;
let grosse_liste = [
76.6006173876 ;
53.2095327249 ;
62.8074649884 ;
…
5.87672187988 ;
76.3344025048 ;
99.8239434767 ];;
cherche (!maxi) (tri_rapide grosse_liste) (float_of_string Sys.argv.(2));;
[/code]
En une seconde
[quote]499.999672721=0.823815509831+0.971225682395+2.73708440896+2.89972820541
+3.01480164877+3.02292807563+4.98373837349+5.14089910613+5.85383028871
+5.87672187988+6.11430589708+6.85180377081+7.40644982461+11.3861047321
+12.0469895844+12.417446767+13.3202226366+13.6029593057+14.6877222571
+14.8421974342+15.7364627081+17.0334454898+20.9026319593+23.1362279621
+23.2963494749+26.313173451+30.5372024126+31.8177186297+33.9888211399
+36.5765033284+39.8388409985+52.8213197774
real 0m1.009s
ou par ordre décroissant
499.999993256=99.8239434767+99.7235716825+99.3410284839+98.3687380235
+78.7359242322+13.3202226366+5.87672187988+3.01480164877
+0.971225682395+0.823815509831
real 0m0.662s
[/quote]
En 10s
[quote]499.999969477=0.823815509831+0.971225682395+2.73708440896+2.89972820541
+3.01480164877+3.02292807563+4.98373837349+5.14089910613+5.85383028871
+5.87672187988+6.11430589708+6.85180377081+7.40644982461+11.3861047321
+12.0469895844+12.417446767+13.3202226366+13.6029593057+14.6877222571
+14.8421974342+15.7364627081+17.0334454898+20.9026319593+23.1362279621
+23.2963494749+30.7653326084+34.7356876877+34.8696397735+37.3201741611
+45.7887165638+68.4143256997
real 0m11.440s
et par ordre décroissant
499.999999309=0+99.8239434767+99.7235716825+99.3410284839+98.3687380235
+45.7887165638+29.4346057232+12.417446767+6.11430589708
+5.14089910613+3.02292807563+0.823815509831
real 0m13.496s
[/quote]
Par ordre croissant, c’est moins bon ce qui se comprend facilement en fait
en 1mn
[quote]499.999994849=0.823815509831+0.971225682395+2.73708440896
+2.89972820541+3.01480164877+3.02292807563+4.98373837349+5.14089910613
+5.85383028871+5.87672187988+6.11430589708+6.85180377081+7.40644982461
+11.3861047321+12.0469895844+12.417446767+13.3202226366+13.6029593057
+14.6877222571+14.8421974342+15.7364627081+17.0334454898+20.9026319593
+23.1362279621+23.2963494749+52.0153159277+52.8213197774+62.8074649884
+84.2498011722
real 0m50.070s[/quote]
en 3mn
[quote]499.999997615=0+0.823815509831+0.971225682395+2.73708440896+2.89972820541
+3.01480164877+3.02292807563+4.98373837349+5.14089910613+5.85383028871
+5.87672187988+6.11430589708+6.85180377081+7.40644982461+11.3861047321
+12.0469895844+12.417446767+13.3202226366+13.6029593057+14.6877222571
+14.8421974342+15.7364627081+17.0334454898+20.9026319593+23.2963494749
+32.6907368819+33.9888211399+42.2539841857+78.872384595+87.2242057917
real 3m17.307s
[/quote]
et par ordre décroissant
en 30s:
[quote]499.999999309=0+99.8239434767+99.7235716825+99.3410284839+98.3687380235
+45.7887165638+29.4346057232+12.417446767+6.11430589708+5.14089910613
+3.02292807563+0.823815509831
[/quote]
et en mojns de 2mn
[quote]499.999999554=0+99.8239434767+99.7235716825+99.3410284839+98.3687380235
+17.0334454898+15.7364627081+14.8421974342+14.6877222571+13.3202226366
+12.417446767+6.11430589708+5.85383028871+2.73708440896
real 1m47.338s
[/quote]
Bon, le truc 3D maintenant… mais après mes copies.
Est-ce que tu as une différence de temps d’exécution significative entre le cas où tu fournis statiquement les données et le cas ou le programme les acquiert dynamiquement ?
Je me disais qu’en théorie, le compilo pourrait être assez malin pour
précalculer un max de valeurs… Mais bon, le temps de compilation s’en resentirai forcément…
J’avais testé 30 sec au hasard (le temps que j’étais prêt à attendre devant mon écran quoi) mais on peut
sûrement faire mieux en compilant en -O3 et en limitant le nombre d’appel à time() (ce que je n’ai pas fait).
Si je suis motivé je fais un petit bench ce soir 
J’ai vraiment pas le temps de coder ces exos, ça me saoul.
BBT1, si tu veut une gestion du temps sympa utilise la fonction signal() et la fonction alarm(). Comme ça tu te retrouve à faire simplement un test sur un entier plutôt que d’appeler une fonction système.
Tu n’es pas obligé…
Je crois que c’est de ne pas avoir le temps d’y participer qui le saoule, non les post
Et moi j’pane rien à vos trucs …
[quote=“BBT1”]Est-ce que tu as une différence de temps d’exécution significative entre le cas où tu fournis statiquement les données et le cas ou le programme les acquiert dynamiquement ?
[/quote] Non, tu penses que fabriquer 100 flottants n’est pas très long…
[quote]
J’avais testé 30 sec au hasard (le temps que j’étais prêt à attendre devant mon écran quoi) mais on peut
sûrement faire mieux en compilant en -O3 et en limitant le nombre d’appel à time() (ce que je n’ai pas fait).
Si je suis motivé je fais un petit bench ce soir [/quote]
Ce qui m’étonne c’est que même si le compilateur d’Ocaml est performant, même avec camllight, en 10s je calcule le 500 exact avec tes données, avec des données aléatoires:
[quote]$ time ./Osacados2iter 10.0 500.0
499.999999867=49.7632286064+49.5562680373+49.5120574065+48.2926468525
+48.1207958637+47.8849296851+47.8756064726+47.7175090038+47.0999329838
+37.7750163514+10.4857684398+6.30742327741+6.25341923753+1.38285207828
+0.999654853589+0.93905730733+0.0338334098468
real 0m10.100s
[/quote]C’est pour ça que je pense qu’il doit y avoir un truc dans le code (pas l’algorithme…), Ocaml est vraiment efficace mais à ce point ça m’étonne.
Misterfreeze: je n’avais pas compris, dsl
Mais il y a pas de mal 
. De toute manière je les ferais quand j’aurais du temps, c’est à dire peut être dans 2 ou 3 semaines sinon 2 mois.
[quote=“MisterFreez”]J’ai vraiment pas le temps de coder ces exos, ça me saoul.
BBT1, si tu veut une gestion du temps sympa utilise la fonction signal() et la fonction alarm(). Comme ça tu te retrouve à faire simplement un test sur un entier plutôt que d’appeler une fonction système.[/quote]
Pas con, cette approche me semble plus saine que faire du poll sur time() .
Merci MisterFreez, j’y penserai.
Bon, je relance le sujet avec un “jeu” assez connu, mais qui reste assez dur à coder ( je n’ai pas encore fini moi-même, mais presque): le jeu de la vie.
Explications:
vous avez n cases.
on part avec m cases “vivantes”, càd colorées.
Voila les règles:
Chaque case "vivante" avec:
- de 2 voisins ==> meurt
+ de 3 voisins ==> meurt
2 ou 3 voisins ==> reste en vie
Chaque case vide ou "morte" avec:
3 voisins ==> devient "vivante"Bonne chance.
C’est plus de 4 voisins => meurt.
Non, là je ne ferais rien car de toute façon vis à vis de Golly, ce serait ridicule (apt-get install golly, essaye tu verras c’est époustouflant et c’est la preuve de la puissance des maths). Je te suggère aussi de regarder là http://code.google.com/p/ruletablerepository/wiki/TheRules, la variante colorisée a été une grande déception pour moi car je croyais être l’inventeur de cette variante en 1982 jusqu’à ce que quelqu’un (il y a un an environ, quand j’ai fait le jeu de règles pour Golly) m’a indiqué avoir vu ces règles avant (il semble que cette variante date de 1973 en fait).