сортировка целых чисел в haskell

Question

Есть ли какая-либо функция в библиотеках haskell, которая сортирует целые числа в O (n) времени? [К, О (п) я имею в виду быстрее, чем сравнение сортировка и специфическая для целых]

В принципе я считаю, что следующий код занимает много времени с родом (по сравнению с суммированием списка без сортировки):

import System.Random 
import Control.DeepSeq 
import Data.List (sort) 

genlist gen = id $!! sort $!! take (2^22) ((randoms gen)::[Int]) 

main = do 
    gen <- newStdGen 
    putStrLn $ show $ sum $ genlist gen 

Подведение итогов для списка не требует глубины, но то, что я пытаюсь сделать, но приведенный выше код достаточно хорош для указателей, которые я ищу.

Время: 6 секунд (без сортировки); около 35 секунд (с сортировкой)

Память: около 80 МБ (без сортировки); около 310 МБ (с сортировкой)

Примечание 1: Память - большая проблема, чем время для меня здесь, так как для задачи под рукой я получаю ошибки в памяти (использование памяти становится 3 ГБ! после 30 минут работы -time)

Я предполагаю, что более быстрые алгоритмы также обеспечат печать на бета-памяти, следовательно, ищите O (n) время.

Примечание 2: Я ищу быстрые алгоритмы для Int64, хотя быстрые алгоритмы для других конкретных типов также будут полезны.

---

Решение Используется: IntroSort с Unboxed векторами был достаточно хорош для моей задачи:

import qualified Data.Vector.Unboxed as V 
import qualified Data.Vector.Algorithms.Intro as I 

sort :: [Int] -> [Int] 
sort = V.toList . V.modify I.sort . V.fromList 

Answer 1

Идея сортировки чисел с использованием массива является правильной для уменьшения использования памяти.

Однако использование максимального и минимального списка в качестве границ может привести к превышению использования памяти или даже сбою во время выполнения при maximum xs - minimum xs > (maxBound :: Int).

Поэтому я предлагаю записать содержимое списка в unboxed изменяемый массив, сортируя его на месте (например, с помощью quicksort), а затем снова создавая список из этого списка.

import System.Random 
import Control.DeepSeq 
import Data.Array.Base (unsafeRead, unsafeWrite) 
import Data.Array.ST 
import Control.Monad.ST 

myqsort :: STUArray s Int Int -> Int -> Int -> ST s() 
myqsort a lo hi 
    | lo < hi = do 
     let lscan p h i 
       | i < h = do 
        v <- unsafeRead a i 
        if p < v then return i else lscan p h (i+1) 
       | otherwise = return i 
      rscan p l i 
       | l < i = do 
        v <- unsafeRead a i 
        if v < p then return i else rscan p l (i-1) 
       | otherwise = return i 
      swap i j = do 
       v <- unsafeRead a i 
       unsafeRead a j >>= unsafeWrite a i 
       unsafeWrite a j v 
      sloop p l h 
       | l < h = do 
        l1 <- lscan p h l 
        h1 <- rscan p l1 h 
        if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1 
       | otherwise = return l 
     piv <- unsafeRead a hi 
     i <- sloop piv lo hi 
     swap i hi 
     myqsort a lo (i-1) 
     myqsort a (i+1) hi 
    | otherwise = return() 


genlist gen = runST $ do 
    arr <- newListArray (0,2^22-1) $ take (2^22) (randoms gen) 
    myqsort arr 0 (2^22-1) 
    let collect acc 0 = do 
      v <- unsafeRead arr 0 
      return (v:acc) 
     collect acc i = do 
      v <- unsafeRead arr i 
      collect (v:acc) (i-1) 
    collect [] (2^22-1) 

main = do 
    gen <- newStdGen 
    putStrLn $ show $ sum $ genlist gen 

является достаточно быстрым и использует меньше памяти. Он по-прежнему использует много памяти для списка, 2 Int s берет 32MB хранилище raw (с 64-битным Int s), со списком накладных расходов на пять слов на элемент, что составляет до ~ 200 МБ, но меньше чем половина оригинала.

Answer 2

Это взято из книги Ричарда Берда, Жемчужины функционального алгоритма проектирования, (хотя я должен был изменить это немного, так как код в книге не компилировался точно так же, как написано).

import Data.Array(Array,accumArray,assocs) 

sort :: [Int] -> [Int] 
sort xs = concat [replicate k x | (x,k) <- assocs count] 
     where count :: Array Int Int 
       count = accumArray (+) 0 range (zip xs (repeat 1)) 
       range = (0, maximum xs) 

Он работает путем создания массива индексируются целых чисел, где значения являются количество раз, каждое целое число встречается в списке. Затем он создает список индексов, повторяя их столько же раз, сколько они произошли в исходном списке в соответствии с подсчетами.

Следует отметить, что он линейный с максимальным значением в списке, а не длиной списка, поэтому список, такой как [ 2^x | x <- [0..n] ], не будет сортироваться линейно.

Answer 3

Я бы рассмотрел использование векторов вместо списков для этого, так как списки имеют много служебных данных для каждого элемента, в то время как незаблокированный вектор по существу является просто смежным блоком байтов. Пакет vector-algorithms содержит различные алгоритмы сортировки, которые вы можете использовать для этого, включая radix sort, что, как я полагаю, должно быть хорошо в вашем случае.

Вот простой пример, хотя может быть хорошей идеей сохранить результат в векторной форме, если вы планируете продолжить обработку на нем.

import qualified Data.Vector.Unboxed as V 
import qualified Data.Vector.Algorithms.Radix as R 

sort :: [Int] -> [Int] 
sort = V.toList . V.modify R.sort . V.fromList 

Кроме того, я подозреваю, что значительная часть времени выполнения вашего примера поступает из генератора случайных чисел, так как стандарт один точно не известна для его выполнения. Вы должны убедиться, что вы выбираете только часть сортировки, и если вам нужно много случайных чисел в вашей программе, в Hackage есть более быстрые генераторы.