需要帮助分析代码和分析结果

我试图做一个功能更有效，但我已最差，我不明白为什么。有人能看出原因并向我解释吗？需要帮助分析代码和分析结果

原来的功能：

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

来源

2012-01-08 ePak

请注意，只要不强制第二个参数，您就可以“提早退出”懒惰的折叠器。 – ehird 2012-01-08 05:59:18

当我用一个中等大小的字符串测试它们时，我看到两个函数之间有不同的结果：https：//gist.github.com/75d265248de0e0546174 – 2012-01-08 07:33:41

@ehird：是的，我打算说'foldl'，我会看一看我是否可以在我的情况下使用'foldr'。 – ePak 2012-01-08 09:14:53

可悲的事实是，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"的第一个版本稍微好一些（这里），对于上面的邪恶示例来说，它更好。

来源

2012-01-08 11:17:21

感谢您的详细解释以及如何改善此问题的提示，现在我明白我已将其搞砸了。 – ePak 2012-01-09 09:31:42

需要帮助分析代码和分析结果

回答

相关问题