需要幫助分析代碼和分析結果

Question

我試圖做一個功能更有效，但我已最差，我不明白爲什麼。有人能看出原因並向我解釋嗎？

原來的功能：

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 

剖析結果：

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，因此函數可以花很多時候只是打電話Set.member s m和substrings'返回m。所以，我轉換的功能，使用遞歸：

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'？ 它只是做init . B.tails $ str其原始版本也呼籲... 還是我犯了一個錯誤，並且這兩個功能都沒有邏輯上等同？

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是太昂貴。

在第一個版本，你檢查每個尾巴，如果以前已經見過，如果是的話，忽略它，否則插入其所有非空inits。如果輸入是非常不規則的，那就是O（n）成員測試和O（n^2）插入，總共O（n^2 * log n）（假設O（1）比較的平均成本）。如果輸入是週期性的，並且週期最短（正）週期p，則只有第一個p尾會導致插入，所以這是O（n）測試和O（p * n）插入，O（p * n * log n）總體有點被騙，用於比較的平均成本可能高達O（p）如果p> 1且爲O（n）如果p == 1，但如果週期本身是不規則的，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）個成員測試，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 

如果尾部尚未見過的（正常的），你就開始將其inits - 從最長到最短 - 打破如有以前已經見過（因爲那時所有的短inits也已經見過） 。如果許多長時間多次出現，這很好，但如果不是這樣，你所擁有的就是O（n^2）次額外的會員測試。

對於普通的不規則輸入沒有長串發生多次，但一些短的那些做，並保存在幾個插入件不補償附加的成員測試，繪製第二方法通過一個常數因子慢。 （會員測試比插入便宜，所以該係數應小於2）

對於週期性輸入，第一種方法也避免了不必要的插入件，所述第二保存在外部循環爲O（n）的測試中，但增加了O（p * n）在內循環中進行測試，使其比在不規則情況下稍差。

但是對於一些輸入，第二種方法可以大大提高。嘗試既爲

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

您可以通過插入後的廉價size比較插入之前免去了昂貴的member提高第二版，

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) 

這使其接近在第一個版本通用的情況下，使得它比concat $ replicate n "abcde"的第一個版本稍微好一些（這裏），對於上面的邪惡示例來說，它更好。