2A.i - Stratégies et grandes matrices en mémoire

Links: notebook, html, PDF, python, slides, GitHub

Eléments de réflexion autour des jeux de données trop grands pour tenir en mémoire.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Introduction

Les ordinateurs portables ont en moyenne 8 Go de mémoire, les machines de bureau peuvent aller bien au-delà, monter jusqu’à 1 To de mémoire vive. 8Go suffisent pour la plupart des usages. Que faire quand cela ne suffit pas ? Chaque section propose une direction.

Echantillon aléatoire

C’est le premier réflexe. On regarde les données avec un échantillon aléatoire qui tient en mémoire et avec lequel les calculs prennent un temps raisonnable.

Changer de type numérique

Beaucoup de librairies de machine learning utilise des float et non double. La précision est moindre mais peut n’a-t-on besoin de cette précision pour les calculs. Il en va de même pour les entiers. Si on sait qu’une variable prend ses valeurs entre 0 et 255, un octet pour représenter chaque entier.

Matrice creuse ou sparse

Beaucoup de grandes matrices sont creuses : la plupart des coefficients sont nulles. Cela est souvent le cas pour les matrice d’adjacence des graphes. Dans ce cas, il est avantageux de ne stocker que les coefficients non nuls et d’utiliser les opérations matricielles adéquates de sorte que les zéros ne soient jamais présents en mémoire.

On ne stocke en mémoire que les coefficients non nuls et leurs coordonnées. C’est une façon de compresser l’information. Il existe plusieurs formats. Le plus usité est le format CSR pour Compressed sparse row. Ce n’est pas le seul. Pour une matrice symétrique, on ne mémorisera que la moitié des coefficients. Il n’existe pas de meilleur format en général mais un meilleur format adapté à un usage.

Exercice 1 : CSR et CSC

Mesurer le temps que prend une multiplication matricielle avec les trois formats dense, CSC et CSR. Il faut produire une matrice 3x3 avec des matrices carrées et non carrées, dense ou sparse…

Exercice 2 : sparse dataframe

pandas propose une version sparse des dataframes. Il suffit d’appeler la méthode to_sparse. Mesurer le gain en mémroire pour différents dataframes.

SQL

Certains calculs ne nécessitent d’avoir toutes les données en mémoire. C’est le cas d’une moyenne et typiquement de tout calcul s’appuyant sur une logique SQL ou Map/Reduce. On place les données dans une base de données SQL. On manipule les données en SQL, on ne charge en mémoire que ce qui est nécessaire.

Format compressé

Les données sont compressées pour prendre moins de place. Les calculs nécessitent alors que les matrices soient décompressés avant les calculs puis les résultats compressés. Le module h5py est couramment utilisé et souvent via un autre module qui masque le fait que les données sont compressées. blosc est un autre module de compression, voir aussi python-blosc.

  • pytables gère des bases de données enregistrées au format HDF5, fonctionne avec blosc.
  • zarr : utilise blosc pour compresser les données, propose des opérations pour créer facilement des matrices compressées.
  • wendelin.core : API pour faire des calculs matriciels sur des matrices stockées en mémoire et sur disque

Librairies dédiées

Certaines structures de données sont récurrentes et certaines librairies ont été implémentées pour les manipuler.

  • bcolz : les matrices sont souvent stockées en ligne, deux cellules consécutives sur la même ligne seront contiguës en mémoire. bcolz organise les matrices en colonnes. Deux cellules consécutives sur la même colonne seront contiguës en mémoire.
  • xarray : pour manipuler les tableaux en plusieurs dimensions, s’appuie sur numpy
  • dynd-python : aussi pour manipuler les tableaux en plusieurs dimensions mais implémenté en C++
  • cubes : toujours tableaux multidimensionnels mais stockés via une base de données
  • blist : implémente de large liste plus efficace que le type list
  • datashader : afficher rapidement des graphes actifs (javascript) avec des millions d’observations

Parallélisation

C’est une option pas toujours évidente à mettre en place car elle implique d’écrire différemment les algorithmes.

  • dask : une sorte de pandas parallélisé, ne fait pas tout ce qui propose pandas, seulement ce qui est parallélisable
  • pystorm : interface pour storm
  • rx : itérateurs parallélisés avec une syntaxe très proche de LINQ

Sérialisation

La sérialisation permet de gagner du temps lors de l’écriture et la lecture d’objet. Les objets sont enregistrés dans un format très proche de celui qu’il a en mémoire. Le chargement des données est très rapide. Pour un dataframe, le fait de sérialiser évite toutes les opérations de conversion des nombres au format numérique. Ce processus est très pratique pour les gros dataframe.

  • pickle : module faisant partie des mdoules standard de Python
  • dill : extension de pickle