Эффективный для памяти алгоритм для задачи `take n (sort xs)` ("sorted prefix")

Question

Я хочу взять n самых больших элементов из ленивого списка.

Я слышал, что сортировка слиянием, реализованная в Data.List.sort, является ленивой и не производит больше элементов, чем необходимо. Это может быть правдой с точки зрения сравнений, но, безусловно, это не относится к использованию памяти. Следующая программа иллюстрирует проблему:

{-# LANGUAGE ScopedTypeVariables #-}

module Main where

import qualified Data.Heap as Heap
import qualified Data.List as List

import System.Random.MWC
import qualified Data.Vector.Unboxed as Vec

import System.Environment

limitSortL n xs = take n (List.sort xs)
limitSortH n xs = List.unfoldr Heap.uncons (List.foldl' (\ acc x -> Heap.take n (Heap.insert x acc) ) Heap.empty xs) 

main = do
  st <- create
  rxs :: [Int] <- Vec.toList `fmap` uniformVector st (10^7)

  args <- getArgs
  case args of
    ["LIST"] -> print (limitSortL 20 rxs)
    ["HEAP"] -> print (limitSortH 20 rxs)

  return ()

Runtime:

Data.List:

./lazyTest LIST +RTS -s 
[-9223371438221280004,-9223369283422017686,-9223368296903201811,-9223365203042113783,-9223364809100004863,-9223363058932210878,-9223362160334234021,-9223359019266180408,-9223358851531436915,-9223345045262962114,-9223343191568060219,-9223342956514809662,-9223341125508040302,-9223340661319591967,-9223337771462470186,-9223336010230770808,-9223331570472117335,-9223329558935830150,-9223329536207787831,-9223328937489459283]
   2,059,921,192 bytes allocated in the heap
   2,248,105,704 bytes copied during GC
     552,350,688 bytes maximum residency (5 sample(s))
       3,390,456 bytes maximum slop
            1168 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  3772 collections,     0 parallel,  1.44s,  1.48s elapsed
  Generation 1:     5 collections,     0 parallel,  0.90s,  1.13s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.82s  (  0.84s elapsed)
  GC    time    2.34s  (  2.61s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    3.16s  (  3.45s elapsed)

  %GC time      74.1%  (75.7% elapsed)

  Alloc rate    2,522,515,156 bytes per MUT second

  Productivity  25.9% of total user, 23.7% of total elapsed

Data.Heap:

./lazyTest HEAP +RTS -s 
[-9223371438221280004,-9223369283422017686,-9223368296903201811,-9223365203042113783,-9223364809100004863,-9223363058932210878,-9223362160334234021,-9223359019266180408,-9223358851531436915,-9223345045262962114,-9223343191568060219,-9223342956514809662,-9223341125508040302,-9223340661319591967,-9223337771462470186,-9223336010230770808,-9223331570472117335,-9223329558935830150,-9223329536207787831,-9223328937489459283]
 177,559,536,928 bytes allocated in the heap
     237,093,320 bytes copied during GC
      80,031,376 bytes maximum residency (2 sample(s))
         745,368 bytes maximum slop
              78 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 338539 collections,     0 parallel,  1.24s,  1.31s elapsed
  Generation 1:     2 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   35.24s  ( 35.46s elapsed)
  GC    time    1.24s  (  1.31s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   36.48s  ( 36.77s elapsed)

  %GC time       3.4%  (3.6% elapsed)

  Alloc rate    5,038,907,812 bytes per MUT second

  Productivity  96.6% of total user, 95.8% of total elapsed

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

Существует ли более быстрый алгоритм для решения этой проблемы, который не требует много памяти?

Редактировать : Уточнение: я использую Data.Heap из кучи, я не пробовал пакет кучи.

Answer 1

Итак, мне действительно удалось решить проблему. Идея состоит в том, чтобы отбросить причудливые структуры данных и работать вручную ;-) По сути, мы разбиваем входной список на куски, сортируем их и сворачиваем список [[Int]], выбирая n наименьшие элементы на каждом шаге. Часть хитрости - это правильное слияние аккумулятора с отсортированным фрагментом. Мы должны использовать seq, иначе лень укусит вас, и результат все еще требует много памяти для вычисления. Кроме того, я смешиваю слияние с take n, просто чтобы оптимизировать вещи. Вот вся программа вместе с предыдущими попытками:

{-# LANGUAGE ScopedTypeVariables, PackageImports #-}     
module Main where

import qualified Data.List as List
import qualified Data.List.Split as Split
import qualified "heaps" Data.Heap as Heap -- qualified import from "heaps" package

import System.Random.MWC
import qualified Data.Vector.Unboxed as Vec

import System.Environment

limitSortL n xs = take n (List.sort xs)
limitSortH n xs = List.unfoldr Heap.uncons (List.foldl' (\ acc x -> Heap.take n (Heap.insert x acc) ) Heap.empty xs)
takeSortMerge n inp = List.foldl' 
                        (\acc lst -> (merge n acc (List.sort lst))) 
                        [] (Split.splitEvery n inp)
    where
     merge 0 _ _ = []
     merge _ [] xs = xs
     merge _ ys [] = ys
     merge f (x:xs) (y:ys) | x < y = let tail = merge (f-1) xs (y:ys) in tail `seq` (x:tail) 
                           | otherwise = let tail = merge (f-1) (x:xs) ys in tail `seq` (y:tail)


main = do
  st <- create

  let n1 = 10^7
      n2 = 20

  rxs :: [Int] <- Vec.toList `fmap` uniformVector st (n1)

  args <- getArgs

  case args of
    ["LIST"] ->  print (limitSortL n2 rxs)
    ["HEAP"] ->  print (limitSortH n2 rxs)
    ["MERGE"] -> print (takeSortMerge n2 rxs)
    _ -> putStrLn "Nothing..."

  return ()

Производительность при работе, потребление памяти, время GC: * ​​1008 *

LIST       3.96s   1168 MB    75 %
HEAP       35.29s    78 MB    3.6 %
MERGE      1.00s     78 MB    3.0 %
just rxs   0.21s     78 MB    0.0 %  -- just evaluating the random vector

Answer 2

Существует множество алгоритмов выбора , специализирующихся именно на этом. Алгоритм на основе разделов является «классическим», но, как и Quicksort, он не очень подходит для списков на Haskell. В википедии мало что рассказывается о функциональном программировании, хотя я подозреваю, что описанный «выбор турнира» такой же или не очень отличается от вашего текущего решения слияния.

Если вас беспокоит потребление памяти, вы можете использовать очередь с приоритетами - она ​​использует O (K) памяти и общее время O (N * logK):

queue := first k elements
for each element in the rest:
    add the element to the queue
    remove the largest element from the queue
convert the queue to a sorted list

Answer 3

«Быстрая сортировка и k-е наименьшие элементы» Генриха Апфельмуса: http://apfelmus.nfshost.com/articles/quicksearch.html

Answer 4

Извините, если я не могу расшифровать

 Vec.toList `fmap` uniformVector st (10^7)

но как долго будет длиться этот список?Понятно ли, что независимо от того, насколько ленивым является сортировка слиянием, ему по крайней мере придется реализовать весь список?

Обновление:

Я слышал, что сортировка слиянием реализована в Data.List.sortявляется ленивым и не производит больше элементов, чем необходимо.

Это ничего не говорит о потреблении пространства слиянием до того, как он сможет начать доставлять первые элементы списка.В любом случае, ему придется пройтись (и, таким образом, реализовать) весь список, выделить подлежащие объединению подсписки и т. Д. Здесь приведена информация о http://www.inf.fh -flensburg.de / lang /gorithmen / sortieren / merge /mergen.htm

Недостаток функции mergesort заключается в том, что для временного массива ему требуется дополнительное пространство Θ (n).

Существуют различные возможности для реализации функции.слияния.Наиболее эффективным из них является вариант б.Требуется только вдвое меньше дополнительного пространства, он быстрее других вариантов и стабилен.

Answer 5

Эффективность памяти редко имеет силу haskell. Тем не менее, не так сложно создать алгоритм сортировки, который будет более ленивым, чем сортировка слиянием. Например, вот простая быстрая сортировка:

qsort [] = []
qsort (x:xs) = qcombine (qsort a) b (qsort c) where
    (a,b,c) = qpart x (x:xs) ([],[],[])
qpart _ [] ac = ac
qpart n (x:xs) (a,b,c)
    | x > n = qpart n xs (a,b,x:c)
    | x < n = qpart n xs (x:a,b,c)
    | otherwise = qpart n xs (a,x:b,c)
qcombine (a:as) b c = a:qcombine as b c
qcombine [] (b:bs) c = b:qcombine [] bs c
qcombine [] [] c = c

Я использовал явную рекурсию, чтобы было понятно, что происходит. Каждая часть здесь действительно ленива, это означает, что qcombine никогда не позвонит qsort c, если в этом нет необходимости. Это должно уменьшить использование памяти, если вы просто хотите первые несколько элементов.

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

пример такого подхода:

qselect 0 _ = []
qselect n [] = error ("cant produce " ++ show n ++ " from empty list")
qselect n (x:xs)
    | al > n = qselect n a
    | al + bl > n = a ++ take (al - n) b
    | otherwise = a ++ b ++ (qselect (n - al - bl) c) where
        (a,al,b,bl,c,cl) = qpartl x (x:xs) ([],0,[],0,[],0)

qpartl _ [] ac = ac
qpartl n (x:xs) (a,al,b,bl,c,cl)
    | x > n = qpartl n xs (a,al,b,bl,x:c,cl+1)
    | x < n = qpartl n xs (x:a,al+1,b,bl,c,cl+1)
    | otherwise = qpartl n xs (a,al,x:b,bl+1,c,cl)

Опять же, этот код не самый чистый, но я хочу прояснить, что он делает.

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

С другой стороны, если вы хотите получить почти весь список, но не заботитесь о том, чтобы привести его в порядок, вы можете многократно «удалять» самые нижние элементы в списке.

Оба эти подхода и приведенная выше краткая сортировка - это O (n ^ 2), но вам нужно иметь стратегию, которая часто работает в больших O (k * n) и имеет тенденцию не использовать тонну пространство.

Другой вариант - использовать алгоритм сортировки на месте для контроля использования памяти. Я не знаю каких-либо ленивых видов на месте, но если бы они существовали, это было бы идеально.

Answer 6

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

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

Для подхода с изменяемым массивом вы можете ограничить число ходов на вставку n/2 вместо n-1, записав индекс h, который "указывает" на начало очереди, хранящейся в массиве, и разрешивочередь для «обтекания» внутри массива.