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
)
).
Pour voir les perfs que ça donne avec et sans optimisation.