My friend wrote a program which compares random arrangements of die faces to find the one with the most evenly distributed faces - especially when the faces are not a mere sequence.

I translated his program into haskell because I've been looking for a reason to talk someone's ear off about how cool haskell is. However, I am not very proficient with haskell (it took me forever to write this and it has undergone a couple giant refactorings) and so I have two problems.

  1. he has been big on optimizing his versions, and this is not very fast, and it does not scale linearly. It goes from 415 checks/s to 97 checks/s when I go from 1000 to 20000 checks. Did I mess up some tail recursion or is it some kind of larger problem?
  2. the code that came out of this isn't actually as elegant as I had predicted. I want this to be a solid showcase of Haskell, if you have any ideas on how to simplify it I am all ears

This is the most relevant code:

-- _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)

Main is basically just

print $ maxDistr $ take _TRIALS $ arrangements seed

Just a quick observation: as the length of values and centers increase, the list indexes (!!) are increasingly inefficient. Try values :: Vector Float, centers :: Vector Center with Data.Vector.(!) and see if performance improves.

I'm trying to see what other improvements can be made, I have a few in mind but its difficult to understand how your code works without the full program. Would you mind linking to a pastebin?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.