Оптимизация сортировки по основанию в Хаскеле - PullRequest
Новая
       4

Оптимизация сортировки по основанию в Хаскеле

6 голосов
/ 11 марта 2011

Я все еще изучаю Haskell, и я написал следующую основную функцию сортировки.Кажется, он работает правильно, но проблема в том, что он неэффективно использует память.Если скомпилировано с помощью ghc, объем памяти уже превышает 500 МБ со списком входных данных размером 10000 элементов.

Поэтому я хочу спросить вас, как можно улучшить следующий алгоритм / код, чтобы сделать его более эффективным с точки зрения скорости иобъем памяти.Какое самое лучшее место для начала? 

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

1 Ответ

7 голосов
/ 12 марта 2011

Основная проблема - ваша функция radixsort'', потому что ++ - это O (n), и она копирует каждый раз список, указанный в качестве первого аргумента. 

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
...