распаковывание, (редкие) матрицы и haskell векторная библиотека
Я хотел бы управлять матрицами (полный или редкий) эффективно с векторной библиотекой haskell.
Вот матричный тип
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
Как Вы видите, матрица является вектором распакованных векторов. Теперь, я хотел бы сделать скалярное произведение между вектором и матрицей. Довольно просто сделать путем объединения суммы, zip и карты.
Но если я делаю это, потому что я отображаюсь через строки матрицы, результатом является помещенный в коробку вектор, даже при том, что это могло быть распаковано.
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)
Как я могу получить распакованный вектор в результате эффективно?
1 ответ
Я не знаю, какой у вас тип Field, поэтому не совсем понимаю второй фрагмент.
Но если вы представляете свою матрицу как вектор в клетку, ваши промежуточные результаты будут векторами в клетку. Если вы хотите получить неячейковый результат, вам нужно явно преобразовать типы с помощью U.fromList . V.toList. Вот пример для вашего типа плотной матрицы (для краткости я опустил случай разреженной):
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)
Output:
[[1,2],[3,4]] × [5,6] = [17,39]
Я не уверен в производительности этого подхода. Возможно, гораздо лучше хранить всю матрицу как один небоксовый вектор и обращаться к элементам по индексу в соответствии с моделью хранения. Таким образом, вам не понадобятся коробочные векторы.
Посмотрите также на новую библиотеку repa и ее операцию index.