하스켈의 기수 정렬 최적화

Question

저는 하스켈을 배우는 중이며 기수 정렬 함수를 작성했습니다. 올바르게 작동하는 것 같지만 문제는 메모리가 비효율적이라는 것입니다. ghc로 컴파일하면, 메모리는 이미 10000 개 요소의 입력리스트로 500MB가 넘습니다.

다음 알고리즘/코드가 어떻게 속도와 메모리면에서 더 효율적으로 개선 될 수 있는지 묻고 싶습니다. 가장 좋은 곳은 무엇입니까? ++은 O (N) 인과 카피마다 첫번째 인수로 주어진리스트 때문에

import System.Random 

-- radixsort for positive integers. uses 10 buckets 
radixsort :: [Int] -> [Int] 
radixsort [] = [] 
radixsort xs = 
    -- given the data, get the number of passes that are required for sorting 
    -- the largest integer 
    let maxPos = floor ((log (fromIntegral (foldl max 0 xs))/log 10) + 1) 

     -- start sorting from digit on position 0 (lowest position) to position 'maxPos' 
     radixsort' ys pos 
     | pos < 0 = ys 
     | otherwise = let sortedYs = radixsort' ys (pos - 1) 
          newBuckets = radixsort'' sortedYs [[] | i <- [1..10]] pos 
         in [element | bucket <- newBuckets, element <- bucket] 

     -- given empty buckets, digit position and list, sort the values into 
     -- buckets 
     radixsort'' []  buckets _ = buckets 
     radixsort'' (y:ys) buckets pos = 
      let digit = div (mod y (10^(pos + 1))) (10^pos) 
       (bucketsBegin, bucketsEnd) = splitAt digit buckets 
       bucket = head bucketsEnd 
       newBucket = bucket ++ [y] 
      in radixsort'' ys (bucketsBegin ++ [newBucket] ++ (tail bucketsEnd)) pos 
    in radixsort' xs maxPos 

-- get an random array given an seed 
getRandIntArray :: Int -> [Int] 
getRandIntArray seed = (randomRs (0, div (maxBound :: Int) 2) (mkStdGen seed)) 

main = do 
     value <- (\x -> return x) (length (radixsort (take 10000 (getRandIntArray 0)))) 
     print value 

Answer 1

주요 문제는, 함수 radixsort''이다.

pack (-1) r' _ = r' 
pack n r' relems = 
    let getn = (map snd) . (filter ((n==) . fst)) 
    in pack (n - 1) ((getn relems):r') relems 
radixsort'' elems pos = 
    let digit = \y -> div (mod y (10^(pos + 1))) (10^pos) 
     relems = zip (map digit elems) elems 
    in pack 9 [] relems