5

私の友人は、サイコロの面のランダムな配置を比較して、最も均等に分散された面を持つものを見つけるプログラムを書きました-特に面が単なるシーケンスではない場合.

私は彼のプログラムを haskell に翻訳しました。なぜなら、haskell がいかにクールであるかについて誰かの耳を疑う理由を探していたからです。しかし、私は Haskell にあまり精通していないので (これを書くのに永遠に時間がかかり、いくつかの巨大なリファクタリングを受けました)、2 つの問題があります。

  1. 彼は自分のバージョンの最適化に力を入れてきましたが、これはあまり速くなく、線形にスケーリングしません。末尾の再帰を台無しにしましたか、それともより大きな問題ですか?
  2. ここから生まれたコードは、実際には私が予測したほどエレガントではありません。これがディスカッション掲示板ではないことは承知していますが、簡単にする方法について何かアイデアがあれば、私はすべて耳にします

これは最も関連性の高いコードです:

-- _CENTERS :: [{ x :: Float, y :: Float, z :: Float}]
-- _VALUES :: [Num]

-- Basically just (repeat $ map rand [0.._SIDES]), but never using a seed twice
randstates from = (take _SIDES (infrand from)) : randstates newseed
    where   infrand seed = seed : infrand (shuffle seed)
            newseed      = (infrand from) !! (_SIDES + 1)

-- yates shuffle
yates _ (last:[]) = [last]
yates (rand:pass) (swap:order) = choice:yates pass rorder
        where   choice = order !! index
                index  = (randfrom rand) `mod` (length order)
                rorder = take (index) order ++ swap : drop (index + 1) order

arrangements seed = map arrange $ randstates seed
        where   arrange rands = yates rands [0.._SIDES - 2]

-- fns comparing arrangements --
arcLength i j = 1 / (1 + _WEIGHT * acos(dot3D / _VEC_LEN_SQUARED))
        where   dot3D    = apply x + apply y + apply z
                apply fn = (fn i) * (fn j)

matrix arr = map crosscmp arr
        where   crosscmp s1  = [ value s1 * (distance s1 s2) | s2  <- arr ]
                distance a b = arcLength (_CENTERS !! a) (_CENTERS !! b)
                value s      = fromInteger $ _VALUES !! s

variance arr = sum $ map perside (matrix arr)
        where   perside s = (sum s - mean) ^ 2
                mean      = (sum (concat $ matrix arr)) / (sides + 1)
                sides     = fromInteger $ toInteger _SIDES

maxDistr = maximumBy (\a b -> variance a `compare` variance b)

メインは基本的に

print $ maxDistr $ take _TRIALS $ arrangements seed
4

1 に答える 1

1

コメントにあるように、リストへのインデックス付けはO(index). 改善を確認するには、配列構造に移行する必要があります。

于 2015-02-23T05:53:59.683 に答える