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

Question

Есть ли какая-либо функция в библиотеках haskell, которая сортирует целые числа за O (n) времени ?? [Под 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

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

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

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

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

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

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

---

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

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

Я бы рассмотрел использование векторов вместо списков для этого, так как списки имеют много накладных расходов на элемент, в то время как распакованный вектор - это просто непрерывный блок байтов.Пакет vector-алгоритмы содержит различные алгоритмы сортировки, которые вы можете использовать для этого, включая 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 есть более быстрые генераторы.

Answer 2

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

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

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

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 ^{22 * ​​1010 * Int s занимает 32 МБ памяти (с 64-битным Int s), с объемом служебной информации в списке iirc пять слов на элемент, чтодобавляет до ~ 200 МБ, но меньше половины оригинала.}

Answer 3

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

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] ], не будет отсортирован линейно.