ハスケルのヒント/なぜこのスケールは線形になりませんか？

Question

私の友人は、特に顔が単なるシーケンスではない場合に、最も均一に分布した顔を持つものを見つけるために、ダイの顔のランダムな配列を比較するプログラムを書いています。

私は自分のプログラムを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 

Answer 1

コメントには、リストへのインデックス付けがO(index)なので、線形に拡大縮小することはできません。改善を見始めるには、配列構造体に移動する必要があります。