haskell - Haskell での動的プログラミングの効率的なテーブル

Question

Haskell で0-1 ナップサック問題をコード化しました。これまでに達成された怠惰さと一般性のレベルについて、私はかなり誇りに思っています。

まず、遅延 2 次元行列を作成して処理するための関数を提供します。

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)場合、ni*jは行 i、列 j のエントリを検索するためのもの)

ソリューションがこれらの理想を満たしている理由/方法を説明できればボーナス ポイントです。

knapsackTableをさらに一般化し、それが効率的であることを証明できれば、ボーナス ポイントも得られます。

データ構造を改善するには、次の目標を満たすようにしてください。

• 最大重みが 10 であるソリューションを求める場合 (私の現在のコードではindexTable knapsackTable 5 10、5 は項目 1 ～ 5 を含むことを意味します)、必要最小限の作業のみを実行する必要があります。理想的には、これはO(i*j)、テーブルの各行の背骨を必要な列の長さに強制する作業がないことを意味します。DP がテーブル全体を評価することを意味すると考える場合、これは「真の」DP ではないと言えます。
• テーブル全体を印刷するように要求した場合 (のようなものprintTable knapsackTable 5 10)、各エントリの値は一度だけ計算する必要があります。特定のセルの値は、他のセルの値に依存する必要があります (DP スタイル: 考え方として、同じ部分問題を 2 回再計算しないでください)。

---

アイデア:

• Data.Array境界 :(
• UArray厳密 :(
• メモ化技術（HaskellのDPに関するSOの質問）これはうまくいくかもしれません

私の述べた理想にある程度の妥協をする回答は、有益である限り、（とにかく私によって）支持されます。妥協が最も少ない答えは、おそらく「受け入れられる」ものになるでしょう。

Answer 1

まず、ボックス化されていないデータ構造の基準は、おそらく少し誤解を招く可能性があります。ボックス化されていない値は厳密でなければならず、不変性とは何の関係もありません。私が提案しようとしている解決策は、不変で、怠惰で、ボックス化されています。また、構築とクエリをどのように O(1) にしたいのかわかりません。私が提案している構造は遅延構築されていますが、無限の可能性があるため、完全な構築には無限の時間がかかります。構造体のクエリには、サイズ k の特定のキーに対して O(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

基本的に、レイジー スパインとレイジー値を持つトライとして実装されます。キーの種類によってのみ制限されます。全体が遅延しているため、クエリで強制する前の構造は O(1) です。各クエリは、トライとその値を下る単一のパスを強制するため、制限されたキー サイズO(log n) の場合は O(1) になります。すでに述べたように、これは不変ですが、ボックス化されていません。

再帰呼び出しですべての作業を共有します。実際にはトライを直接印刷することはできませんが、次のようなものは冗長な作業を行うべきではありません:

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

Answer 2

ボックス化されていないということは、厳密で境界があることを意味します。100% Unboxed のものは、Lazy または Unbounded にすることはできません。通常の妥協は、[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 3

怠惰な保存可能なベクトル： http： //hackage.haskell.org/package/storablevector

無制限の、怠惰な、構築するためのO（チャンクサイズ）時間、O（n /チャンクサイズ）インデックス。チャンクサイズは、任意の目的に対して十分に大きくすることができます。基本的に、いくつかの重要な定数係数の利点を備えた怠惰なリスト。

Answer 4

関数をメモ化するには、Luke Palmer のメモ コンビネーターのようなライブラリをお勧めします。ライブラリは、制限がなく、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

無限試行を作成する方法は他にもありますが、これが人気です。

Answer 5

他の Data.Map を入れて Data.Map を使用しないのはなぜですか? 私の知る限り、それはかなり速いです。怠け者ではないでしょう。

それ以上に、データに Ord 型クラスを実装できます

data Index = Index Int Int

2 次元インデックスを直接キーとして配置します。このマップをリストとして生成してから使用することで怠惰を実現できます

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