Unboxing, matrices (dispersas) y biblioteca de vectores haskell - matrices, haskell, vector, unboxing

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

Aquí hay 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 puede ver, la matriz es un vector de vectores sin caja. Ahora, me gustaría hacer un producto de puntos entre un vector y una matriz. Es bastante simple de hacer combinando una suma, un zip y un mapa.

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

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 caja como resultado de manera eficiente?

Respuestas

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

Pero si representa su matriz como un vector en caja, sus resultados intermedios serán vectores en caja. Si desea tener un resultado sin caja, necesita convertir tipos explícitamente con U.fromList . V.toList. Este es un ejemplo para su tipo de matriz densa (omití el caso disperso por 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 según el modelo de almacenamiento. De esta manera usted no necesita vectores en caja.

Echa un vistazo también a nuevo repa biblioteca y su index operación.