[C/algo] Cumul des termes d'un vecteur

Le
JKB
Bonjour à tous,

Je suis en train de me poser un problème d'algorithmie (peut-être de
base, mais sur ce coup, google n'est pas mon ami). J'ai un vecteur de
real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.

Lors de mes lointaines études, j'ai appris qu'il fallait toujours
additionner les termes d'une accumulation en partant des plus petits en
valeur absolue. J'ai donc écrit la chose suivante :

real8
sommation_vecteur_reel(real8 *vecteur, unsigned long *taille,
logical1 *erreur_memoire)
{
unsigned long nombre_elements;
unsigned long pointeur;

/*
* Sommation des termes en commençant par le plus petit
*/

nombre_elements = (*taille);
(*erreur_memoire) = d_faux;

while(nombre_elements != 1)
{
pointeur = (*taille) - nombre_elements;
tri_vecteur(&(vecteur[pointeur]), nombre_elements);
vecteur[pointeur + 1] += vecteur[pointeur];
nombre_elements--;
}

return(vecteur[(*taille) - 1]);
}

qui a le mérite de respecter la règle précédente (même si c'est du
goret-coding) . Maintenant, sur un vecteur de quelques millions d'éléments,
le temps de calcul peut être très long tri_vecteur est un tri shell Metzner
qui trie en fonction de la valeur _non_ signée. Je suppose qu'il existe un algo
largement plus optimal. Quelqu'un aurait-il un pointeur, un article ?

Merci de vos lumières,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
espie
Le #18562581
In article JKB
Bonjour à tous,

Je suis en train de me poser un problème d'algorithmie (peut-être de
base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de
real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.

Lors de mes lointaines études, j'ai appris qu'il fallait toujours
additionner les termes d'une accumulation en partant des plus petits en
valeur absolue. J'ai donc écrit la chose suivante :



T'es sur d'etre oblige de tout trier ?

Si tu en as vraiment beaucoup, tu peux pas te contenter de faire ca ordre
de grandeur par ordre de grandeur ?

Ton algo deviendrait lineaire, du coup...
Jean-Marc Bourguet
Le #18562741
JKB
Je suis en train de me poser un problème d'algorithmie (peut-être
de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur
de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.



Ça, c'est une question pour Vincent.

En attendant un spécialiste d'analyse numérique, tu peux faire quelque
chose qui s'approche de la double précision (et que j'ai trouvé si j'ai
bonne mémoire chez D.E.K.)

real8 sum(real8 const* array, int size)
{
real8 result = 0.0, error = 0.0;
int i;
for (i = 0; i < size; ++i) {
real8 temp = result;
real8 y = array[i] + error;
result = temp + y;
error = (temp - result) + y;
}
return result;

}

Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un
ordre, tu peux faire des sommes partielles puis les sommer) dépend des
données. Si tous les nombres sont positifs, effectivement l'ordre
croissant est la réponse, mais si il y a des valeurs négative, le trouver
est dans l'absolu un problème NP-complet.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Eric Levenez
Le #18562731
Le 02/02/09 20:34, dans « JKB »
Je suis en train de me poser un problème d'algorithmie (peut-être de
base, mais sur ce coup, google n'est pas mon ami...).



fr.comp.algorithmes est ton ami.

--
Éric Lévénez
FAQ de fclc :
Arnaud Giersch
Le #18562841
Lundi 02 février 2009, vers 20:34:23 (+0100), JKB a écrit:

while(nombre_elements != 1)
{
pointeur = (*taille) - nombre_elements;
tri_vecteur(&(vecteur[pointeur]), nombre_elements);
vecteur[pointeur + 1] += vecteur[pointeur];
nombre_elements--;
}



Ça me semble tellement gros que j'ai l'impression qu'il y a une
subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour
chaque élément ? Qu'est ce qui ne va pas avec quelque chose comme :

tri_vecteur(vecteur, *taille);
unsigned i;
real8 somme = 0.0;
for (i = 0 ; i < taille ; i++)
somme += vecteur[i];
return somme;

Ensuite, pour le tri, ça ne coûte pas grand chose de comparer avec le
qsort standard avant de chercher plus loin.

Arnaud
Arnaud Giersch
Le #18562981
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:

Ça me semble tellement gros que j'ai l'impression qu'il y a une
subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour
chaque élément ?



Je me réponds tout seul... pour faire à chaque fois la somme des deux
éléments les plus petits. Dans ce cas, tu peux essayer de maintenir
une structure de tas (heap). Ça derait être moins coûteux que de
recommencer le tri à chaque fois.

Arnaud
JKB
Le #18563361
Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,
Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB
Je suis en train de me poser un problème d'algorithmie (peut-être
de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur
de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.



Ça, c'est une question pour Vincent.

En attendant un spécialiste d'analyse numérique, tu peux faire quelque
chose qui s'approche de la double précision (et que j'ai trouvé si j'ai
bonne mémoire chez D.E.K.)

real8 sum(real8 const* array, int size)
{
real8 result = 0.0, error = 0.0;
int i;
for (i = 0; i < size; ++i) {
real8 temp = result;
real8 y = array[i] + error;
result = temp + y;
error = (temp - result) + y;
}
return result;

}

Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un
ordre, tu peux faire des sommes partielles puis les sommer) dépend des
données. Si tous les nombres sont positifs, effectivement l'ordre
croissant est la réponse, mais si il y a des valeurs négative, le trouver
est dans l'absolu un problème NP-complet.



C'est bien mon problème ;-) Et comme ça entre dans un autre algo
NP-complet...

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
JKB
Le #18563351
Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,
Arnaud Giersch ?crivait dans fr.comp.lang.c :
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:

Ça me semble tellement gros que j'ai l'impression qu'il y a une
subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour
chaque élément ?



Je me réponds tout seul... pour faire à chaque fois la somme des deux
éléments les plus petits.



C'est exactement ça.

Dans ce cas, tu peux essayer de maintenir
une structure de tas (heap). Ça derait être moins coûteux que de
recommencer le tri à chaque fois.



Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe
comment, soit la technique n'apporte pas grand chose sur mes données.

Cordialement,

JKB

--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
JKB
Le #18563571
Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,
Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB
Je suis en train de me poser un problème d'algorithmie (peut-être
de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur
de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.



Ça, c'est une question pour Vincent.

En attendant un spécialiste d'analyse numérique, tu peux faire quelque
chose qui s'approche de la double précision (et que j'ai trouvé si j'ai
bonne mémoire chez D.E.K.)

real8 sum(real8 const* array, int size)
{
real8 result = 0.0, error = 0.0;
int i;
for (i = 0; i < size; ++i) {
real8 temp = result;
real8 y = array[i] + error;
result = temp + y;
error = (temp - result) + y;
}
return result;

}



Je ne vois pas bien ce soir comment ce truc fonctionne (enfin,
théoriquement parlant...). S'il y avait quelque part un pointeur avec
une explication, je suis preneur.

Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un
ordre, tu peux faire des sommes partielles puis les sommer) dépend des
données. Si tous les nombres sont positifs, effectivement l'ordre
croissant est la réponse, mais si il y a des valeurs négative, le trouver
est dans l'absolu un problème NP-complet.



J'ai aussi commencé par scinder mon problème pour avoir des sommes
partielles. Le souci est que je ne maîtrise plus la dérive...

Cordialement,

JKB

Xpost et fu2 à fca (que j'avais oublié...)
--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Marc
Le #18563711
JKB wrote:

Arnaud Giersch ?crivait dans fr.comp.lang.c :
Dans ce cas, tu peux essayer de maintenir
une structure de tas (heap). Ça derait être moins coûteux que de
recommencer le tri à chaque fois.





D'accord avec ça.

Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe
comment, soit la technique n'apporte pas grand chose sur mes données.



Pour rester dans le code trivial, on peut remplacer le tri par une
recherche du plus petit élément et son échange avec le premier (ou
dernier, je n'ai pas bien suivi).
Publicité
Poster une réponse
Anonyme