15

ネタバレ：私は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に送信すると（Luke PalmerのMemoCombinatorsをインポートする代わりに、必要なパーツをコピーして送信されたソースに貼り付けるだけです）、制限時間を超えています。= /

理由がわかりません。0-1ナップザックを実行する効率的な方法について以前に質問しましたが、これはほぼ同じ速さであるとかなり確信しています。メモ化された関数は、生成するために絶対に必要なサブエントリのみを再帰的に計算します。正しい結果。どういうわけかメモ化を台無しにしましたか？このコードに私が見逃している遅い点はありますか？SPOJはHaskellに対して偏見を持っているだけですか？

私も{-# OPTIONS_GHC -O2 #-}提出物の一番上に置きましたが、残念ながら、それは役に立ちませんでした。の2D配列を使用する同様のソリューションを試しましたSequenceが、遅すぎるとして拒否されました。

4

2 に答える 2

4

これを本当に遅くする1つの大きな問題があります。多形すぎます。関数の型に特化したバージョンは、多態的な種類よりもはるかに高速である可能性があり、何らかの理由で、GHCは、使用中の正確な型を判別できるポイントまでこのコードをインライン化しません。の定義を次のように変更すると、次のintegralようになります。

integral :: Memo Int
integral = wrap id id bits

約5倍のスピードアップが得られます。SPOJで受け入れられるほど速いと思います。

ただし、これはgorlum0のソリューションよりも大幅に低速です。その理由は、彼が配列を使用していて、カスタムのトライタイプを使用しているためだと思います。トライを使用すると、メモリが大幅に消費され、余分な間接化やキャッシュミスなどが原因でルックアップが遅くなります。IntMapでフィールドを厳密化してボックス化解除すると、多くの違いを補うことができるかもしれませんが、よくわかりません。それは可能です。でフィールドを厳密化しようとすると、BitTrieランタイムクラッシュが発生します。

純粋なhaskellのメモ化コードは良いかもしれませんが、（少なくとも内部では）危険なことをするほど速くはないと思います。レナート・オーガストソンの手法を適用して、メモ化がうまくいくかどうかを確認できます。

于 2011-10-18T14:02:02.653 に答える
0

Haskellの速度を低下させる1つのことはIOです。HaskellのString型は、SPOJには必要のないUTF8サポートを提供します。ByteStringは非常に高速であるため、代わりにByteStringの使用を検討することをお勧めします。

于 2016-10-22T17:43:30.593 に答える