Эффективная таблица для динамического программирования на Haskell

Во-первых, ваш критерий для неупакованной структуры данных, вероятно, немного вводит в заблуждение. Неупакованные значения должны быть строгими и не имеют ничего общего с неизменностью. Решение, которое я собираюсь предложить, является неизменным, ленивым и упакованным. Кроме того, я не уверен, каким образом вы хотите, чтобы построение и запрос были O (1). Предлагаемая мной структура строится лениво, но поскольку она потенциально неограниченна, ее полное построение займет бесконечное время. Запрос структуры займет O(k) времени для любого конкретного ключа размера k, но, конечно, для вычисления значения, которое вы ищете, может потребоваться дополнительное время.

Структура данных — ленивая попытка. В своем коде я использую библиотеку 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(1) для ограниченного размера ключа O(log n). Как я уже сказал, он неизменяемый, но не распакованный.

Он разделит всю работу в рекурсивных вызовах. На самом деле это не позволяет вам печатать trie напрямую, но что-то вроде этого не должно выполнять лишней работы:

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

Unboxed подразумевает строгость и ограниченность. Все, что на 100% не упаковано, не может быть ленивым или неограниченным. Обычный компромисс воплощается в преобразовании [Word8] в Data.ByteString.Lazy, где есть неупакованные фрагменты (strict 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) 

Ленивые сохраняемые векторы: http://hackage.haskell.org/package/storablevector

Неограниченное, ленивое, O(размер фрагмента) время построения, индексирование O(n/размер фрагмента), где размер фрагмента может быть достаточно большим для любой заданной цели. По сути, ленивый список с некоторыми значительными преимуществами постоянного фактора.

Для запоминания функций я рекомендую такую ​​библиотеку, как memo combinators Люка Палмера. Библиотека использует попытки, которые не ограничены и имеют поиск 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

Есть и другие способы создания бесконечных попыток, но этот популярен.

Почему бы вам не использовать Data.Map, вставив в него другой Data.Map? Насколько я знаю, это довольно быстро. Хотя было бы не лень.

Более того, вы можете реализовать класс типов Ord для своих данных.

data Index = Index Int Int

и поместите двумерный индекс непосредственно в качестве ключа. Вы можете добиться лени, создав эту карту в виде списка, а затем просто используя

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