大きなリスト（またはベクトル）をソートする割り当てを減らす

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 ] 

リストには、通常、数千の要素が含まれています。 take n . List.sortBy (flip $ Ord.comparing id)をreturn . List.maximumに置き換えると、私の生産性は60％から95％になるので、リストの並べ替えが原因だと思います。

割り当てを減らすためにできることはありますか？

更新

推奨されているように、私はvector-algorithmsからのインプレースの並べ替えではlist.sortを置き換えます。 おそらく私は間違っていますが、私が見ていることは割り当てがありません（リストでは63％に対して生産性は97％ですが）、プログラムは何倍も遅くなります。リストでは85秒で実行されます。並び替え;私はそれを殺しました 7分待ってからそれを殺しました。私はイントロとマージの両方の種類を試しました。ここに私のコードです：

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

並べ替えは実​​際には多くの割り当てが発生するように見えます。ソートはリスト上で実行されますが、リストをソートすると多くの中間リストが作成されるため、完全に変更することはできません。必要であれば、効率的なソートアルゴリズムを提供する例えばvector-algorithmsパッケージを使用して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）それから、各自のキーを調べます。マップにあるキーだけを検索するので、デフォルトを使用することはありません。 flip $ Ord.comparing idでidをより読み（そしておそらく、より効率的）になるアイデンティティ機能、などが実際にされている場合は、

(d,zt_d) <- IntMap.assocs m 

：はるかに効率的には、マップの1つのトラバーサルにキー/値ペアのリストを作成することですsortBy (flip compare)。

加算された要素のタイプ（場合によっては最適化レベル）によっては、sumの代わりにData.List.foldl' (+) 0を使用する方がよい場合があります。