この機能を高速化する可能性はありますか？

Question

は

、私は次の関数スピードアップしようとしています：その性能を強調するために

{-# LANGUAGE BangPatterns #-} 

import Data.Word 
import Data.Bits 
import Data.List (foldl1') 
import System.Random 
import qualified Data.List as L 

data Tree a = AB (Tree a) (Tree a) | A (Tree a) | B (Tree a) | C !a 
    deriving Show 

merge :: Tree a -> Tree a -> Tree a 
merge (C x) _    = C x 
merge _ (C y)    = C y 
merge (A ta) (A tb)   = A (merge ta tb) 
merge (A ta) (B tb)   = AB ta tb 
merge (A ta) (AB tb tc)  = AB (merge ta tb) tc 
merge (B ta) (A tb)   = AB tb ta 
merge (B ta) (B tb)   = B (merge ta tb) 
merge (B ta) (AB tb tc)  = AB tb (merge ta tc) 
merge (AB ta tb) (A tc)  = AB (merge ta tc) tb 
merge (AB ta tb) (B tc)  = AB ta (merge tb tc) 
merge (AB ta tb) (AB tc td) = AB (merge ta tc) (merge tb td) 

を、私はmergeを使用してソート実装しました：

fold ab a b c list = go list where 
    go (AB a' b') = ab (go a') (go b') 
    go (A a')  = a (go a') 
    go (B b')  = b (go b') 
    go (C x)  = c x 

mergeAll :: [Tree a] -> Tree a 
mergeAll = foldl1' merge 

foldrBits :: (Word32 -> t -> t) -> t -> Word32 -> t 
foldrBits cons nil word = go 32 word nil where 
    go 0 w !r = r 
    go l w !r = go (l-1) (shiftR w 1) (cons (w.&.1) r) 

word32ToTree :: Word32 -> Tree Word32 
word32ToTree w = foldrBits cons (C w) w where 
    cons 0 t = A t 
    cons 1 t = B t 

toList = fold (++) id id (\ a -> [a]) 

sort = toList . mergeAll . map word32ToTree 

main = do 
    is <- mapM (const randomIO :: a -> IO Word32) [0..500000] 
    print $ sum $ sort is 

パフォーマンスは、外出先からかなり良い思い付​​い、約2.5xのsortよりも遅い。しかし、私はそれ以上のスピードアップはしていませんでした。いくつかの関数をインライン化し、多くの場所でバン・アノテーションをUNPACKのC !aに挿入しました。この機能をスピードアップする方法はありますか？

Answer 1

あなたは間違いなく多くのサンクを割り当てています。ここで

merge (A ta) (A tb)   = A (merge ta tb) 

あなたはサンク1つの引数、とコンストラクタAを割り当てる：私は、コードを解析する方法を紹介します。 merge ta tbチャンクが強制的に強制終了されると言うことができますか？おそらく、結果のツリーが使用されたときの最後でのみです。それを確実にするために、各Treeコンストラクタの各引数に強打を追加しようとすると、背筋が厳格である：

data Tree a = AB !(Tree a) !(Tree a) | A !(Tree a) | B !(Tree a) | C !a 

次の例：あなたはl-1、shifrR w 1とcons (w.&.1) rのためのサンクを割り当てている。ここ

go l w !r = go (l-1) (shiftR w 1) (cons (w.&.1) r) 

。最初の1つはlとoを比較すると次の反復で強制され、次の反復で3dsunkを強制すると強制されます（wがここで使用されます）。そして3番目のサンクはa bang on r。だから、おそらくこの特定の節はOKです。