我在 Haskell 中撰寫了一個函式來計算矩陣的行列式，它作業得很好，但速度非常慢，所以我試著像Haskell Wiki 中的 Fibonacci 函式一樣記住它。
但不知何故，即使在計算單位矩陣的行列式時，我的記憶函式也比非記憶函式花費的時間略長，這應該從記憶中受益匪淺。
我還嘗試使用 Map 來快取結果，但找不到將修改后的 Map 傳遞給遞回函式的下一次迭代的方法。
我怎樣才能解決這個問題？
-- Non-Memoized version
det :: (Num a, Eq a) => [[a]] -> a
det x
| fst s == 0 = 0
| fst s == 1 = head $ head x
| fst s == 2 = (head (head x) * ((x !! 1) !! 1))
- ((head x !! 1) * head (x !! 1))
| F.allEqual x = 0
| otherwise = sum [((-1) ^ (i 1)) * head (x !! (i - 1))
* det (sub x i 1)
| i <- [1..(fst s)]]
where
s = shape x
-- Memoized version
mDet :: (Num a, Eq a) => [[a]] -> a
mDet x = sum [((-1) ^ (i 1)) * head (x !! (i - 1))
* det' (sub x i 1)
| i <- [1..(fst $ shape x)]]
where
det' y
| fst s == 0 = 0
| fst s == 1 = head $ head y
| fst s == 2 = (head (head y) * ((y !! 1) !! 1))
- ((head y !! 1) * head (y !! 1))
| F.allEqual y = 0
| otherwise = mDet y
where
s = shape y
uj5u.com熱心網友回復：
有更有效的演算法可以通過分解來計算行列式。
即使有了記憶，在樸素的行列式公式中也有指數級的子矩陣，所以這有點毫無意義。
uj5u.com熱心網友回復：
僅供參考，您的函式重寫以避免!!訪問變為
-- Non-Memoized version
det :: (Num a, Eq a) => [[a]] -> a
det [] = 0
det [r] = head r
det [r,q] = case [r,q] of
[[a,b],[c,d]] -> a*d - b*c -- error out on wrong shape
det x | or [ or [a==b | b <- bs] -- quadratic test
| (a:bs) <- tails x ] -- (must be "collinear",
= 0 -- "any", not "all"! -- not "==", anyway)
det x = sum $ [s * head r * det ([reverse a,b] >>= map tail)
| (a,r,b) <- picks3 x
| s <- cycle [1,-1]]
picks3 :: [a] -> [([a], a, [a])]
picks3 xs = unfoldr (\case { (_,[]) -> Nothing ;
(a,x:xs) -> Just ((a,x,xs), (x:a,xs)) })
([],xs)
這里沒有什么可以立即記住的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/423004.html
標籤：
上一篇：堆組態檔中的微量元素是什么？
下一篇：檔案開頭無用的種類相等錯誤