Mẹo Haskell/tại sao không quy mô này tuyến tính?

Question

Bạn tôi đã viết một chương trình so sánh sự sắp xếp ngẫu nhiên khuôn mặt chết để tìm khuôn mặt có khuôn mặt được phân bố đều nhất - đặc biệt khi các khuôn mặt không phải là một chuỗi đơn thuần.

Tôi đã dịch chương trình của anh ấy thành haskell bởi vì tôi đã tìm kiếm lý do để nói chuyện với ai đó về việc haskell tuyệt vời như thế nào. Tuy nhiên, tôi không thành thạo với haskell (nó đã cho tôi mãi mãi để viết điều này và nó đã trải qua một vài tái cấu trúc khổng lồ) và vì vậy tôi có hai vấn đề.

1. anh ấy đã lớn về việc tối ưu hóa các phiên bản của mình và điều này không quá nhanh và không quy mô tuyến tính. Tôi đã làm hỏng một số đệ quy đuôi hoặc là nó một số loại vấn đề lớn hơn?
2. mã xuất hiện không thực sự tao nhã như tôi đã dự đoán. Tôi biết điều này không phải là một diễn đàn thảo luận, nhưng nếu bạn có bất kỳ ý tưởng về làm thế nào để đơn giản hóa nó Tôi là tất cả tai

Đây là mã phù hợp nhất:

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

chính là cơ bản chỉ

print $ maxDistr $ take _TRIALS $ arrangements seed 

Answer 1

Là lưu ý nhận xét, nó không thể mở rộng tuyến tính khi lập chỉ mục vào danh sách là O(index). Bạn sẽ cần chuyển sang cấu trúc mảng để bắt đầu thấy các cải tiến.