unboxing, (rzadkie) macierze i biblioteka wektorów haskell - tablice, haskell, wektor, unboxing

Chciałbym efektywnie manipulować macierzami (pełną lub rzadką) za pomocą biblioteki wektorowej haskell.

Oto typ macierzy

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

Jak widzisz, macierz jest wektorem wektorów bez pudełek. Chciałbym teraz zrobić produkt kropkowy między wektorem a macierzą. Całkiem proste jest połączenie sumy, zipu i mapy.

Ale jeśli to zrobię, ponieważ odwzorowuję przez wiersze macierzy, wynikiem jest wektor w ramce, mimo że może być rozpakowany.

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)

W jaki sposób mogę wydajnie uzyskać wektor bez skrzynki?

Odpowiedzi:

Nie wiem, co twoja Field typ jest, więc nie rozumiem drugiego fragmentu.

Ale jeśli reprezentujesz swoją macierz jako wektor w ramce, wyniki pośrednie będą wektorem pudełkowym. Jeśli chcesz uzyskać wynik niezapisany, musisz jawnie przekonwertować typy za pomocą U.fromList . V.toList. To przykład dla twojego gęstego typu matrycy (pominąłem rzadki przypadek dla zwięzłości):

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)

Wydajność:

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

Nie jestem pewien co do skuteczności tego podejścia. Prawdopodobnie o wiele lepiej jest przechowywać całą macierz jako pojedynczy wektor bez skrzynki i uzyskiwać dostęp do elementów według indeksu według modelu pamięci. W ten sposób nie potrzebujesz wektorów pudełkowych.

Spójrz także na nowe repa biblioteka i jej index operacja.