하스켈 팁/왜이 스케일을 선형 적으로 사용하지 않습니까?

Question

내 친구는 죽은 얼굴의 무작위 배치를 비교하여 가장 균일하게 분포 된 얼굴을 찾는 프로그램을 작성했습니다. 특히 얼굴이 단순한 순서가 아닌 경우 특히 그렇습니다.

저는 멋진 프로그램이 어떤 사람인지에 관해 이야기 할 이유를 찾고 있었기 때문에 그의 프로그램을 haskell로 번역했습니다. 그러나, 나는 haskell에 능숙하지 않다. (이것을 작성하는 데 영원히 걸렸고 거대한 리펙토링을 거쳤다.) 그래서 두 가지 문제가있다.

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)이므로 선형으로 확장 할 수 없습니다. 개선 사항을보기 시작하려면 배열 구조로 이동해야합니다.