matrici unboxing, (sparse) e libreria vettoriale haskell

Question

Mi piacerebbe manipolare le matrici (complete o sparse) in modo efficiente con la libreria vettoriale di haskell.

Qui è un tipo di matrice

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 

Come si può vedere, la matrice è un vettore di vettori senza custodia. Ora, vorrei fare un prodotto punto tra un vettore e una matrice. È abbastanza semplice combinare una somma, una zip e una mappa.

Ma se lo faccio, perché sto mappando attraverso le righe della matrice, il risultato è un vettore in scatola, anche se potrebbe essere unboxed.

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) 

Come posso ottenere un vettore unboxed come risultato in modo efficiente?

Answer 1

Non so quale sia il tuo tipo Field, quindi non capisco il secondo frammento.

Ma se si rappresenta la matrice come un vettore in scatola, i risultati intermedi saranno vettori in scatola. Se si desidera avere un risultato unbox, è necessario convertire i tipi esplicitamente con U.fromList . V.toList. Questo un esempio per il tipo di matrice densa (ho omesso il case sparse per brevità):

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) 

uscita:

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

Non sono sicuro circa le prestazioni di questo approccio. Probabilmente è molto meglio memorizzare l'intera matrice come un singolo vettore unboxed e accedere agli elementi per indice in base al modello di archiviazione. In questo modo non hai bisogno di vettori in scatola.

Dai un'occhiata anche alla nuova libreria repa e alla sua operazione index.