Haskell動態編程的高效表

Question

我編寫了Haskell中的0-1 Knapsack problem。我對迄今爲止所達到的懶惰和普遍性水平感到非常自豪。

我開始提供創建和處理惰性2D矩陣的函數。

mkList f = map f [0..] 
mkTable f = mkList (\i -> mkList (\j -> f i j)) 

tableIndex table i j = table !! i !! j 

我再做出具體的表給定揹包問題

knapsackTable = mkTable f 
    where f 0 _ = 0 
      f _ 0 = 0 
      f i j | ws!!i > j = leaveI 
       | otherwise = max takeI leaveI 
       where takeI = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i 
        leaveI = tableIndex knapsackTable (i-1) j 

-- weight value pairs; item i has weight ws!!i and value vs!!i 
ws = [0,1,2, 5, 6, 7] -- weights 
vs = [0,1,7,11,21,31] -- values 

並與一對夫婦的輔助功能玩完了在表中查找

viewTable table maxI maxJ = take (maxI+1) . map (take (maxJ+1)) $ table 
printTable table maxI maxJ = mapM_ print $ viewTable table maxI maxJ 

這多少是很容易。但我想更進一步。

我想要一個更好的表格數據結構。理想的情況下，它應該是

• 無盒裝（不變） [編輯]別提這個
• 懶
• 無界
• O(1)時間來構建
• O(1)時間複雜度爲查找給定條目，
  （更真實地說，最壞的情況是O(log n)，其中n是i*j，用於在r處查找條目我列j）

獎勵積分，如果你能解釋爲什麼/你的解決方案如何滿足這些理想。

如果您可以進一步概括knapsackTable，並證明它是有效的，還可獲得積分。

在提高數據結構，你應該儘量滿足以下目標：

• 如果我問其中的最大重量爲10的溶液（在我當前的代碼，這將是indexTable knapsackTable 5 10，5種手段包括1-5項）只需要執行最少量的工作。理想情況下，這意味着沒有O(i*j)用於強制表中每行的脊柱達到必要的列長度。如果您認爲DP意味着評估整個表格，您可以說這不是「真正的」DP。
• 如果我要求打印整個表格（類似printTable knapsackTable 5 10），則每個條目的值應該只計算一次。給定單元的值應取決於其他單元格的值（DP風格：想法是，從來沒有重新計算相同的子問題兩次）

---

思路：

• Data.Array界:(
• UArray嚴格:(
• Memoization techniques（SO大約DP哈斯克爾問題）這可能工作

答案，使我對所述的理想有所妥協將 upvoted（由我，反正），只要他們是信息。答案最少的可能是「接受」的答案。

Answer 1

首先，您對無盒數據結構的標準可能有點誤導。無盒值必須嚴格，而且它們與不變性無關。我要提出的解決方案是不可變的，懶惰的和盒裝的。另外，我不確定你想以什麼方式構建和查詢是O（1）。我建議的結構是懶散地建造的，但是因爲它可能是無限的，所以它的全部構造將需要無限的時間。查詢結構將會花費O（k）個時間處理k個大小的特定鍵，但是當然，您查找的值可能需要更長的時間來計算。

數據結構是一個懶線索。我在代碼中使用了Conal Elliott的MemoTrie庫。對於通用性，它取得的是權重和值的函數而不是列表。

knapsack :: (Enum a, Num w, Num v, Num a, Ord w, Ord v, HasTrie a, HasTrie w) => 
      (a -> w) -> (a -> v) -> a -> w -> v 
knapsack weight value = knapsackMem 
    where knapsackMem = memo2 knapsack' 
     knapsack' 0 w = 0 
     knapsack' i 0 = 0 
     knapsack' i w 
      | weight i > w = knapsackMem (pred i) w 
      | otherwise = max (knapsackMem (pred i) w) 
         (knapsackMem (pred i) (w - weight i)) + value i 

基本上，它實現爲具有懶惰的脊柱和懶惰值的trie。它只受關鍵類型限制。因爲整個事情都是懶惰的，所以在強制查詢之前它的構造是O（1）。每個查詢強制沿着trie的單個路徑及其值，因此它的 O（1）對於有界密鑰大小 O（log n）。正如我已經說過的那樣，它是不可改變的，但不是拆箱。

它將共享遞歸調用中的所有工作。它實際上並沒有讓你直接打印線索，但這樣的事情不應該做任何多餘的工作：

mapM_ (print . uncurry (knapsack ws vs)) $ range ((0,0), (i,w)) 

Answer 2

爲什麼不使用Data.Map將其他Data.Map放入它？據我所知這很快。 雖然這不會太懶。

更重要的，你可以實現奧德類型類爲您的數據

data Index = Index Int Int 

，並直接把二維索引處作爲重點。您可以通過生成此地圖作爲列表來實現懶惰，然後只使用

fromList [(Index 0 0, value11), (Index 0 1, value12), ...] 

Answer 3

拆箱意味着嚴格和有界。任何100％Unboxed都不能懶惰或無界限。通常的折衷方案體現在將[Word8]轉換爲Data.ByteString.Lazy，其中有無箱的塊（嚴格的ByteString），它們以無限制的方式懶散地連接在一起。

可以使用「scanl」，「zipWith」和我的「takeOnto」來創建效率更高的表生成器（增強用於跟蹤各個項目）。這有效地避免使用（!!）在創建表：

import Data.List(sort,genericTake) 

type Table = [ [ Entry ] ] 

data Entry = Entry { bestValue :: !Integer, pieces :: [[WV]] } 
    deriving (Read,Show) 

data WV = WV { weight, value :: !Integer } 
    deriving (Read,Show,Eq,Ord) 

instance Eq Entry where 
    (==) a b = (==) (bestValue a) (bestValue b) 

instance Ord Entry where 
    compare a b = compare (bestValue a) (bestValue b) 

solutions :: Entry -> Int 
solutions = length . filter (not . null) . pieces 

addItem :: Entry -> WV -> Entry 
addItem e wv = Entry { bestValue = bestValue e + value wv, pieces = map (wv:) (pieces e) } 

-- Utility function for improve 
takeOnto :: ([a] -> [a]) -> Integer -> [a] -> [a] 
takeOnto endF = go where 
    go n rest | n <=0 = endF rest 
      | otherwise = case rest of 
          (x:xs) -> x : go (pred n) xs 
          [] -> error "takeOnto: unexpected []" 

improve oldList wv@(WV {weight=wi,value = vi}) = newList where 
    newList | vi <=0 = oldList 
      | otherwise = takeOnto (zipWith maxAB oldList) wi oldList 
    -- Dual traversal of index (w-wi) and index w makes this a zipWith 
    maxAB e2 e1 = let e2v = addItem e2 wv 
       in case compare e1 e2v of 
        LT -> e2v 
        EQ -> Entry { bestValue = bestValue e1 
           , pieces = pieces e1 ++ pieces e2v } 
        GT -> e1 

-- Note that the returned table is finite 
-- The dependence on only the previous row makes this a "scanl" operation 
makeTable :: [Int] -> [Int] -> Table 
makeTable ws vs = 
    let wvs = zipWith WV (map toInteger ws) (map toInteger vs) 
     nil = repeat (Entry { bestValue = 0, pieces = [[]] }) 
     totW = sum (map weight wvs) 
    in map (genericTake (succ totW)) $ scanl improve nil wvs 

-- Create specific table, note that weights (1+7) equal weight 8 
ws, vs :: [Int] 
ws = [2,3, 5, 5, 6, 7] -- weights 
vs = [1,7,8,11,21,31] -- values 

t = makeTable ws vs 

-- Investigate table 

seeTable = mapM_ seeBestValue t 
    where seeBestValue row = mapM_ (\v -> putStr (' ':(show (bestValue v)))) row >> putChar '\n' 

ways = mapM_ seeWays t 
    where seeWays row = mapM_ (\v -> putStr (' ':(show (solutions v)))) row >> putChar '\n' 

-- This has two ways of satisfying a bestValue of 8 for 3 items up to total weight 5 
interesting = print (t !! 3 !! 5) 

Answer 4

懶惰可儲存載體：http://hackage.haskell.org/package/storablevector

無界，懶惰，O（CHUNKSIZE）時間來構造，O（N/CHUNKSIZE）索引，其中對於任何給定的目的，塊大小可以足夠大。基本上是一個懶惰的列表，有一些重要的常數因子好處。

Answer 5

爲了memoize的功能，我建議像盧克帕爾默的memo combinators庫。該庫使用try，它是無界的，並具有O（密鑰大小）查找。 （一般情況下，你不能這樣做比O（密鑰大小）查找更好，因爲你總是要觸摸鍵的每一個位。）

knapsack :: (Int,Int) -> Solution 
knapsack = memo f 
    where 
    memo = pair integral integral 
    f (i,j) = ... knapsack (i-b,j) ... 

內部，integral組合子可能建立一個無限數據結構

data IntTrie a = Branch IntTrie a IntTrie 

integral f = \n -> lookup n table 
    where 
    table = Branch (\n -> f (2*n)) (f 0) (\n -> f (2*n+1)) 

查詢是這樣的：

lookup 0 (Branch l a r) = a 
lookup n (Branch l a r) = if even n then lookup n2 l else lookup n2 r 
    where n2 = n `div` 2 

還有其他的方法來構建無限的嘗試，但是這一次是popul AR。