Как эта запомненная таблица DP слишком медленная для SPOJ? - PullRequest
Новая
       45

Как эта запомненная таблица DP слишком медленная для SPOJ?

14 голосов
/ 22 сентября 2011

СПОЙЛЕРЫ: я работаю над http://www.spoj.pl/problems/KNAPSACK/, так что не смотрите, если не хотите, чтобы вам испортили возможное решение.

Шаблон: 

import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)

main = interact knapsackStr

knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
  where [capacity, numItems] = map read . words $ head ls
        ls = lines str
        items = map (makeItem . words) $ take numItems $ tail ls

Некоторые типы и помощники для установки сцены: 

type Item = (Weight, Value)
type Weight = Int
type Value = Int

weight :: Item -> Weight
weight = fst

value :: Item -> Value
value = snd

makeItem :: [String] -> Item
makeItem [w, v] = (read w, read v)

И основная функция: 

knapsack :: [Item] -> Weight -> Int -> Value
knapsack itemsList = go
  where go = memo2 integral integral knapsack'
        items = fromList $ (0,0):itemsList
        knapsack' 0 _ = 0
        knapsack' _ 0 = 0
        knapsack' w i | wi > w    = exclude
                      | otherwise = max exclude include
          where wi = weight item
                vi = value item
                item = items `index` i
                exclude = go w (i-1)
                include = go (w-wi) (i-1) + vi

И этот код работает;Я попытался подключить пример теста SPOJ, и он дает правильный результат.Но когда я отправляю это решение в SPOJ (вместо того, чтобы импортировать MemoCombinators Люка Палмера, я просто копирую и вставляю необходимые детали в предоставленный источник), оно превышает ограничение по времени.= /

Я не понимаю, почему;Я ранее спрашивал об эффективном способе выполнения ранца 0-1, и я вполне уверен, что это примерно так же быстро, как это происходит: запомненная функция, которая будет только рекурсивно вычислять вложенные записи, которые онаабсолютно необходимо для того, чтобы получить правильный результат.Я как-то испортил памятку?Есть ли в этом коде медленная точка, которую мне не хватает?SPOJ просто предвзято относится к Haskell?

Я даже поставил {-# OPTIONS_GHC -O2 #-} в верхней части представления, но, увы, это не помогло.Я пробовал подобное решение, в котором используется двумерный массив Sequence с, но оно также было отклонено как слишком медленное.

Ответы [ 2 ]

4 голосов
/ 18 октября 2011

Есть одна серьезная проблема, которая действительно замедляет это.Это слишком полиморфно.Специализированные по типу версии функций могут быть намного быстрее, чем полиморфные разновидности, и по какой-то причине GHC не указывает этот код до такой степени, что он может определить точные используемые типы.Когда я изменяю определение integral на: 

integral :: Memo Int
integral = wrap id id bits

, я получаю примерно 5-кратное ускорение;Я думаю, что это достаточно быстро, чтобы быть принятым на SPOJ.

Это все еще значительно медленнее, чем решение gorlum0.Я подозреваю, что причина в том, что он использует массивы, а вы используете пользовательский тип Trie.Использование дерева Trie займет гораздо больше памяти, а также замедлит поиск из-за дополнительных косвенных ссылок, пропусков кэша и т. Д. Вы можете быть в состоянии компенсировать большую разницу, если вы строгие и распаковываете поля в IntMap, но я не уверенэто возможноПопытка ограничить поля в BitTrie создает для меня сбои во время выполнения.

Чистый запоминающий код на haskell может быть хорошим, но я не думаю, что это так же быстро, как делать небезопасные вещи (по крайней мере, под капотом).Вы можете применить технику Леннарта Огюсссона , чтобы увидеть, улучшится ли она при запоминании.

0 голосов
/ 22 октября 2016

Единственное, что замедляет Haskell, это IO. Тип String в Haskell предоставляет поддержку UTF8, которая нам не нужна для SPOJ.ByteStrings работают быстро, поэтому вы можете использовать их вместо этого.

...