[Fichiers] Lire une ligne spécifique dans un (gros) csv

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonjour,

j'ai un fichier de paramètres dépendant du temps pour un programme qui est sous format CSV.
Ce fichier se présente sous la forme suivante:

Colonnes:
la variable temporelle en colonne. Il ya 480 mois (40 ans) => 480 colonnes

Lignes:
PLus de 1000 lignes. Chacune de ces lignes correspond à une simulation bien précise. Ces lignes sont ordonnées (plus petite simul vers la plus grande)
La première colonne reprend le numéro de la simulation.

J'aimerais faire qqch du style:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int lastSimulation = 1000; for (int i = 1; i<= lastSimulation; i++){ std::ifstream fichier( "fichier.txt" ); if ( fichier ) { std::string ligne; while ( std::getline( fichier, ligne ) ) { if( on est sur la ligne correspondant au compteur i) doSomething(); } } }
Le code (que j'ai retapé de mémoire ) fonctionne, mais le problème est que si le n° de simulation est dans le début du fichier, j'arrive à la fonction doSomething() (forcément) assez vite, par contre si la simulation est très loin dans le fichier, ca prend bcp de temps (une seconde contre qqs millisecondes).
Le temps étant très important pour moi, avez vous une idée pour acceder à une ligne particulière plus rapidement?

Merci bcp
David

23/06/2008, 21h44
ram-0000

Je ne sais pas si c'est possible mais si les lignes font toutes la même longueur, tu pourrais utiliser fseek (ou équivalent) afin de te positionner directement dans le fichier sur la ligne à lire. Par contre, attention si une seule ligne ne respecte pas le format !!!

Si le critère de temps de positionnement est vraiment important, tu pourrais même imposer une taille fixe pour tes lignes.

C'est le seul moyen que je voie pour optimiser le temps d'accès à une ligne particulière.
23/06/2008, 22h39
dhoorens

En fait toutes les colonnes contiennent des chiffres (hormis la première qui indique le n0 de la simulation (c'est aussi un chiffre :-) ).
Ces chiffres sont du style 0.0457568 mais avec parfois moins ou plus de décimales... Et il n'est pas possible de restreindre la taille pcq c'est un autre programme (un générateur de scénarios économiques) qui me fournit cet input sous format csv.

A) D'un coté:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 std::ifstream fichier( "fichier.txt" ); if ( fichier ) { std::string ligne; int i = 0; while ( std::getline( fichier, ligne ) && (i++<lastSimulation) ) { if( on est sur la ligne correspondant au compteur i) //Renverra toujours vrai doSomething(); } }
ça ne sert à rien de double boucler!

B) Sinon tu peux pas tous passer en memoire?

Si A et B ne conviennents pas:

C) Algorithme recursif en complexité log2:

Citation:

fonction chercher_log2(int commencerOu)

fseek(commencerOu)

lire jusqu'au prochain caractere "\n" (saut de ligne, ou fin de fichier)

if( on est sur une ligne inferieur au compteur i)
alors
-> chercher_log2(commencerOu + commencerOu/2)
sinon
if(on est sur une ligne egale au compteur i)
retourner ligne ou flux ou directement la structure etc...
sinon
-> chercher_log2(commencerOu - commencerOu/2)
fin if
fin if

Cela marche uniquement si toute tes structures sont dans un ordre triée

24/06/2008, 10h31
koala01
Salut,

Peut-être - étant donné que tu as un nombre de colonnes connues - serait-il intéressant d'envisager un simili fichier ISAM (le I étant pour "indexed" ;)) :question:

Dans un fichier à part, tu indiques les offsets de chaque début de ligne, et tu charges ces offset dans un tableau en début de programme.

Quand tu dois accéder à un élément X, tu calcule pos = X / nombre_colonnes à l'arrondi inférieur, et tu récupères l'offset en tab_offset[pos].

Cet offset te permet (à l'aide de fseek) de sauter directement au début de ligne qui t'intéresse, et tu n'a plus au maximum qu'à lire la totalité des colonnes de cette ligne :D

Nous ne sommes pas encore en O(log(n)), cela te permet de garder un temps "presque constant" :D (constant pour aller chercher la ligne, en O(N) pour aller chercher la colonne)

Pour obtenir l'index, l'idéal serait de modifier l'application qui crée ton fichier CSV de manière à ce qu'elle crée l'index, mais, sinon:
1. tu peux créer une petite application qui s'en charge (ca doit pas faire beaucoup plus de 5 lignes :D)
2. Tu peux lire une fois le fichier au lancement de ton application, et créer l'index "à la volée" :D (ici aussi, cela ne fait pas beaucoup plus de 5 lignes :D)
Cependant, ces deux dernières solutions seront plus lentes que la solution idéale :D

[EDIT]Il est aussi possible de prévoir un index d'offset toutes les X données (ou X peut varier à ton gré de 1 - qui n'est pas vraiment intéressant au vu de la taille du tableau qu'il implique - à autant que tu veux :D )
24/06/2008, 14h19
dhoorens

Mais il ya une sorte d'index, puisque la première colonne contient le n° de la simulation..

On a qqch du style:
Simul ; 0 ; 1 ; 2 ; 3 ;......
1; 0.045 ; 0.0645; 0.0368; 0.12 ;....
2; 0.0756; 0.0752; 0.0953; 0.564 ;....
3; 0.065 ; 0.0123; 0.0321; 0.8525;....
......

Est ce que je peux l'utiliser astucieusement?
24/06/2008, 15h34
Sylvain Togni

Si les lignes sont numérotées alors un algorithme de dichotomie permettra d'accélérer l'accès (O(log n) contre O(n)).
24/06/2008, 15h48
dhoorens

Citation:

Envoyé par Sylvain Togni

Si les lignes sont numérotées alors un algorithme de dichotomie permettra d'accélérer l'accès (O(log n) contre O(n)).

gnééé??
24/06/2008, 15h54
ram-0000

Citation:

Envoyé par Sylvain Togni

Si les lignes sont numérotées alors un algorithme de dichotomie permettra d'accélérer l'accès (O(log n) contre O(n)).

Non car de toute façon, il faudra lire toutes les lignes entre la position courante et la position suivante et éventuellement lire aussi en arrière.

Ce que tu pourrais faire, c'est de créer un index genre :
la ligne 1 commence à l'offset 0
la ligne 2 commence à l'offset 37
la ligne 3 commence à l'offset 151
...

A partir de là, dès que le gros fichier CSV est modifié, reconstruction de l'index (enfin pseudo index)

ensuite, tu veux aller à la ligne 3252, tu lit la valeur de l'offset de la ligne 32 dans l'index (là c'est un accès direct puisque tu t'arranges à ce que tes index fassent tous la même taille). Ensuite tu ouvres ton gros fichier et tu va directement à la bonne ligne

Mon idée @ 0,01€
24/06/2008, 17h26
koala01

Effectivement... le principe ISAM est bel et bien celui que ram_000 a expliqué autrement.

Pour peu que le pas des index soit "suffisemment petit", tu obtiendra un résultat dans un délais des plus raisonnables ;)
08/07/2008, 15h07
dhoorens
Citation:
Envoyé par koala01

Salut,

Peut-être - étant donné que tu as un nombre de colonnes connues - serait-il intéressant d'envisager un simili fichier ISAM (le I étant pour "indexed" ;)) :question:

Dans un fichier à part, tu indiques les offsets de chaque début de ligne, et tu charges ces offset dans un tableau en début de programme.

Quand tu dois accéder à un élément X, tu calcule pos = X / nombre_colonnes à l'arrondi inférieur, et tu récupères l'offset en tab_offset[pos].

Cet offset te permet (à l'aide de fseek) de sauter directement au début de ligne qui t'intéresse, et tu n'a plus au maximum qu'à lire la totalité des colonnes de cette ligne :D

Nous ne sommes pas encore en O(log(n)), cela te permet de garder un temps "presque constant" :D (constant pour aller chercher la ligne, en O(N) pour aller chercher la colonne)

Pour obtenir l'index, l'idéal serait de modifier l'application qui crée ton fichier CSV de manière à ce qu'elle crée l'index, mais, sinon:
tu peux créer une petite application qui s'en charge (ca doit pas faire beaucoup plus de 5 lignes :D)
Tu peux lire une fois le fichier au lancement de ton application, et créer l'index "à la volée" :D (ici aussi, cela ne fait pas beaucoup plus de 5 lignes :D)
Cependant, ces deux dernières solutions seront plus lentes que la solution idéale :D

[EDIT]Il est aussi possible de prévoir un index d'offset toutes les X données (ou X peut varier à ton gré de 1 - qui n'est pas vraiment intéressant au vu de la taille du tableau qu'il implique - à autant que tu veux :D )
Bonjour
J'ai essayé cette solution, càd que je crée un petit fichier txt qui indique à chaque ligne l'offset correspondant à la longueur de la ligne correspondante dans mon fichier de base.

Ensuite, lorsque j'ai besoin d'une ligne en particulier, j'ouvre mes deux fichiers (le gros et le petit) et je recupère dans le petit l'offset correspondant à ma simulation et je me déplace à l'aide de fseek dans le gros fichier jusque l'offset et je récupère ma ligne.
Tout fonctionne bien, sauf qu'au niveau du temps c'est pas top.

Lorsque je fais tourner mon programme sur les 100 premieres simulations , ça prend 1 minute (c'est le temps que dure mon programme => il faut prendre le temps relatif)
Lorsque je fais tourner mon programme sur les 100 premieres simulations , ca prend 5 minutes

=> j'ai (en gros) un rapport X5 entre le fait d'accèder aux premières lignes et les dernières lignes...

C'est un peu genant car je voudrais réduire le temps de calcul considérablement...:-/

Si vous avez une idée...
Merci

Attention, l'idée est de placer les offsets qui servent d'index dans un tableau dés le début du programme, et de n'effectuer la lecture de cet index que... s'il y a eu changement d'index entre la première lecture du fichier et la tentative d'obtention de l'index...

Ainsi, tu pourrais envisager quelque chose sous la forme de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* une classe servant à l'indexation */
class Index
{
    public:
       /* le constructeur fournit le nom du fichier index "en dur"... mais on 
        * pourrait envisager de fournir ce nom dans le constructeur ;)
        *
        * La lecture de l'index se fait une bonne fois pour toutes à 
        * l'initialisation de l'application (directement dans le constructeur
        * de la classe
        */
       Index()
       {
           std::ifstream ifs("fichier.ind");
           /*Si l'ouverture du fichier index échoue, on quitte l'application 
            * FileNotFound est une classe à créer en vue de s'en servir comme
            * d'une exception
            */
           if(!ifs)
               throw FileNotFound();
           size_t ind;
           /* Tant que l'on sait lire un offset, on l'insere dans le tableau 
            */
           while( ifs>>ind)
               tab.push_back(ind);
       }
       ~Index(){}
        size_t offsetFor(size_t pos) const
        {
            /* renvoie l'offset correspondant à l'index calculé sur base
             * de la position recherchée divisée par le pas
             *
             * lance une exception de type std::out_of_range si la division
             * fournit un indice hors des limites
             */
            return  tab.at(pos / step);
        }
        static size_t getStep(){return step;}
    private:
        /* le membre step correspond au "pas" qui sépare deux index...
         * Il s'agit de choisir un pas "suffisemment grand" pour ne pas
         * "crouler" sous les indexes, mais "suffisemment" petit pour que la
         * boucle ne doive pas être effectuée *trop* souvent
         */
        static const size_t step;
        /* et bien sur, il nous faut un tableau en vue de maintenir les 
         * offsets ;)
         */
        std::vector<size_t> tab;
}; 
/* dans un et un seul fichier d'implémentation */
const size_t Index::step = 100;// valeur choisie arbitrairement... à adapter à 
                               // tes besoins ;)

Et il y a une classe qui va prendre la lecture des informations qui te sont nécessaires... tu travaillera donc sous une forme proche de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
class Reader
{
    public:
        Reader(){}
        ~Reader(){}
         /* la fonction de lecture des informations
          * @ in : le numéro de la simulation à lire
          *       une référence constante sur la classe Index
          * @ out : l'élélement du type lu qui va bien
          */
        static LeTypeQuiVaBien read(size_t pos, const Index& ind)
        {
            std::ifstream ifs(fname.c_tr());
            /* récupération de l'offset vers lequel aller */
            size_t offset = ind.offsetFor(pos);
            /* pour terminer les calculs une fois pour toutes, calculons
             * le nombre d'éléments que nous devrons lire avant d'obtenir 
             * celui qui nous intéresse
             */
            size_t topass = pos % ind.getStep();
            /*sautons à l'offset que nous avons déterminé 
             */
             ifs.seekg(offset);
            /* nous bouclons lisons en boucle les éléments que nous devons 
             * passer (j'ai choisi de croire qu'il y a une surcharge de 
             * l'operateur >> par facilité :P )
             */
            for(size_t i= 0; i<=topass;++i)
            {
                /* Comme nous allons lire ces données sans rien en faire,
                 * autant les récupérer dans un objet qui sera détruit à
                 * chaque fois ;)
                 */
                LeTypeQuiVaBien temp;
                ifs>>temp;
            }
            /* il ne nous reste plus qu'à lire les informations qui nous
             * intéressent et à les renvoyer ;)
             */
            LeTypeQuiVaBien final;
            ifs>>final;
            return final;
        }
    private:
        static const std::string fname;
};
/*et dans un et un seul fichier d'implémentation 
 * (adaptations possibles ) 
 */
const std::string Reader::fname="tonfichier.dat";

Au final, ta fonction principale pourrait ressembler à

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int main(int argc, char* argv[])
{
    /* on commence par récupérer les numéros des simulations qui nous
     * intéressent dans... un tableau d'entiers ;)
     */
    std::vector<size_t> tab;
    if(argc==1)
    {
        std::cout<<"veuillez indiquer au minimum un numéro de simulation";
        return 1;
    }
    for(int i = 1;i<argc;++i)
    {
        std::stringstream ss;
        ss<<argv[i];
        size_t read;
        /*pour le cas où  l'argument passé ne serait pas une valeur entière */
        if(!ss>>read)
        {
            std::cout<<"veuillez n'introduire que des valeurs entieres,"
                     <<" separees par un espace";
            return 1;
         }
         tab.puh_back(read);
    }
    /* nous lisons maintenant notre index */
    Index ind ;
    /* et nous effectuons notre travail sur les simulations qui nous 
     *intéressent
     */
    for(size_t i = 0 ; i<tab.size(); ++i)
    {
        LeTypeQuiVaBien simulation  = Reader::read(tab[i],ind);
        /* tout le travail qui doit être effectué */
    }
    std::cout<<"Merci de votre patience et bonne journee";
    return 0;
}

et l'application serait appelée sous une forme proche de

Citation:

MonApp.exe 10 1523482 1114444777 36520 78 56

pour avoir le traitement pour

la simulation numéro 10
la simulation numero 1523482
la simulation numéro 1114444777
la simulation numéro 36520
la simulation numéro 78 et enfin
la simulation numéro 56

Evidemment, il y a une foule d'adaptations possibles ( telles que devoir donner le nom des fichiers dans la ligne de commande, modifier le pas d'index...) ;)

08/07/2008, 17h00
dhoorens

waw CA c'est de la réponse... ;-))

okay je vais tester et je reviens avec j'espere un bon vieux petit "résolu" ...:lol:

Merci
David

Code:

1
2
3
/* dans un et un seul fichier d'implémentation */
const size_t Index::step = 100;// valeur choisie arbitrairement... à adapter à 
                               // tes besoins ;)

Je ne vois pas comment choisir cette variable step
...
Peux tu m'expliquer à quoi elle correspond?

27/08/2008, 09h14
epsilon68

et ca donne quoi si tu mettais ce fichier dans une DB genre SQLite?
j'imagine que ca devrait etre plus rapide a developper, plus facile a maintenir, et hyper rapide a l'execution non?

tu peux poster ton fichier CSV? il fait combien de Mo (ou Go)?

je me lancerais bien dans un bench, j'ai Qt sous la main pour faire l'interface avec SQLite.
27/08/2008, 12h42
dhoorens

Citation:

Envoyé par epsilon68

et ca donne quoi si tu mettais ce fichier dans une DB genre SQLite?
j'imagine que ca devrait etre plus rapide a developper, plus facile a maintenir, et hyper rapide a l'execution non?

tu peux poster ton fichier CSV? il fait combien de Mo (ou Go)?

C'est une librairie C++?
J'aimerais incorporer tout le traitement dans une dll => si c'est possible, moi je suis pas contre
Par contre pour le fichier, il est gros mais sa structure est simple:
||Colonne1||Colonne2||Colonne3||Colonne4||…||Colonne244
Ligne1||"Trial"||"Parameter"||0||1|| ||240
Ligne2||1||"blabla longueur 20"||x||x||x||x
Ligne3||2||"blabla longueur 20"||x||x||x||x
…|| ||"blabla longueur 20"||x||x||x||x
Ligne1001||1000||"blabla longueur 20"||x||x||x||x

(copiez le dans excel avec comme délimiteur || )
avec x qui sont des nombres (forcement différents dans chaque cellule) de type double

Merci
27/08/2008, 12h43
dhoorens

ahh oui et la taille est environ de 5MB par fichier
27/08/2008, 13h18
epsilon68

5 Mo ? mais c'est tout petit !!!

mets ton fichier dans SQLite et ne travaille plus qu'avec SQLite, ca sera carrement plus efficace avec un temps de traitement constant, une maintenabilité excellente et une constante amelioration gratuite de SQLite.

http://www.sqlite.org
(SQLite est une database embarquée écrite en C.)
27/08/2008, 14h23
dhoorens

Citation:

Envoyé par epsilon68

5 Mo ? mais c'est tout petit !!!

Hélllàààà

:-)
27/08/2008, 14h27
epsilon68

il faut analyser de la facon suivante:

- tu ne peux pas garder le CSV puisque tu es bloqué par manque de performance
- il faudrait faire des index
- ca revient a une database
- on manque de temps
- on veut de la performance
- on veut se concentrer sur notre objectif principal, pas se rajouter des taches.
- SQLite !!!!!!!!!

;-)

a+

Voir 40 message(s) de cette discussion en une page