unboxing, (dispersas) matrices y biblioteca de vectores haskell

Question

Me gustaría manipular matrices (completas o dispersas) de manera eficiente con la biblioteca de vectores de haskell.

Aquí es un tipo de matriz

import qualified Data.Vector.Unboxed as U 
import qualified Data.Vector as V 

data Link a = Full (V.Vector (U.Vector a)) 
    | Sparse (V.Vector (U.Vector (Int,a))) 

type Vector a = U.Vector a 

Como se puede ver, la matriz es un vector de vectores sin embalaje. Ahora, me gustaría hacer un producto de punto entre un vector y una matriz. Es bastante simple de hacer combinando una suma, zip y mapa.

Pero si hago eso, porque estoy mapeando a través de las filas de la matriz, el resultado es un vector en caja, aunque podría estar desagrupado.

propagateS output (Field src) (Full weights) = V.map (sum out) weights 
    where out  = U.map output src 
      sum s w = U.sum $ zipWithFull (*) w s 

propagateS output (Field src) (Sparse weights) = V.map (sum out) weights 
    where out  = U.map output src 
      sum s w = U.sum $ zipWithSparse (*) w s 

zipWithFull = U.zipWith 

zipWithSparse f x y = U.map f' x 
    where f' (i,v) = f v (y U.! i) 

¿Cómo puedo obtener un vector sin embalaje como resultado de manera eficiente?

Answer 1

No sé cuál es su tipo de Field, por lo que no entiendo muy bien el segundo fragmento.

Pero si representa su matriz como un vector enmarcado, sus resultados intermedios serán vectores encuadrados. Si desea obtener un resultado no empacado, debe convertir los tipos explícitamente con U.fromList . V.toList. Este un ejemplo para su densa tipo de matriz (I omite el caso escasa por razones de brevedad):

import qualified Data.Vector.Unboxed as U 
import qualified Data.Vector as V 

-- assuming row-major order 
data Matrix a = Full (V.Vector (U.Vector a)) 

type Vector a = U.Vector a 

-- matrix to vector dot product 
dot :: (U.Unbox a, Num a) => (Matrix a) -> (Vector a) -> (Vector a) 
(Full rows) `dot` x = 
    let mx = V.map (vdot x) rows 
    in U.fromList . V.toList $ mx -- unboxing, O(n) 

-- vector to vector dot product 
vdot :: (U.Unbox a, Num a) => Vector a -> Vector a -> a 
vdot x y = U.sum $ U.zipWith (*) x y 

instance (Show a, U.Unbox a) => Show (Matrix a) where 
    show (Full rows) = show $ V.toList $ V.map U.toList rows 

showV = show . U.toList 

main = 
    let m = Full $ V.fromList $ map U.fromList ([[1,2],[3,4]] :: [[Int]]) 
     x = U.fromList ([5,6] :: [Int]) 
     mx = m `dot` x 
    in putStrLn $ (show m) ++ " × " ++ (showV x) ++ " = " ++ (showV mx) 

Salida:

[[1,2],[3,4]] × [5,6] = [17,39] 

no estoy seguro sobre el rendimiento de este enfoque. Probablemente sea mucho mejor almacenar toda la matriz como un único vector sin caja y acceder a los elementos por índice de acuerdo con el modelo de almacenamiento. De esta manera no necesita vectores en caja.

Eche un vistazo también a la nueva biblioteca repa y su operación index.