Bonjour, je voudrais savoir si quelqu'un d'entre vous a le code miracle.
J'ai un vector<double> dont les éléments sont rangés par valeurs croissantes.
Pour réaliser une interpolation, je doit trouver entre quels éléments se trouve une valeur U, non nécessairement dans le tableau
mon code c'est ça : (tout bêtement...)

Après il y a la procédure d'interpolation, mais c'est ce while qui prend le plus de temps!
Savez vous comment accélérer cette recherche?

mets un iondex  
 
utilise une structure plus évoluée que les vector ( arbre binaire de recherche par exemple )

 
Je ne pensais pas que cette seule ligne de code allait arriver à m'ennuyer, mais comme elle est répétée des milliers de fois, elle en est devenue critique.
Je vais essayer de mettre un indexe tous les 100 ou 200 points et scanner d'abord cet indexe. C'est bien ça, la première solution que tu proposes?
 

il faut voir  
par contre, il faut bien prendre en compte le temps de mise a jour de l'index
 
mais ca me semble une bonne solution

Faudrait ptet commencer par faire une binary search au lieu d'une recherche séquentielle hein, avant même de penser aux binary trees ou aux index

utilse un std::set qui va te maintenir l'ordre comme il faut. Et il y a toutes les fonctions (upper/lower bound, etc) pour faire ce que tu veux.
 
edit: sinon si tu es effectivement trié, utilise directement lower/upper_bound/equal_range sur ton vector, ça va y aller par dichotomie et ça va booster en logn

Ok merci, je viens d'essayer le lower_bound. La routine en question passe de 8s à 3s de calcul. Ca doit me ramener le temps de calcul total de 12h à 4-5h. Il ne me reste plus qu'à traquer les gouffres à secondes partout dans le programme...

comment tries-tu tes données ? qsort ? std::sort ? tu les tries plusieurs fois ? si t'en as vraiment beaucoup et que la précision va, tu peux essayer de passer en float

par contre la réduction du temps avec std::lower_bound est logarithmique, donc si c'est bien ce point là qui consomme du temps CPU, la réduction du temps d'exécution pourrait être plus grande que ta prévision

profite du fait que ton tableau est range par ordre croissant pou faire une recherche dichotomique qui a une complexite en ~log(n)
le tien a une complexity lineaire

Ouep, joneal, je pense que c'est ce que fait lower_bound. Les 3s secondes restantes sont difficilement compressibles. Elles ne sont plus dues à la recherche dans le tableau, mais à la procédure qui est derrière (interpolation de neville en se servant des 4 points avant et des 4 points après). Je vais essayer aussi de l'optimiser, mais le nombre d'opérations à effectuer va être difficile à diminuer et joue beaucoup sur la précision du calcul.  Pour le tri du tableau, Taz, il est fait une seule fois au début du prog et ne rentre pas dans la boucle. Pour l'utilisation des float, j'ai un peu peur, parce qu'il y a des E-34 à manipuler. Mais bon, je suis passé de 58% d'occupation mémoire il y a quelques jours à 7% en bidouillant bien.
C'est au programme des études en info tous ces problèmes?

Ca dépend où tu fais tes études, mais dans le cas précis le passage de la recherche linéaire à la binary search c'est de l'algorithmique, donc oui.
 
Mais les études ne sont pas impératives sur le sujet, il y a de très bon bouquins d'algorithmique (même s'ils ne sont pas nécessairement donnés).

10**34 ça passe dans un float

toi t'as l'air bien aware

 
tien ! toi aussi t'as l'air "aware"

mais c'est peut-être une blague de programmeur C++ que tu ne saisis pas ?

T'as aussi des algos inspires de la dichotomie un peu plus rapides (qui comme d'hab' imposent des donnees triees) :
- on regarde les 2 bornes du vecteur
- on regarde la taille du vecteur
- en fonction de la valeur cherche, on fait un truc genre  

- on rappelle entre l'index trouve et la borne sup ou inf qui va bien en cas d'echec.
 
Ca fonctionne plutot bien quand la distribution est uniforme.
 
 
 
 
Bon, sinon, tu peux pas prendre une structure un peu plus habile ?  

J'ai pensé à ça hier, justement. Pour une raison que j'ignore, je tombe complètement à coté de la vraie valeur, pourtant le pas entre les données est constant. J'ai dû me planter, je referai un essai. Il n'y a aucune raison pour que ça ne fonctionne pas.
 
Ce qui est rageant, c'est que je sais que je peux diviser le temps de calcul par 4, mais je ne sais pas qui me bouffe mes secondes.
Pour schématiser, un calcul c'est ça (à répéter des milliers de fois) :
 
calcul=0;
for (i=0; i<beaucoup_beaucoup)
{
     valeur=recherche_dans_le_tableau(calcul);
     calcul=calcul1(valeur)*calcul2(valeur);
}
 
Je sais que la recherche dans le tableau est faite à peu près 3 millions de fois à chaque fois, mais le calcul derrière aussi.
Comment puis-je évaluer le temps passé dans chacune des fonctions? Au départ pour évaluer, je retirais tout simplement la fonction du calcul, mais comme le calcul est itératif, ça ne me donne aucune estimation valable. Mettre des espèces de timers?

votre truc ça ne marche que si les valeurs sont parfaitement et linéairement croissante. Ce n'est pas le cas. Si c'était le cas, on pourrait faire un addressage direct.
 
Sors ton :
- profiler
- ltrace
- boost::timer

 
J'ai sorti le <ctime>. Même si CLOCKS_PER_SEC me dit 1000 000, je pense que j'ai une précision de 1 à 10 millisecondes.
Le gouffre à secondes vient d'une librairie que j'utilise (matpack). Là, je n'ai plus trop de solution. Va falloir que je fasse avec.
La gsl offre le même type de fonction mathématique que celle qui me faut, mais elle est encore plus lente.

C'est comme si tu cherchais un mot dans le dico, pourtant y a pas autant de mots en A que en Z. Tu sais a peu pres ou taper.

bah je vois pas comment à part par une analyse statistiques en o(n)... et écrire un algo spécifique avec un c log(n) et un c < 1. Et l'implémenter correctement. J'attends de voir.

Il ne se fait pas en une iteration l'algo la    
Tu le rappelles du bon cote en cas d'echec (encore une fois, c'est vraiment comme si tu cherchais un mot dans le dico).

Moi je dirais que la proposition des arbres triés est à considérer.

en quoi ça serait plus rapide qu'une dichotomie dans un tableau ?

Bon, prenons un dictionnaire. Tu cherche le mot : truelle.
 
Dichotomie : tu ouvres au milieu, tu regardes si truelle est a gauche ou a droite.
Autre methode : tu ouvres a la lettre t, tu regardes si c'est a gauche ou a droite.

Dans ce cas là, je pense qu'on procède également par dichotomie, mais l'indexe (ta mémoire ou un marque pages) que tu utilises change juste les bornes de ton ensemble de départ.
 

nan mais ça d'accord : mais tu divises comment ta collection de double ? et pour quel gains ? et comment est-ce que tu définis ton classement lexicographique de double ?

Je ne sais pas. Peut-être qu'il y a moyen de se servir du résultat précédent comme point de départ.

 
Diviser la collection de double ? On precede sur un intervalle, on rappelle en changeant les bornes.
Quels gains ? Il faudrait voir en pire cas comment ca se comporte (probablement moins bien que la dicho). Pour les cas moyens, c'est certainement plus rapide.
Classement ? Je vois pas ou est le souci pour utiliser la relation d'ordre total entre double. C'est trie, on utilise la formule plus haut  

Comment détermines-tu les intervalles ? Comment détermines-tu en une opération que x fait partie de l'intervalle I ? Si tu fais plusieurs comparaisons, alors c'est comme de la dichotomie ...
 
J'attends toujours une explication sérieuse sur comment réaliser un tri lexicographique sur des double pour permettre un indexage ensuite. Un dictionnaire, c'est un Trie. Je ne vois pas comment implémenter cette structure de données sur des doubles tout en maintenant la relation d'ordre.

 
Tu rappelles sur l'intervalle delimite par la borne initiale quivabien et le nouvel index que tu viens de trouver.
 
J'ai dis des le depart que c'etait inspire de la dichotomie hein
Et non justement, en cas moyen ce n'est pas comme de la dichotomie.
 
L'auteur du topic a ecrit : J'ai un vector<double> dont les éléments sont rangés par valeurs croissantes.
Tu blagues la ?

Non je ne blagues pas. Tu me parles de faire comme avec un dictionnaire pour accélérer les choses. Comment fait tu pour aller __directement__ à la lettre avec des doubles ? Comment établit tu ce classement par lettre ?

 
En tenant compte de la dérivée en chacun des points sur lesquels ont tombe? Y aller directement, c'est possible uniquement si les points sont _strictement_ équidistants.  
Moi non plus, je ne comprends pas ce qui te gêne, Taz.

Tu n'y va pas directement, sinon il n'y aurait aucun besoin de rappeler sur l'intervalle  
Tu t'en rapproches juste plus vite.
 
 
edit : sinon tu prends un gros bouquin, avec plein de double dedans, classes par ordre croissant. Comment ferais-tu pour trouver les 2 qui encadre le double que tu cherches ? Je regarde celui de la premiere page, celui de la derniere page et j'ouvre a peu pres la ou il me parait etre. Je recommence apres a gauche ou a droite...

ah bon ? comment ça plus vite ? par dichotomie, il faut log(n) comparaisons. Pour comparer deux nombres (choisir l'intervalle), il faut une seule comparaison. Pour en comparer 3 (pour une selection d'intervalles si par exemple tu divises en 3 intervalles), il te faut 2 comparaisons en moyenne. Donc dans un cas, en 2 comparaisons, tu as divisé par 4 la plage à rechercher, et dans l'autre cas, tu as divisé seulement en 3. Je ne vois pas le gain.
 
Et donc ton histoire de dictionnaire ne tient absolument pas la route. Choisi tes termes. Un dictionnaire, c'est un acces indexé. Quand tu veux la lettre E, tu y accèdes directement. Il n'y a donc aucun dictionnaire dans ton histoire. C'est pas la peine de me prendre pour un idiot. Dans ton dernier exemple du livre, tu te démontes complètement, plus du tout question de simple dictionnaire.

 
Je parle de dictionnaire comme le livre, le truc en papier la, pour essayer de te faire comprendre l'algo. Tu fais l'idiot en ne voulant comprendre qu'un autre sens informatique pour ce mot.
 
As-tu compris mon premier post ? Depuis le depart j'ai l'impression que tu survoles, que tu t'obstines a croire que c'est comme de la trichotomie ou Nchotomie (comme tu veux). En effet, la complexite de ces algorithmes sont identiques.
Mais la, le choix de l'endroit ou tu coupes en 2 est different.
 
Pourtant c'est le truc bidon que j'ai vu juste apres la dichotomie et avant le hachage avec mon prof d'algo. Si tu piges pas un truc trivial comme ca, je laisse tomber   Je sais pas, prends un papier, dessines un exemple  

 
c'est toi qui t'exprimes mal.[/quotemsg]
 
laisse tomber, reviens quand tu seras un peu sérieux et que t'auras envie d'arrêter la bidouille. Ça m'apprendre à voulour discuter. J'aurais du dès le début te dire que ta solution c'est de la merde, avec même complexité (voire même avec une constante multiplicatrice supérieure) et une implémentation plus lourde. Je te prouves que ça l'est et  ton seule argument c'est "je l'ai appris à l'école". T'es bidon. Bonsoir.

 
Ah bon ?  
Je suis curieux. Toi qui me parle de complexite log(n) pour la dichotomie, on sent que t'es cale    
 
Comme d'hab, je te suggere de relire mon premier post dans lequel je proposais une solution a un probleme pour lequel la structure est imposee. Si tu ne peux faire abstraction de ce simple fait, ne discutes pas oui...

 
Ben ... il a raison:

 
http://fr.wikipedia.org/wiki/Dichotomie