sorting - `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 ()

运行:

数据列表:

./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 个字节
GC 期间复制了 2,248,105,704 个字节
552,350,688 字节最大驻留(5 个样本)
3,390,456 字节最大斜率
1168 MB 总内存正在使用(0 MB 由于碎片丢失)

第 0 代:3772 次收集，0 次并行，1.44s，1.48s 已过
第 1 代:5 次收集，0 次并行，0.90s，1.13s 已过

初始化时间 0.00s(经过 0.00s)
MUT 时间 0.82s(经过 0.84s)
GC时间2.34s(经过2.61s)
退出时间 0.00s(经过 0.00s)
总时间 3.16s(经过 3.45s)

%GC 时间 74.1%(经过 75.7%)

分配速率 2,522,515,156 字节/MUT 秒

生产力占总用户的 25.9%，占总使用时间的 23.7%

数据堆:

./lazyTest 堆 +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 个字节
GC 期间复制了 237,093,320 个字节
80,031,376 字节最大驻留(2 个样本)
745,368 字节最大斜率
78 MB 总内存在使用(0 MB 由于碎片丢失)

第 0 代:338539 个集合，0 个并行，1.24s，1.31s 已过
第 1 代:2 次收集，0 次并行，0.00s，0.00s 已过

初始化时间 0.00s(经过 0.00s)
MUT时间35.24s(经过35.46s)
GC时间1.24s(经过1.31s)
退出时间 0.00s(经过 0.00s)
总时间 36.48s(经过 36.77s)

%GC 时间 3.4%(经过 3.6%)

分配速率 5,038,907,812 字节/MUT 秒

总用户的 96.6%，总使用时间的 95.8%

显然 limitSortL 快得多，但它也非常消耗内存。在较大的列表中，它达到了 RAM 大小。

有没有更快的算法来解决这个问题，而且不是那种内存不足的问题？

编辑 :澄清:我使用来自 heaps 包的 Data.Heap，我没有尝试 heap 包。

Answer 1

所以，我实际上已经设法解决了这个问题。这个想法是抛弃花哨的数据结构并手工工作;-)
本质上，我们将输入列表分成 block ，对它们进行排序，然后折叠 [[Int]]列表，选择 n每一步的最小元素。
棘手的部分是以适当的方式将累加器与排序 block 合并。我们必须使用 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时间:

列表 3.96s 1168 MB 75 %
堆 35.29s 78 MB 3.6 %
合并 1.00s 78 MB 3.0 %
just rxs 0.21s 78 MB 0.0 % - 只是评估随机向量