Bonjour tt le monde,
 
J'ai un problème théorique : je dois lire un fichier texte possédant environ 900 000 lignes,mais susceptible d'être plus grand (disons 900 000 pour l'instant ). Chaque ligne contient les coordonnées d'un objet à un pas de temps.  
 
Schématiquement, ça ressemble à ça :  
 
xt0 yt0 zt0 AngleXt0 AngleYt0 AngleZt0
xt1 yt1 zt1 AngleXt1 AngleYt1 AngleZt1
xt2 yt2 zt2 AngleXt2 AngleYt2 AngleZt2
...
xtn ytn ztn AngleXtn AngleYtn AngleZtn
 
 
La ieme ligne indique la position de l'objet à l'instant i.
 
Je dois être capable d'animer un objet suivant la trajectoire décrite par ces positions. Jusqu'ici aucun probleme.
 
Je dois pouvoir utiliser un curseur pour me déplacer dans le temps, en avant comme en arrière. Mon problème est le suivant : comment minimiser le temps d'attente de l'utilisateur lorsqu'il place son curseur à ti et qu'il veut voir l'objet à sa position à l'instant ti ?
 
Ma réponse bête est : on lit tout le fichier dès le départ, on stocke toutes les positions dans un tableau géant et on va chercher ces positions dans le tableau quand on en a besoin.
 
Cette technique promet d'être particulièrement gourmande en mémoire vu la taille du tableau, sans compter qu'il y a d'autres infos que seulement des coordonnées (entre autre l'objet est articulé...)
 
j'ai entendu parler du mappage de fichier, de lecture par bloc... Quelqun pourrait il ou elle m'en dire plus ?
 
En vous remerciant boucou boucou d'avance  

Tu peux p-ê indexer tes lignes avec le temps t (ou le numéro de ligne xtn , ce qui revient +/- au même) comme clé dans une hash_map ou qq chose comme ça. La hash_map te donne la position de la ligne à lire dans le fichier, par exemple. Après, il y a certainement des optimisaions à faire pour diminuer le nombre d'accès fichier si tu dois lire plusieurs lignes d'un coup.
Et si tu peux stocker ton fichier en binaire plutôt qu'en texte, ça sera à la fois plus rapide et moins gourmand.

Attention, ceci n'est pas du C++, c'est du C.
 
Pour éviter les temps de latence, utiliser mmap est effectivement la meilleure solution. (Sous unix: man mmap. Sous windows, ça fonctionne avec une autre API). Ca te permet de considérer que le fichier est tout entier en mémoire, et c'est l'OS et le CPU qui font le reste (tu économises énormément de copies entre l'OS et ton appli, et ça t'évites de passer du temps CPU dans les APIS de fread(), etc.)
 
Et comme le dit el muchacho, pre-stocker les positions de début de chaque ligne, c'est franchement pas con (pas dans une hash-map: plutôt un simple tableau linéaire qui te donne l'offset (l'équivalent de ftell() ) de chaque début de ligne, ou même de chaque ligne paire, ou chaque ligne sur 5, etc. Après, avec une recherche dichotomique de base, tu as tout ce que tu veux (où un indexage direct si le temps est représenté de façon linéaire dans ton fichier)...
 
De longues explications Sous Windows : http://msdn.microsoft.com/library/ [...] namemo.asp

moi déjà, je stockerais le fichier sous format binaire, parce que sinon, ça sert à rien de mmaper : faudra à chaque fois faire des conversion. la conversion en format binaire peut être faite dans un fichier temporaire qui sera ensuite chargé en mémoire. avec un format binaire, tu as aussi l'avantage que tes enregistrement sont de taille fixe : plus de problème d'indexage.

 
Ah oui, c'est connissime.

je vais étudier la question à vos lumières... la suite au prochain épisode !

ouais enfin surtout ma proposition sur laquelle on s'accorde

j en ai fait des file mapping sous win en fait ca revient au meme que de charger le fic en memoire ca bouffe autant de meme
ton pb ca me fait penser au moteur de bd multidimensionnel ils utilisent la compression pour gerer des tablo gigantesk ca reste plu rapide de decompresser a la volée que d acceder au disque

je sais pas comment ça fonctionne le mmap de windows, mais sous  GNU/Linux ça fonctionne à merveille et c'est super efficace

 
euh sous windows aussi

pour des raisons indépendantes de ma volonté   je code sous visual c++ un prog sensé tourner sous unix.
 
les fonctions de mmap sous windows ne me semblent pas franchement portables, et ça va être dur d'utiliser la version native sous unix de mmap, puisque je compile sous windows. connaissez vous des librairies portables (ou tout du moins adaptables sans trop de pb) qui m'aiderait à créer mes mmap maison ?
 
en tout les cas merci de votre aide.

glup. finalement je crois que je vais devoir essayer autre chose (hypothèse : lire mon fichier par blocs...) depuis que je suis tombé sur cette citation de Bjarne Stroustrup :  
 
"There are things you just can't do in a machine-independent way,
 
 specialized instructions (e.g. vector operations,
 I/O instructions, memory mapping instructions)"
 
Merci de votre aide, je vous tiens au courant.
 
La suite au prochain épisode...

et si tu utilisé un B-arbre ?

ça va bouffer de la RAM niveau structure ...

 
On développe des librairies qui tournent indépendamment
sous Win9x/winNt/win2k/winXp, les différences entre les systemes sont cachées par des #ifdef. Le grand jeu est evidemment de designer le truc pour que le plus de code soit partagé (et limiter les #ifdef aux parties critiques).