Format de stockage d'une grosse matrice

Format de stockage d'une grosse matrice - PHP - Programmation

Marsh Posté le 19-09-2007 à 11:46:26    

Je fais du calcul matriciel sur une grosse matrice en PHP : une SVD (Singular value décomposition -> valeurs propres et vecteurs propres). Une fois que j'ai ma SVD, quelle est la forme de stockage la plus appropriée pour stocker mes matrices U, Sigma et V? Dans des fichiers csv (environ 200 Mo par fichier :() qui seront lus par php lorsqu'un de mes scripts en aura besoin ou dans des tables mysql?


Message édité par rufo le 19-09-2007 à 16:07:12
Reply

Marsh Posté le 19-09-2007 à 11:46:26   

Reply

Marsh Posté le 19-09-2007 à 11:53:00    

une fois généré ces SVD sont elles accessibles:

  • uniquement en lecture?
  • en lecture/ecriture?


Lors d'un accès en lecture, sera-ce l'intégralité des elements  qui devront être lus et utilisés, ou uniquement une "portion" de ceux-ci?

Reply

Marsh Posté le 19-09-2007 à 13:29:36    

Si tu souhaites effectuer des calculs dessus, il vaut mieux les laisser stockées en base, parce que la lecture d'un fichier de 200 Mo ça va vraiment prendre du temps.
 
Par contre je ne connais pas le nombre de champs maximums qu'une table peut contenir...


---------------
Directeur Technique (CTO)
Reply

Marsh Posté le 19-09-2007 à 15:06:46    

La SVD va être accessible uniquement en lecture et a priori, je ne vais utiliser que les k premiers valeurs et vecteurs propres (sur 2500, je pense en prendre entre 500 et 1000, les tests devraient me permettre de trouver une bonne valeur de k).
Pour le nb de champ, effectivement, c'est à voir. Autant en nb de lignes, c'est plusieurs millions, autant le nb de champs :??: Je vais regarder la doc de mysql.

Reply

Marsh Posté le 19-09-2007 à 15:47:28    

Bon, ben je viens de regarder ça pour le nb de champs max dans une table : http://dev.mysql.com/doc/refman/5. [...] ngine.html
Pour MyIsam, j'ai pas réussi à trouver mais pour InnoDB, c'est 1000
http://dev.mysql.com/doc/refman/5. [...] tions.html
Comme InnoDB est plu récent que MyIsam, j'en déduis que ça sera pas plus pour lui (c'est ce que j'utilise comme format pour mes tables).
Donc, je ne pourrai pas stocker ma matrice telle quelle dans une table :(

Reply

Marsh Posté le 19-09-2007 à 17:54:50    

Juste une remarque à deux balles...
 
Tu peux aussi écrire ta matrice sous forme binaire dans un fichier.
 
Par exemple, t'as une matrice de dimensions m, n, o, p
Tes nombres sont des int32
 
Tu copies séquentiellement au format binaire tous tes éléments de ta matrice en parcourant récursivement chaque dimension.
 
Lorsque t'as besoin de lire le nombre dans ta matrice qui se trouve à l'indice 12,3,27,96 t'as juste à faire :
 
(pseudo code)
 
open_file();
seek(4 * (12 x n x m x o + 3 x m x o + 27 x o + 96));
read(4);
 
=> Ainsi tu ne perds pas de temps à lire pour rien quoi que ce soit dans le fichier. Pour lire un simple enregistrement, c'est bien pratique. Pour charger de gros blocs tu perds un peu d'intérêt. Dans tous les cas, ce sera plus rapide qu'un SGBD (s'il s'agit de lire aveuglément des nombres à un indice donné, sans autre critère)
 
Ensuite une base de donnée est la solution qui apporte le meilleur ration simplicité/rapidité (tandis que le CSV est certainement le pire ;))

Reply

Marsh Posté le 20-09-2007 à 08:52:52    

Je vais creuser l'idée, par contre, ma matrice n'a que 2 dimensions.
 
Par contre, sur quel plan le csv est le pire? Parce que c'est facile à parser donc pour passer du csv à un array en php, c'est très facile alors que ça me paraît plus dur avec un fichier binaire.

Message cité 1 fois
Message édité par rufo le 20-09-2007 à 08:54:07
Reply

Marsh Posté le 20-09-2007 à 09:08:22    

MagicBuzz a écrit :

Ensuite une base de donnée est la solution qui apporte le meilleur ration simplicité/rapidité (tandis que le CSV est certainement le pire ;))


Pas d'accord :o ça dépend de trop de facteurs pour pouvoir affirmer ça.
D'après ce que je comprends, on a un nombre de colonnes non fixe, et l'essentiel des requêtes seront des opérations aritmétiques "réunissant" plusieurs colonnes ( mais jamais les mêmes).
=> ça va être bien compliqué des créer des indexs corrects qui optimisent vraiment l'execution des requêtes et vu qu'il semble y avoir "plusieurs millions" de lignes, ça peut vite devenir sympa.
D'autant que ces indexs devront se faire sur l'intégralité des vecteurs, alors que seul un nombre k d'entre eux est pertinent.

 

En contre partie, il faut reconnaitre que le temps de lire le fichier ( quelque soit son format), risque de plomber les perfs de la solution csv.
Mais si le nombre de vecteurs est limité à 500/1000, la problèmatique n'est plus la même car seules les 500/1000 premières lignes du fichier devront être lues.

 

Pour moi y'a pas trente six solutions, faut mettre en place les deux solutions et faire un petit benchmark.
Mais perso, à l'intuition, j'aurais tendance à dire que la solution du fichier me parait plus adaptée.

 


edit: orthographe du matin, chagrin :o

Message cité 1 fois
Message édité par anapajari le 20-09-2007 à 09:09:59
Reply

Marsh Posté le 20-09-2007 à 09:18:23    

"un nombre de colonnes non fixe" => ce nombre est quand même borné (dans mon ex, il vaut 2500), par contre, comme tu l'as bien compris, je ne vais réellement en utiliser qu'une partie. Du reste, une fois mon nombre k déterminé, pour alléger le fichier, je peux très bien ne conserver que les vecteurs (colonnes) pertinents.
 
Cela dit, je pensais à une solution toute bête si on part sur un fichier : c'est faire un fichier php direct :
<?php
MatU = array(
                   array(.....),
                   array(....),
                   ...
                  );
 
MatV = array(
                   array(.....),
                   array(....),
                   ...
                  );
...
?>
 
Et quand j'en ai besoin, j'ai plus qu'à faire un include() ;) Ca m'économise l'opération de lecture et de conversion en variable php...

Reply

Marsh Posté le 20-09-2007 à 09:45:07    

si tu n'as besoin que d'un nombre fini et determiné de données et que le reste des données est "non pertinent" ( et donc inutile des les conserver), ça ira plus vite avec une DB qu'avec un fichier :o


Message édité par anapajari le 20-09-2007 à 09:45:25
Reply

Marsh Posté le 20-09-2007 à 09:45:07   

Reply

Marsh Posté le 20-09-2007 à 09:53:48    

certes mais les tables de mysql n'acceptent pas plus de 1000 colonnes :( Donc ça veut dire qu'il faut que je sérialise pour mettre dans des blob.
D'où mon interrogation, quelle est la solution la plus rapide :
1) stocker sous forme sérialisée mes matrices dans une bd + effectuer requête sql + lire résultat + désérialiser + convertir en variable php
2) stocker mes matrices dans des fichiers php sous la forme de variable php déjà prêtes à l'emploi
Perso, je pencherais pour la 2ième solution.

Reply

Marsh Posté le 20-09-2007 à 09:55:56    

rufo a écrit :

Je vais creuser l'idée, par contre, ma matrice n'a que 2 dimensions.
 
Par contre, sur quel plan le csv est le pire? Parce que c'est facile à parser donc pour passer du csv à un array en php, c'est très facile alors que ça me paraît plus dur avec un fichier binaire.


Ben le parsing justement...
Ca t'oblige à :
1/ Lire un fichier texte, par blocs sans rapport avec les données du fichier : impossible d'accéder directement à une ligne donnée ou une valeur donnée sans lire tout les blocs précédent celui à atteindre. Pour un fichier de 200 Mo c'est problématique.
2/ Le parsing, c'est des traîtements lourds en mémoire, car dans le cas du CSV, cela implique :
a) la manipulation de chaînes de caractères (cauchemare)
b) la manipulation de multiples tableaux en mémoire (qui dit mieux ?)
c) et tout bêtement convertir des chaînes de caractères en entier, ce qui est une perte de temps
3/ Si à un moment tu dois modifier une valeur à un endroit précis du fichier, tu dois réécrire l'intégralité de la suite du fichier (idem 1 donc)

Reply

Marsh Posté le 20-09-2007 à 10:00:21    

anapajari a écrit :


Pas d'accord :o ça dépend de trop de facteurs pour pouvoir affirmer ça.
D'après ce que je comprends, on a un nombre de colonnes non fixe, et l'essentiel des requêtes seront des opérations aritmétiques "réunissant" plusieurs colonnes ( mais jamais les mêmes).
=> ça va être bien compliqué des créer des indexs corrects qui optimisent vraiment l'execution des requêtes et vu qu'il semble y avoir "plusieurs millions" de lignes, ça peut vite devenir sympa.
D'autant que ces indexs devront se faire sur l'intégralité des vecteurs, alors que seul un nombre k d'entre eux est pertinent.
[/quote]
Oublie une répreséentation en colonne. Il a 2500 colonnes, donc ça nécessite impérativement une représentation sous forme de lignes. Dans un de ses autres topics autour du sujet je lui ai suggéré une structure pour stocker ça sous forme de 3 colonnes de façon performante (identifiant du document (première dimention), indice dans la seconde dimension, et valeur.
 
[quotemsg=1613293,8,80309]
En contre partie, il faut reconnaitre que le temps de lire le fichier ( quelque soit son format), risque de plomber les perfs de la solution csv.  
Mais si le nombre de vecteurs est limité à 500/1000, la problèmatique n'est plus la même car seules les 500/1000 premières lignes du fichier devront être lues.
 
Pour moi y'a pas trente six solutions, faut mettre en place les deux solutions et faire un petit benchmark.
Mais perso, à l'intuition, j'aurais tendance à dire que la solution du fichier me parait plus adaptée.


pour moi le CSV n'est clairement pas viable, surtout s'il doit en faire une utilisation relativement intensive par la suite. la solution du fichier binaire sera la plus rapide, mais nécessite bien plus de travail (d'où ma notion de rapport rapidité/simplicité). le sgbd reste une bonne alternative, mais demande de bien mettre à plat les besoins.
rufo n'a pas l'air très familier avec les sgbd, et j'ai un peu de mal à lui faire exprimer son dictionnaire des données.
 
enfin dans tous les cas, le CSV est à éviter.

Reply

Marsh Posté le 20-09-2007 à 10:03:37    

rufo a écrit :

certes mais les tables de mysql n'acceptent pas plus de 1000 colonnes :( Donc ça veut dire qu'il faut que je sérialise pour mettre dans des blob.
D'où mon interrogation, quelle est la solution la plus rapide :
1) stocker sous forme sérialisée mes matrices dans une bd + effectuer requête sql + lire résultat + désérialiser + convertir en variable php
2) stocker mes matrices dans des fichiers php sous la forme de variable php déjà prêtes à l'emploi
Perso, je pencherais pour la 2ième solution.


1) Oui, à condition que tu soit sûr de ne jamais avoir besoin de faire des requête du genre "je cherche toutes les matrices où la valeur [a,b] est > à une valeur donnée" => stocker "proprement" dans la base te permettra d'obtenir de meilleurs perfs pour ce genre de recherches que tout ce que tu pourras imaginer en code (surtout en PHP)
2) c'est encore pire que le CSV

Reply

Marsh Posté le 20-09-2007 à 10:20:00    

Pour rappel, j'ai pas besoin de modifier mes matrices, elles sont juste en lecture seule.
J'ai juste besoin de pouvoir les lire rapidement en vue d'effectuer qq calculs matriciels en php. Je n'ai donc pas besoin d'effectuer des requêtes sql sur ces matrices.
Il ne faut pas non plus perdre de vue que ce sont de grosses matrices (>= 2500*2500) donc pas possible de les stocker directement sous la forme lignes*colonnes dans une table (avec une ligne dans al table = une ligne de la matrice et un champ dans la table = 1 colonne dans la matrice) à cause des limitations de Mysql.
 
C'est pour ça qu'un include d'un fichier php me paraît plus simple et plus rapide vu que l'interpréteur php est codé en c/c++, je pense qu'il ira plus vite qu'un script php qui va manipuler la bd pour extraire les matrices.
 
Mais j'essaierai de faire un bench pour comparer. Par contre, c'est clair, je laisse tomber le csv. :D
 
MagicBuzz, tu t'y prendrais comment pour stocker 3 matrices de 2500*2500?  
1) Une table avec 2 champs (1 ID et un blob) et 3 lignes (1 ligne par matrice)
2) 3 tables, 1 par matrice, avec 2 champs (1 ID et un blob) et 2500 lignes, 1 ligne = 1 colonne de la matrice (ben oui, comme je veux récupérer des vecteurs, c'est plus pratique d'inverser lignes et colonnes, je pense)
3) autre solution?
 
ps : MagicBuzz, même si j'utilise que peu des fonctionnalités de mysql, ça fait quand même 4 ans que je bosse dessus ;)


Message édité par rufo le 20-09-2007 à 10:21:35
Reply

Marsh Posté le 20-09-2007 à 10:35:20    

3) tout dans la même table avec un champ supplémentaire permettant d'identifier la matrice parmi les 3
 
aucune solution n'est vraiment meilleure par rapport aux autres. chacune a ses avantages et inconvénients. d'après ton besoin, si tu es sûr que le moteur sql ne sera pas exploité pour manipuler/filtrer les données des matrices, alors la première solution devrait offrir les meilleurs performances. quoi que je verrais plutôt la structure suivante : [doc_id, matrice1_blob, matrice2_blob, matrice3_blob] (tant qu'à faire...)

Reply

Marsh Posté le 20-09-2007 à 10:37:18    

attention quand même au blobds. vérifie que pdo permet de manipuler de blobs volumineux.
 
avec ado par exemple, c'est la tannée : obligé de passer par un stream, impossible de passer directement les données en paramètre à la requête. (et à la base, c'est pas vraiment une limitation d'ADO mais des différents SGBD qui n'acceptent pas des requêtes SQL trop grosses)

Reply

Marsh Posté le 20-09-2007 à 10:58:06    

MagicBuzz a écrit :

3) tout dans la même table avec un champ supplémentaire permettant d'identifier la matrice parmi les 3
 
aucune solution n'est vraiment meilleure par rapport aux autres. chacune a ses avantages et inconvénients. d'après ton besoin, si tu es sûr que le moteur sql ne sera pas exploité pour manipuler/filtrer les données des matrices, alors la première solution devrait offrir les meilleurs performances. quoi que je verrais plutôt la structure suivante : [doc_id, matrice1_blob, matrice2_blob, matrice3_blob] (tant qu'à faire...)


 
attention, tu t'embrouilles avec mon autre topic : là, ces 3 matrices ne sont pas liées à un document. :D
Perso, pour la solution à base de mysql, je pensais plutôt faire une ligne par colonne de matrice : ça permet plus de souplesse et pouvoir ramener des colonnes bien précises (et pas tout le paquet cadeau :lol:)

Reply

Marsh Posté le 20-09-2007 à 11:15:48    

ça empêche pas que tu peux différencier tes matrices en rajoutant un champs supplémentaire :)
 
en gros :
 
t'as trois matrices, tab1[x][y], tab2[x][y], tab3[x][y]
 
ça peut aussi bien se représenter par :
tab[3][x][y]
=> donc deux champs qui indiquent les indices des nombres dans la matrice, puis un champ qui indique de quelle matrice il s'agit

Reply

Marsh Posté le 20-09-2007 à 11:25:22    

doc_id, je l'avais pris pour document_id. En fait, tu voulais dire mat_id ;)

Reply

Marsh Posté le 20-09-2007 à 11:27:40    

ah oui, c'est juste du nommage de champ ;)
enfin, l'important c'est que la représentation des données dans la table est totalement indépendante du rôle des données. en clair, c'est pas parcequ'un terme est mauvais que le modèle est mauvais. et c'est pas parcequ'une table sert "à priori" à stocker certaines informations qu'elle ne peut pas aussi gérer des infos de même structure

Reply

Marsh Posté le 20-09-2007 à 11:30:10    

tout à fait, mais pour la lisibilité, la compréhension et la maintenabilité, appelons un chat, un chat :D

Reply

Marsh Posté le 20-09-2007 à 11:31:26    

exactement :
 
champ1, champ2, champ3... :D

Reply

Marsh Posté le 20-09-2007 à 11:34:01    

sans oublier "champ." (shampooing :D)

Reply

Marsh Posté le 20-09-2007 à 11:41:50    

Ces matrices elles sont à combien de dimensions? Et en plus de la position, c'est quoi les autres données qui caractérisent chaque "point"?
Je demande par ce que si c'est des matrices à deux dimensions alors tu peux faire une colonne de type "point" (ou équivalent) pour stocker les coordonnées vu que de plus en plus de bases de données se munissent de système de gestion de "données spaciales" (dans le sens cartographique et non pas volumétrique) comprenant un type de colonne adapté au stockage de coordonné et une série de fonctions mathématique permettant de manipuler ces coordonnées (par exemple pour trouver la distance entre deux points) Pour les autres données, il t'es surement possible de t'en sortir avec les autres types de colonnes.
 
J'espères que ces infos vont t'aider bien que je n'arrive pas à cerner tes besoins réels.

Reply

Marsh Posté le 20-09-2007 à 11:47:54    

Ce sont des matrices à 2 dimensions. Mysql ne dispose pas du type "point" mais si j'ai compris ce qui tu proposais, c'est de faire un table par matrice (histoire de pas voir 1 seule table trop grosse) avec la structure suivante :
ID (int), CoordonneeX (int), CoordonneeY (int), valeur (float)
 
C'est bien ça l'idée? Si oui, je pense que ça rejoint l'idée de MagicBuzz.

Message cité 1 fois
Message édité par rufo le 20-09-2007 à 11:48:35
Reply

Marsh Posté le 20-09-2007 à 12:08:05    

Jettes un oeuil ici pour l'ensemble de la doc sur le sujet : http://dev.mysql.com/doc/refman/5. [...] sions.html
 
Un exemple de création de colonne de type POINT : http://dev.mysql.com/doc/refman/5. [...] lumns.html
 
Personnellement, je n'ai jamais utilisé toute cette partie de la doc vu que je n'en ai jamais eu besoin mais vu que la première implémentation date de mysql 4.1, ça doit bien fonctionner en 5.x .
 
PS : Je ne sais pas si ça fonctionne avec autre chose que des tables en myisam.


Message édité par omega2 le 20-09-2007 à 12:09:23
Reply

Marsh Posté le 20-09-2007 à 13:34:38    

rufo a écrit :

Ce sont des matrices à 2 dimensions. Mysql ne dispose pas du type "point" mais si j'ai compris ce qui tu proposais, c'est de faire un table par matrice (histoire de pas voir 1 seule table trop grosse) avec la structure suivante :
ID (int), CoordonneeX (int), CoordonneeY (int), valeur (float)
 
C'est bien ça l'idée? Si oui, je pense que ça rejoint l'idée de MagicBuzz.


 
ID (int, clé primaire), CoordonneeX (int), CoordonneeY (int), valeur (float), Matrice (int, clé étrangère)
 
C'est pas con comme idée !  :lol:  


---------------
Directeur Technique (CTO)
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed