Unboxing, (spärlich) Matrizen und Haskell-Vektorbibliothek

Question

Ich möchte Matrizen (voll oder spärlich) effizient mit Haskells Vektorbibliothek manipulieren.

Hier ist eine Matrix-Typ

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 

Wie Sie sehen können, wobei die Matrix ein Vektor von unboxed Vektoren ist. Nun würde ich gerne ein Punktprodukt zwischen einem Vektor und einer Matrix machen. Es ist ziemlich einfach zu tun, indem man eine Summe, einen Reißverschluss und eine Karte kombiniert.

Aber wenn ich das tue, weil ich durch die Reihen der Matrix abbilde, ist das Ergebnis ein eingerahmter Vektor, obwohl es ungepackt sein könnte.

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) 

Wie kann ich einen unboxed Vektor als Ergebnis effizient erhalten?

Answer 1

Ich weiß nicht, was Ihr Field Typ ist, so verstehe ich nicht ganz das zweite Snippet.

Aber wenn Sie Ihre Matrix als ein Boxed Vektor darstellen, werden Ihre Zwischenergebnisse Boxed Vektoren sein. Wenn Sie ein ungesichertes Ergebnis haben möchten, müssen Sie Typen explizit mit U.fromList . V.toList konvertieren. Dies ist ein Beispiel für Ihre dichte Matrix-Typ (I weggelassen, um die spärlichen Fall der Kürze halber):

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) 

Ausgang:

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

Ich bin über die Leistung dieses Ansatzes nicht sicher. Wahrscheinlich ist es viel besser, die gesamte Matrix als einen einzelnen ungepackten Vektor zu speichern und Elemente gemäß dem Speichermodell nach Index zu durchsuchen. Auf diese Weise benötigen Sie keine umrahmten Vektoren.

Schauen Sie sich auch die neue repa-Bibliothek und ihre index Operation an.