我的 friend 编写了一个程序,它比较随机排列的骰子面,以找到分布最均匀的面——尤其是当面不仅仅是序列时。
我将他的程序翻译成 haskell 是因为我一直在寻找一个理由来让别人知道 haskell 有多酷。然而,我对 haskell 不是很精通(我花了很长时间写这个,而且它经历了几次巨大的重构),所以我有两个问题。
这是最相关的代码:
-- _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
最佳答案
正如评论所指出的,它不能线性缩放,因为索引到列表中是 O(index)
.您需要转到数组结构才能开始看到改进。
关于Haskell 提示/为什么这不是线性缩放?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13371014/