Discussion :

[Christophe Genolini]

Bonjour a tous,

Je travaille dans le milieu des statistiques. Je travaille sur la base de donnée suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
|-----+-----+-------+
|Name |Age  |Gender |
|-----+-----+-------|
|Marc |32   |M      |
|Isa  |36   |F      |  
|Lea  |35   |F      |
|Lee  |31   |M      |  
|-----+-----+-------|

(en beaucoup plus gros bien sur).
Sur mon disque, elle est au format .csv. Elle est enregistrée sous forme de ligne.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

"Name","Age","Gender"\n"Marc",32,"M"\n"Isa",36,"F"\n"Lea",35,"F"\n"Lee",31,"M"\OEF

Je souhaite la stocker en mémoire sous forme de colonne.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 Marc Isa Lea Lee 32 36 35 31 M F F M

Savez-vous comment faire ca de manière efficace ? J’ai pensé à 3 méthodes :

• Première
  
  1. Lire la première ligne entièrement.
  2. Créer des vectors pour chaque colonne.
  3. Stocker les données au fur et a mesure de la lecture du fichier dans les vectors.
  4. De temps en temps, il faudra faire une recopie d’un vector, quand celui-ci est trop petit.
  
  
• Deuxième
  
  1. Lire la base intégralement une fois, pour connaitre le nombre de ligne et le nombre de colonne
  2. Créer en mémoire des tableaux de tailles adéquates.
  3. Lire ensuite la base de données une deuxième fois en remplissant les tableaux.
  
  
• Troisième
  
  1. Lire la base intégralement et la stocker en ligne.
  2. Puis faire des permutations entre les valeurs.

Laquelle serait la plus efficace ? A y-t-il une autre méthode encore plus efficace ?

Christophe

[kajtp]

Bonjour,

Etes vous obligé d'utiliser le C, ou l'utilisation du c++ est elle permise? Dans le second cas l'utilsation de la classe std::vector ou std::list pourrait etre utile et éviter les problèmes de recopie du vecteur quand celui là est trop petit (pour la solution 1). Sinon la solution me parait comporter moins de risque de plantage liée à une mauvaise allocation mémoire que la 1.

[Matt_Houston]

À moins d'utiliser une implémentation d'allocateur complexe (type slab par exemple), std::vector doit aussi recopier son contenu lors d'une réallocation. Il n'y a pas de magie.

Je pars du principe que la technologie utilisée est le C.

Christophe, qu'est-ce qui t'empêche d'utiliser une structure pour chaque entrée (stockage « entrelacé ») ? Tu as des requêtes à faire sur les différents champs ? À quel problème initial le système répond-il ?

[Christophe Genolini]

Merci pour vos réponses.

@kajtp
Je n'ai pas de contrainte, je peux utiliser le C comme le C++.

@Matt_Houston
Je vais faire des analyses statistiques. Donc je vais par exemple avoir besoin d’accéder à la colonne Age pour en calculer la moyenne, l'écart type, la variance, la médiane, les quartiles...
Juste Age parce qu'une moyenne sur les Gender, ca n'a pas de sens.

Plus tard dans mes analyses, j'aurais besoin de calculer les effectif de Gender (compter le nombre de M et de F). A ce moment, là, j'aurais besoin juste de Gender, plus de Age...

Encore plus tard, j'aurais plein de truc hyper compliqué (régression logistique, ACP, AFP, clustering...) sur une seule colonne, ou sur deux colonnes, selon les cas.

[picodev]

Bonjour,
si tu te lances en C, autant utiliser un petit sgbd pour te simplifier la vie. Sqlite pourrait très bien faire l'affaire après un import csv. Tu n'as pas besoin d'installer un serveur ou de faire de grosse configuration, il est efficace, rapide … bref à tester dans ton cas.

[kajtp]

Bonjour,

Matt_Houston a raison, "std::vector doit aussi recopier son contenu lors d'une réallocation.", sans entrer dans des considérations de l'efficacité de traitement , je voulais simplement dire que le push_back() permet de rendre "invisible" au codeur le coté réallocation (même si elle doit être faite on est bien d'accord )

Et oui une liste de structure ou la solution sqlite paraissent bonnes.

[Obsidian]

Bonjour à tous,

Christophe, c'est toujours une bonne idée de faire du traitement de données en C parce qu'on peut obtenir de très bonnes performances et qu'on peut interfacer son programme avec presque n'importe quoi ensuite, mais si ton objectif final est de faire uniquement de la statistique, peut-être serais-tu intéressé par le langage R, qui sert à ça.

Laquelle serait la plus efficace ? A y-t-il une autre méthode encore plus efficace ?

En dehors du côté algorithmique, il peut être intéressant de « mapper » le fichier en mémoire plutôt que le lire en entier (surtout s'il est gros) s'il doit au final se retrouver de toutes façons dans le swap. Le seul « problème » des CSV est que la longueur de leurs lignes n'est pas fixe, ce qui les rend difficile à indexer.

[Christophe Genolini]

Je connais bien R, j'ai même écrit un livre sur R et la cocarde qui orne mon profil fait justement référence à des tutoriaux que j'ai écris sur R.

R est un logiciel très bien pour faire de l'analyse statistique, mais coté performance, il est assez catastrophique. En terme de big data, il s’arrête a 1 giga sous Windows, une dizaine de giga sous Linux (alors que les logiciels d'informaticiens se chatouillent avec des 50 ou 10 tera). Donc, nous avons décidé de ré-écrire R (rien que ca !) mais en utilisant des techniques informatique moderne.

Donc nous allons reprogrammer nous même la gestion des données, et nous allons effectivement utiliser le C parce que c'est le plus efficace. D'ou ma question sur le "comment optimiser"...

Pour l'instant, on fait l'hypothèse que nos données tiennent en mémoire. Mais comme tu viens de le dire, les lignes CSV sont de longueurs variables. Donc accéder à la 4° colonne d'un fichier d'un million de ligne est long, surtout si le fichier est stocké sous forme de ligne.
On cherche donc a lire le fichier (sous forme de ligne car en CSV) mais le stocker en mémoire sous forme de colonne. Ainsi, tous les calculs ultérieurs seront beaucoup plus rapide.

[Obsidian]

Je connais bien R, j'ai même écrit un livre sur R et la cocarde qui orne mon profil fait justement référence à des tutoriaux que j'ai écris sur R.

En effet, toutes mes excuses alors !
C'est vrai que j'aurais pu me renseigner un peu mais sur le coup, j'ai pris ton emblème pour un avatar ! :-)

R est un logiciel très bien pour faire de l'analyse statistique, mais coté performance, il est assez catastrophique. En terme de big data, il s’arrête a 1 giga sous Windows, une dizaine de giga sous Linux (alors que les logiciels d'informaticiens se chatouillent avec des 50 ou 10 tera). Donc, nous avons décidé de ré-écrire R (rien que ca !) mais en utilisant des techniques informatique moderne.

Donc nous allons reprogrammer nous même la gestion des données, et nous allons effectivement utiliser le C parce que c'est le plus efficace. D'ou ma question sur le "comment optimiser"...

Effectivement, dans ce cas, il vaut mieux utiliser d'emblée les techniques d'allocation avancées. Comme il est certain que ce problème a déjà été fréquemment rencontré en informatique, il peut être intéressant d'utiliser des objets tout faits pour cela plutôt que passer beaucoup de temps à réinventer la roue, à condition toutefois qu'ils tiennent leurs promesses et soient vraiment adaptés à ce que tu veux faire.

Il y a quelques temps, on s'était intéressés aux allocateurs de boost en C++ et l'un d'eux (un allocateur rapide) avait pour stratégie, chaque fois qu'une page était remplie, d'en allouer une autre deux fois plus grande que la précédente. Ça se justifie effectivement quand on reste dans des quantités de données qui tiennent en mémoire, fût-elle vaste, et qu'on compte les libérer rapidement.

Et comme tu traites à la fois de très grosses quantités de données (big data) en faisant du traitement spécialisé (stats), tu auras probablement besoin à terme d'utiliser des approches heuristiques et, donc, de faire des statistiques poussées sur tes propres méta-données. Comme cela me dépasse un peu, je me garderai de donner un avis…

Pour l'instant, on fait l'hypothèse que nos données tiennent en mémoire. Mais comme tu viens de le dire, les lignes CSV sont de longueurs variables. Donc accéder à la 4° colonne d'un fichier d'un million de ligne est long, surtout si le fichier est stocké sous forme de ligne. On cherche donc a lire le fichier (sous forme de ligne car en CSV) mais le stocker en mémoire sous forme de colonne. Ainsi, tous les calculs ultérieurs seront beaucoup plus rapide.

C'est-à-dire qu'une fois en mémoire, stocker « en colonne » ou « en ligne » n'a plus vraiment de sens. Cela devient plutôt implicitement un tri de donnée : les données individuelles t'arrivent d'abord par colonne puis par ligne mais sont en fait toutes stockées consécutivement en mémoire. L'idée est plutôt de savoir à quelle fréquence tu as besoin d'accéder à chacune de tes données.

La première chose à faire, à mon avis, est de mettre en place un index sur ton fichier, c'est-à-dire un fichier pouvant être lu linéairement et qui indique à quel offset se trouve chaque ligne de ton fichier CSV, voire même chaque groupe de ligne : si tu indexes ton fichier par groupe de dix lignes, par exemple, tu divises par dix la taille de ton index et tu n'as besoin que de parcourir séquentiellement dix lignes, au plus, pour retrouver ton information.

Tu peux ensuite mettre utiliser un système de hash table pour re-classer ton index sous une forme plus adaptée, qui permet de regrouper entre elles des données qui partagent un même critère, sans que ce sous-ensemble soit forcément trié, ni que les différents sous-ensembles soient eux-mêmes ordonnés les uns par rapport aux autres.

Une bonne chose consisterait ensuite à convertir tes fichiers CSV en un format plus adapté, spécialement s'il y a beaucoup de redondance : un champ « prénom », par exemple, a quand même tout à gagner à être converti en références vers un dictionnaire qui, lui, ne contient qu'un exemplaire de chaque prénom. En ce sens, utiliser une vraie base de données permet déjà de s'affranchir d'une bonne partie du travail (par contre oublie SQLite si c'est pour travailler avec des téra-octets). Par contre, cela va introduire beaucoup d'overhead inutile (copie entre le serveur et la mémoire de ton programme) si le côté relationnel ne t'intéresse pas.