コードとプロファイリングの結果を分析する際に助けが必要です

Question

私は機能をより効率的にしようとしていますが、私はそれを最悪にしました。誰かがなぜそれを見て、私に説明してもらえますか？

オリジナル機能：

total time =  3.14 secs (157 ticks @ 20 ms) 
    total alloc = 1,642,067,360 bytes (excludes profiling overheads) 

COST CENTRE     MODULE    %time %alloc 

doInsert      Main     95.5 92.1 
insertInits     Main     2.5 7.8 
substringsSB'     Main     1.9 0.0 


                           individual inherited 
COST CENTRE    MODULE            no. entries %time %alloc %time %alloc 

MAIN      MAIN             1   0 0.0 0.0 100.0 100.0 
main     Main             280   1 0.0 0.0 100.0 100.0 
    substringsSB   Main             281   1 0.0 0.0 100.0 100.0 
    substringsSB'   Main             282   1 1.9 0.0 100.0 100.0 
    doInsert    Main             285  1233232 95.5 92.1 95.5 92.1 
    insertInits   Main             284  1570 2.5 7.8  2.5 7.8 
    substrings'   Main             283   1 0.0 0.0  0.0 0.0 
CAF      GHC.IO.Handle.FD          211   3 0.0 0.0  0.0 0.0 
CAF      GHC.IO.Encoding.Iconv        169   2 0.0 0.0  0.0 0.0 
CAF      GHC.Conc.Signal          166   1 0.0 0.0  0.0 0.0 

私の知る限りでは、我々は 倍 foldlに早期の出口を持つことができませんので、機能を過ごすことができます

substringsSB s = substringsSB' Set.empty s 
substringsSB' m s = substrings' m s 
    where 
    substrings' m s = {-# SCC "substrings'" #-}if (Set.member s m) then m else foldl' insertInits m (init . B.tails $ s) 
    insertInits m s = {-# SCC "insertInits" #-}if (Set.member s m) then m else foldl' doInsert m (tail . B.inits $ s) 
    doInsert m k = {-# SCC "doInsert" #-}Set.insert k m 

結果をプロファイリング多くの時間はSet.member s mとなり、mはsubstrings'に戻ります。

substringsSB s = substringsSB' Set.empty s 
substringsSB' m str = substrings' m (init . B.tails $ str) 
    where 
    substrings' m [] = m 
    substrings' m (s:ss) | Set.member s m = m 
         | otherwise  = {-# SCC "substrings'" #-}substrings' insertTail ss 
         where insertTail = insertInits m $ reverse $ (tail . B.inits $ s) 
    insertInits m [] = m 
    insertInits m (s:ss) | Set.member s m = m 
         | otherwise  = {-# SCC "insertInits" #-}insertInits (doInsert s m) ss 
    doInsert k m = {-# SCC "doInsert" #-}Set.insert k m 

プロファイリング結果：

total time =  5.16 secs (258 ticks @ 20 ms) 
    total alloc = 1,662,535,200 bytes (excludes profiling overheads) 

COST CENTRE     MODULE    %time %alloc 

doInsert      Main     54.7 90.5 
substringsSB'     Main     43.8 9.5 
insertInits     Main     1.6 0.0 


                           individual inherited 
COST CENTRE    MODULE            no. entries %time %alloc %time %alloc 

MAIN      MAIN             1   0 0.0 0.0 100.0 100.0 
main     Main             280   1 0.0 0.0 100.0 100.0 
    substringsSB   Main             281   1 0.0 0.0 100.0 100.0 
    substringsSB'   Main             282   1 43.8 9.5 100.0 100.0 
    doInsert    Main             285  1225600 54.7 90.5 54.7 90.5 
    insertInits   Main             284  1225600 1.6 0.0  1.6 0.0 
    substrings'   Main             283  1568 0.0 0.0  0.0 0.0 
CAF      GHC.IO.Handle.FD          211   3 0.0 0.0  0.0 0.0 
CAF      GHC.IO.Encoding.Iconv        169   2 0.0 0.0  0.0 0.0 
CAF      GHC.Conc.Signal          166   1 0.0 0.0  0.0 0.0 

しかし、このオリジナル版よりも時間がかかるので、私は、再帰を使用する関数を変換しました。 なぜそれは多くの時間をsubstringsSB'に費やしていますか？ また、私は間違いを犯しましたが、これらの2つの機能は論理的に同等ではありませんか？ 入力と

main = do 
    s <- getLine 
    let m = substringsSB $ B.pack s 
    print $ Set.size m 
    return() 

：

asjasdfkjasdfjkasdjlflaasdfjklajsdflkjasvdadufhsaodifkljaiduhfjknhdfasjlkdfndbhfisjglkasnjjfgklsadmsjnhsjdflkmsnajjkdlsmfnjsdkfljasd;fjlkasdjfklasjdfnasdfjjnsadfjsadfhasjdfjlaksdfjlkasdfjljkasdflasidfjlaisjdflaisdjflaisjdfliasjdgfouqhagdfsia;klsjdfnklajsdfkhkasfhjdasdfhaskdflhjaklsdfh;kjlasdfh;jlaksdflkhajsdfkjahsdfkjhasdfkkasdfkjlkasfdkljasdfkhljkasdkflkjasdfasdlfkajsdlfkjaslkdfjjaksdjgujhgjhghjbjnbghjghhgfghfghvfgfgjhgjhdfjfjhgfjgvjhgvjhgvjhgvjhgvjhgvjhasdkfjkasdjfklajsdfklkahsdfjklhjklhghjhkhgfvcghjkjhghjkjhhvjkl/ljklkjlkjlkjlkjaslkdfjasd;lkfjas;dlfkjas;dflkjas;dflkjas;dflkjas;dflkja;slkdfja;sdlkjfa;sdlkfja;lsdfkjas;ldkfja;sdlkfja;skldfja;slkdjfa;slkdfja;sdklfjas;dlkfjas;dklfjas;dlkfjas;dfkljas;dflkjas;lkdfja;sldkfj;aslkdfja;sldkfja;slkdfj;alksdjf;alsdkfj;alsdkfja;sdflkja;sdflkja;sdlfkja;sdlfkja;sldkfja;sdlkfja;sldfkj;asldkfja;sldkfja;lsdkfja;sldfkja;sdlfjka;sdlfjkas;dlkfjas;ldkfjas;dlfkjasfd;lkjasd;fljkads;flkjasdf;lkjasdf;lkajsdf;lkajsdf;aksljdf;alksjdfa;slkdjfa;slkdjfa;slkdfja;sdflkjas;dflkjasd;flkjasd;flkjasdf;lkjasdf;ljkasdf;lkajdsf;laksjf;asldfkja;sdfljkads;flkjasd;fljkasdf;lkjasdf;ljkadfs;fljkadfs;ljkasdf;lajksdf;lkajsdf;lajsfd;laksdfgvjhgvjhgvjhcfjhgcjfgvjkgvjjgfjghfhgkhkjhbkjhbkjhbkybkkugtkydfktyufctkyckxckghfvkuygjkhbykutgtvkyckjhbliuhgktuyfkvuyjbjkjygvkuykjdjflaksdjflkajsdlkfjalskdjflkasjdflkjasdlkfjalksdjfklajsdflkjasdlkjfalksdjflkasjdflkjasdlfkjaslkdjflaksjdflkajsdlfkjasdlkfjalsdjflkasjdflkasjdflajsdfjsfuhaduvasdyhaweuisfnaysdfiuhasfdnhaksjdfahsdfiujknsadfhbaiuhdfjknahbdshfjksnashdfkjnsadfiukjfnhsdfkjnasdfikjansdfhnaksdjfaisdfkn 

Answer 1

悲しい真実はSet.memberがあまりにも高価であるということです。

最初のバージョンでは、以前に見たことがある場合は各テールをチェックし、そうであればそれを無視し、そうでない場合は空でないすべてのイニットを挿入します。入力が十分に不規則であれば、O（n）メンバーシップ検定とO（n^2）挿入、O（n^2 * log n）（O（1）の比較の平均コストを仮定）入力が周期的に最短（正）の期間pである場合、最初のpテールだけが挿入につながるので、O（n）テストとO（p * n）挿入、O（p * n * log n） P> 1の場合はO（p）まで、p == 1ならO（n）までである可能性がありますが、期間自体が不規則な場合、比較のためのO（1）は問題ありません） 。第二に

、

substringsSB s = substringsSB' Set.empty s 
substringsSB' m str = substrings' m (init . B.tails $ str) 
    where 
    substrings' m [] = m 
    substrings' m (s:ss) | Set.member s m = m 
         | otherwise  = substrings' insertTail ss 
          where 
          insertTail = insertInits m $ reverse $ (tail . B.inits $ s) 

それは前に見てきたのであれば停止する場合は、それぞれの尾をチェック。それは良いですが、最初のものをあまり上回ることはありません最初に、前に尾が見えている場合は、それ以前のすべての尻尾も見ていますので、ほとんどのO（n）ログn）操作。通常の不規則な入力に対しては、以前に見られた最短のテールのほんの少数だけがスキップされます。

insertInits m [] = m 
    insertInits m (s:ss) | Set.member s m = m 
         | otherwise  = insertInits (doInsert s m) ss 
    doInsert k m = {-# SCC "doInsert" #-}Set.insert k m 

尾は（通常の）まだ見ていない場合は、あなたがそののINITを挿入を開始 - 最長からの最短 - いずれかが前に見られた場合には破壊（そして、すべての短い方のINITも前に見てきたので） 。多くの長いinitsが複数回出現するなら、それは素晴らしいことですが、そうでなければO（n^2）の追加メンバーシップテストしかありません。

通常の不規則な入力では、長い部分文字列は何度も出ますが、いくつかの短い部分文字列はありません。いくつかの短い部分文字列は追加のメンバシップテストを補うものではありません。 （メンバシップテストは挿入よりも安いので、係数は2未満である必要があります）。

第1の方法でも不要な挿入が回避され、2番目のテストは外部ループにO（n）テストを保存しますが、 O（p * n）は内部ループでテストされ、不規則な場合よりもわずかに悪くなります。

しかし、一部の入力ではですが、2番目の方法は劇的に優れています。の最初のバージョンに、それは近いもたらすこと

substringsSB str = go 0 Set.empty (init $ B.tails str) 
    where 
    go sz m (s:ss) 
     | Set.member s m = m 
     | otherwise  = go nsz nm ss 
      where 
      (nsz,nm) = insInits sz m (reverse . tail $ B.inits s) 
    go _ m [] = m 
    insInits sz m (s:ss) 
     | sz1 == sz  = (sz,m) 
     | otherwise  = insInits sz1 nm ss 
      where 
      nm = Set.insert s m 
      sz1 = Set.size nm 
    insInits sz m [] = (sz,m) 

、両方

main = do 
    let x = substringsSB $ B.pack $ replicate 9999 97 ++ [98] 
    print (Set.size x) 

のためにあなたは、挿入後に安いsize比較して、挿入する前に、高価なmemberを置き換えることにより第2のバージョンを向上させることができます試してみてください一般的なケースでは、concat $ replicate n "abcde"の最初のバージョンよりも若干良い（ここに）改善され、上記の悪い例のほうがはるかに優れています。