déballage, matrices (clairsemées) et bibliothèque de vecteurs haskell

Question

Je voudrais manipuler les matrices (complètes ou éparses) efficacement avec la bibliothèque vectorielle de haskell.

est ici un type de 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 

Comme vous pouvez le voir, la matrice est un vecteur de vecteurs unboxed. Maintenant, je voudrais faire un produit scalaire entre un vecteur et une matrice. C'est assez simple à faire en combinant une somme, un zip et une carte. Mais si je fais cela, parce que je suis en train de cartographier les lignes de la matrice, le résultat est un vecteur encadré, même s'il peut être décompacté.

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) 

Comment puis-je obtenir un vecteur non-box efficacement?

Answer 1

Je ne sais pas quel est votre type Field, donc je ne comprends pas très bien le second extrait. Mais si vous représentez votre matrice en tant que vecteur encadré, vos résultats intermédiaires seront des vecteurs encadrés. Si vous souhaitez obtenir un résultat sans boîte, vous devez convertir les types explicitement avec U.fromList . V.toList. Cet exemple pour votre type de matrice dense (j'omis le cas clairsemés par souci de concision):

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) 

Sortie:

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

Je ne suis pas sûr de la performance de cette approche. Il est probablement préférable de stocker toute la matrice sous la forme d'un seul vecteur non boxé et d'accéder aux éléments par index selon le modèle de stockage. De cette façon, vous n'avez pas besoin de vecteurs en boîte.

Regardez également la nouvelle bibliothèque repa et son opération index.