减少大列表(或向量)的分配排序

Question

我正在努力减少程序中的GC时间。主要可疑代码如下：

Data.Vector.Unboxed.fromList . take n . List.sortBy (flip $ Ord.comparing id) 
 $ [ ( sum [ (c + a) * wsum z | (z,c) <- IntMap.toList zt_d ] , d)
   | d <- IntMap.keys $ m
   , let zt_d = IntMap.findWithDefault IntMap.empty d $ m ]

正在排序的列表通常包含数千个元素。我认为列表排序是罪魁祸首，因为如果我用return . List.maximum替换take n . List.sortBy (flip $ Ord.comparing id)，我的生产率就会从60%提高到95%。

我能做些什么来减少这里的分配吗？

更新

按照建议，我将List.sort替换为来自vector-algorithms的就地排序。也许我做错了，但我看到的是没有分配（生产力为97%，而列表为63%），但程序慢了很多倍：使用List.sortBy只需85秒；我当场就杀了它等待7分钟。我同时尝试了Intro和Merge排序。这是我的代码：

import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Algorithms.Merge as Sort
import qualified Data.Vector.Fusion.Stream as Stream
import Control.Monad.ST   
sortBy :: (Ord a, U.Unbox a) => (a -> a -> Ordering) -> [a] -> U.Vector a
sortBy cmp xs = runST $ do
  mv  <- GM.unstream . Stream.fromList $ xs
  Sort.sortBy cmp mv
  G.unsafeFreeze mv

Answer 1

排序看起来确实会导致大量分配。虽然排序是在列表上执行的，但这不能完全改变，因为排序列表会导致构建许多中间列表。如果需要，您可以尝试在MVector上进行排序，例如使用提供高效排序算法的矢量算法包。

然而，在中，效率低下的情况会导致更多的分配

Data.Vector.Unboxed.fromList . take n . List.sortBy (flip $ Ord.comparing id) 
 $ [ ( sum [ (c + a) * wsum z | (z,c) <- IntMap.toList zt_d ] , d)
   | d <- IntMap.keys $ m
   , let zt_d = IntMap.findWithDefault IntMap.empty d $ m ]

当你写

d <- IntMap.keys m, let zt_d = IntMap.findWithDefault IntMap.empty d m
-- The '$' are unnecessary, I left them out

您需要1）遍历整个地图以收集关键点列表，2）然后查找每个关键点本身。由于您只查找地图中存在的关键点，因此永远不会使用默认值。更有效的方法是在映射的一次遍历中创建键/值对列表：

(d,zt_d) <- IntMap.assocs m

那么，如果flip $ Ord.comparing id中的id确实是身份函数，那么它将与sortBy (flip compare)一样更可读（并且可能更高效）。

根据求和元素的类型（可能还有优化级别），最好使用Data.List.foldl' (+) 0而不是sum。