Discos dispersos en Haskell?

Question

¿Existe alguna manera estándar o "más usual" de representar arreglos dispersos multidimensionales en Haskell (sin sacrificar demasiado el rendimiento)?

Algo como mapa < int, mapa < int, MyClass>> en C++, por ejemplo. Busqué en Google y encontré solo algunos documentos académicos antiguos y otras personas pidiendo esto también.

Gracias!

Answer 1

Data.Map (Int,Int) MyClass es una excelente sugerencia; intenta eso primero.

Si tiene problemas de espacio con eso, intente IntMap (IntMap MyClass). IntMap s (en el módulo Data.IntMap) son Map s con Int s como claves; al estar especializados, son más eficientes que los mapas genéricos. Puede o no hacer una diferencia significativa.

También existe el proyecto Scalable, adaptive persistent container types que podría serle útil. Esos contenedores (incluidos los mapas) utilizan mucho menos espacio que los mapas normales, pero son un poco más complicados (aunque aún son razonablemente fáciles de usar).

Answer 2

Nada puedo ver que es gratis, pero no es lo siguiente:

Sparse matrix representations in a functional language

y esto:

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

Answer 3

¿Qué tal un Data.Map (Int,Int) MyClass?

Answer 4

Hay HsJudy, que parece estar bien adaptado para conjuntos de claves dispersas.

fijaciones Judy (una biblioteca de C que implementa matrices dinámicas rápidas dispersos) para presentar las API Haskell se ajusten lo más posible a las interfaces existentes de la biblioteca de Haskell, como Data.Map y Data.Array.MArray. Este enlace para la biblioteca Judy incluye todos sus cuatro tipos: asignación de palabras a bits (Judy1), de palabras a valores (JudyL), de cadenas a valores (JudyHS) y de matriz de bytes a valores (JudyHS).

Pero probablemente vaya con un Data.Map.Map (Int, Int) MyClass hasta que tenga problemas de escalabilidad o usabilidad.

Answer 5

He encontrado this short gist que muestra una fila de almacenamiento comprimido para Haskell y el correspondiente multiplicación de matrices en vectores:

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