可能なすべてのゲームの「最小の数字が勝つ」ゲーム結果を計算する - メモリ不足

Question

私はハズケルで考え、コードを学習しています。 「最小の数が勝つ」ゲーム：n人が1とnの間の数字にベットを行い、最小の数字が1つの賭けで勝ちます。

私はn = 10と勝者数を数えるベットのすべての可能なシリーズを計算しています。はい、このコードは正確には行いませんが、私のここでのポイントではありませんが、比較的速くメモリが不足している私のコードです。

（追加されたコメント - ！申し訳ありません）

import Data.Array 
import Data.List 

f xs = flip map [1..10] $ flip (:) xs 
p 1 = f [] 
p n = concat $ map f $ p (n-1) 
--the above, (p n) generates the list of all possible [a1, a2, ..., an] lists, where ai=1..10 
--p 2 = [[1,1],[2,1],[3,1],[4,1],[5,1],...,[10,10] 

--my first shot at the countidens function, the functionality stays the same with the other 
--countidens2 xs = map (\x->(head x, length x)) $ group $ sort xs 

countidens' xs = accumArray (+) 0 (1,10) $ zip xs $ repeat 1 
countidens xs = filter ((/=) 0 . snd) $ zip [1..10] $ map ((countidens' xs)!) [1..10] 
--counts the number of occurrences of each number (1..10) in a list 
--countidens [1,1,1,2,2,3] = (1,3),(2,2),(3,1)] 
--(the above, countidens2 is much easier to understand) 

numlist n = map (flip (++) ([(0,0)])) $ map countidens $ p n 
--maps countidens on the (p n) list, and attaches a dummy (0,0) to the end (this is needed later) 

g (x, (y, z)) | (x==y) && (z==1) = True 
       | (x < y)    = True 
       | (y==0)    = True 
       | otherwise   = False 
-- filter function for [(a, (a,a)] lists - (a1, (a1, a)) -> Bool 

winners n = map fst $ map (head . filter g) $ map (zip [1..]) $ numlist n 
-- extracts the number of the first element of (numlist n) that qualifies as g 
-- for each element of g (note: these are results of the countidens function, since that was mapped) 
-- the dummy (0,0) was needed so there's always one that does 

winnernumsarr n = accumArray (+) 0 (1,10) $ flip zip (repeat 1) $ winners n 
-- winners n produces a simple list of integers (1..10) that is 10^n long, this (winnernumsarr) accumulates the number of each integer, much like countidens did 
-- (but does not produce a fancy output) 

main = putStrLn $ show $ winnernumsarr 7 -- aiming for 10! even 8 runs out of memory on my machine 

私はこのコードは、私はそれが何をしたいのですが、正確に何をしません知っているが、何より重要なのは、これは私がしました初めてではないということですhaskellで "メモリ不足"問題に遭遇し、私が知っている問題はC++で書かれていて、使用されるメモリはわずかです。

方法が必要ですが、どうすればよいですか？

Answer 1

ここでは2つのことが重要です。シグネチャとボックス化されていない配列を入力します。

module Main (main) where 

import Data.Array.Unboxed 
import Data.List 

f xs = flip map [1..10] $ flip (:) xs 
p 1 = f [] 
p n = concat $ map f $ p (n-1) 

--my first shot at the countidens function, the functionality stays the same with the other 
--countidens2 xs = map (\x->(head x, length x)) $ group $ sort xs 

countidens' :: [Int] -> UArray Int Int 
countidens' xs = accumArray (+) 0 (1,10) $ zip xs $ repeat 1 

countidens xs = filter ((/=) 0 . snd) $ assocs (countidens' xs) 

numlist n = map (flip (++) ([(0,0)])) $ map countidens $ p n 

g (x, (y, z)) | (x==y) && (z==1) = True 
       | (x < y)    = True 
       | (y==0)    = True 
       | otherwise   = False 

winners n = map fst $ map (head . filter g) $ map (zip [1..]) $ numlist n 

winnernumsarr :: Int -> UArray Int Int 
winnernumsarr n = accumArray (+) 0 (1,10) $ flip zip (repeat 1) $ winners n 
main = putStrLn $ show $ winnernumsarr 7 

は非常に低速ですが（8秒で約50秒、7秒で4.9秒かかる）、実行されます。

箱入りの配列を使用している場合、accumArrayは配列にプレーン・ナンバーを書きませんが、サンクします。 winnernumsarrでは、サンクは巨大になります。これは大量のメモリを必要とし、最終的に評価するために多くのスタックスペースを必要とします。ボックス化されていない配列を使用すると、巨大なサンクを構築するのではなく、追加が行われます。

タイプシグネチャは、印刷する配列のタイプを修正し、すべての発生する数字タイプをより少ない割り当てと高速化のためにIntにするために必要です。

より慣用バージョン、アルゴリズムを変更することなく、また、高速で

module Main (main) where 

import Data.Array.Unboxed 
import Data.List 

p :: Int -> [[Int]] 
p 0 = [[]] 
p n = [k:xs | xs <- p (n-1), k <- [1 .. 10]] 

countidens' :: [Int] -> UArray Int Int 
countidens' xs = accumArray (+) 0 (1,10) $ map (\k -> (k,1)) xs 

countidens :: [Int] -> [(Int,Int)] 
countidens = filter ((/=) 0 . snd) . assocs . countidens' 

numlist n = map ((++[(0,0)]) . countidens) $ p n 

g :: (Int,(Int,Int)) -> Bool 
g (x, (y, z)) | (x==y) && (z==1) = True 
       | (x < y)    = True 
       | (y==0)    = True 
       | otherwise   = False 

winners :: Int -> [Int] 
winners n = map fst $ map (head . filter g) $ map (zip [1..]) $ numlist n 

winnernumsarr :: Int -> UArray Int Int 
winnernumsarr n = accumArray (+) 0 (1,10) $ map (\k -> (k,1)) $ winners n 

main :: IO() 
main = print $ winnernumsarr 7 

あります。 GHCがリスト生成関数pのこの形式を最適化でき、zip xs (repeat 1)をmap (\k -> (k,1)) xsに置き換えることによって、GHCが最適化できるという事実から、少し高速化が行われます。私はなぜそれが大きな違いをもたらすのか理解できないことを認めなければならないが、zipは_ : _の両方のリストと一致しなければならないが、mapはxsと一致する必要がある。

Answer 2

あなたのコードが何をしているのかを正確に理解していないので、代わりに私はちょうど関数を書いた。betsプレイヤーの数と可能なすべての賭けの怠け者リストを吐き出している。

-- `bets n` calculates all possible sequences of bets with `n` players. 
-- It returns a list of lists, each sub-list being `n` in length 
bets :: Int -> [[Int]] 
bets n = bets' n 
    where bets' :: Int -> [[Int]] -- use separate function so we always have the total `n` available 
     bets' n' 
      | n' == 0 = [[]] 
      | n' > 0 = concatMap step $ bets' (pred n') 
      | otherwise = error "bets: negative number of players" 
     step :: [Int] -> [[Int]] 
     step bs = zipWith (:) [1..n] (repeat bs) 

私はn == 5でテストしました。これは美しく動作します。私はn == 10とあなたが期待しているパフォーマンスの種類は分からないので、これはあなたにとって遅すぎる可能性があります。

Answer 3

アレイからボックス化されていない配列でも、Vectorライブラリに切り替えることをお勧めします。インタフェースがはるかに豊富であり、融合ベースのベクタの実装はパフォーマンスのメリットをもたらします。

ここでベクターを用いて同等のバージョンが組み込まダニエル・フィッシャーの変更の一部で、です：私のシステムで

{-# LANGUAGE TupleSections #-} 

import qualified Data.Vector.Unboxed as V 
import Data.List 

p :: Int -> [[Int]] 
p 0 = [[]] 
p n = [k:xs | xs <- p (n-1), k <- [1 .. 10]] 

countidens' :: [Int] -> V.Vector Int 
countidens' xs = V.accum (+) (V.replicate 11 0) $ map (,1) xs 

countidens = V.filter ((/= 0) . snd) . V.indexed . countidens' 

numlist = map ((`V.snoc` (0,0)) . countidens) . p 

g (x, (y, z)) | (x==y) && (z==1) = True 
       | (x < y)    = True 
       | (y==0)    = True 
       | otherwise   = False 

winners n = map (fst . V.head . V.filter g . V.imap (\ix a -> (ix+1,a))) $ numlist n 
winnernumsarr :: Int -> V.Vector (Int,Int) 
winnernumsarr n = V.tail . V.indexed $ V.accum (+) (V.replicate 11 0) 
    $ flip zip (repeat 1) $ winners n 
main = putStrLn $ show $ winnernumsarr 8 

、これは「-O2 -msse2」でコンパイルされた両方のプログラムで、31Sの49Sからランタイムをカット。

2つの注意点：最初にVectorはベクターを実装しているので、多次元のインデックス作成が必要な場合は、配列にとどまることができます。第2に、ベクトルは0でインデックス付けされているため、残りのコードを適切に調整する必要があります。