Rayons clairs dans Haskell?

Question

Existe-t-il une manière standard ou "la plus courante" de représenter des tableaux clairsemés multidimensionnels dans Haskell (sans trop sacrifier la performance)?

Quelque chose comme la carte < int, la carte int, MyClass>> en C++, par exemple. J'ai googlé et trouvé juste quelques vieux papiers académiques et d'autres personnes demandant cela aussi.

Merci!

Answer 1

Data.Map (Int,Int) MyClass est une excellente suggestion; essayez cela en premier.

Si vous rencontrez des problèmes d'espace avec cela, essayez IntMap (IntMap MyClass). IntMap s (dans le module Data.IntMap) sont Map s avec Int s comme clés; étant spécialisés, ils sont plus efficaces que les cartes génériques. Cela pourrait ou non faire une différence significative. Il y a aussi le projet Scalable, adaptive persistent container types qui pourrait vous être utile. Ces conteneurs (y compris les cartes) utilisent beaucoup moins d'espace que les cartes normales, mais ils sont légèrement plus compliqués (bien qu'ils restent relativement faciles à utiliser).

Answer 2

Je ne peux rien voir qui est libre, mais il y a ceci:

Sparse matrix representations in a functional language

et ceci:

A study of sparse matrix representations for solving linear systems in a functional language

Answer 3

Que diriez-vous d'un Data.Map (Int,Int) MyClass?

Answer 4

Il y a HsJudy, ce qui semble bien adapté aux jeux de clés clairsemés.

liaisons Judy (une bibliothèque C qui implémente des tableaux dynamiques clairsemés rapide) pour les API présentant Haskell conformes, autant que possible aux interfaces des bibliothèques existantes Haskell, comme Data.Map et Data.Array.MArray. Cette liaison pour la bibliothèque Judy inclut tous ses quatre types: la mise en correspondance de mots en bits (Judy1), de mots en valeurs (JudyL), de chaînes en valeurs (JudyHS) et de array-of-bytes en valeurs (JudyHS).

Mais j'irais probablement avec un Data.Map.Map (Int, Int) MyClass jusqu'à rencontrer des problèmes d'évolutivité ou d'utilisabilité.

Answer 5

Je trouve this short gist qui montre un stockage Row compressé pour Haskell et la multiplication matrice-vecteur associé:

import Data.Vector.Unboxed as U 

-- | A compressed row storage (CRS) sparse matrix. 
data CRS a = CRS { 
     crsValues :: Vector a 
    , colIndices :: Vector Int 
    , rowIndices :: Vector Int 
    } deriving (Show) 

multiplyMV :: CRS Double -> Vector Double -> Vector Double 
multiplyMV CRS{..} x = generate (U.length x) outer 
    where outer i = U.sum . U.map inner $ U.enumFromN start (end-start) 
      where inner j = (crsValues ! j) * (x ! (colIndices ! j)) 
       start = rowIndices ! i 
       end  = rowIndices ! (i+1) 
       (!) a b = unsafeIndex a b