findSubstrings ve breakSubstring içinde Data.ByteString

Question

Data/ByteString.hs kaynağında findSubstrings işlevinin breakSubstring lehine reddedildiğini belirtir. Ancak KMP algoritması kullanılarak uygulanan findSubstrings'un, naif olan breakSubstring'da kullanılan algoritmadan çok daha verimli olduğunu düşünüyorum. Bunun neden yapıldığına dair bir fikri olan var mı?

İşte eski uygulama görebilirsiniz:

{-# DEPRECATED findSubstrings "findSubstrings is deprecated in favour of breakSubstring." #-} 

{- 
{- This function uses the Knuth-Morris-Pratt string matching algorithm. -} 

findSubstrings pat@(PS _ _ m) str@(PS _ _ n) = search 0 0 
where 
    patc x = pat `unsafeIndex` x 
    strc x = str `unsafeIndex` x 

    -- maybe we should make kmpNext a UArray before using it in search? 
    kmpNext = listArray (0,m) (-1:kmpNextL pat (-1)) 
    kmpNextL p _ | null p = [] 
    kmpNextL p j = let j' = next (unsafeHead p) j + 1 
        ps = unsafeTail p 
        x = if not (null ps) && unsafeHead ps == patc j' 
          then kmpNext Array.! j' else j' 
        in x:kmpNextL ps j' 
    search i j = match ++ rest -- i: position in string, j: position in pattern 
    where match = if j == m then [(i - j)] else [] 
      rest = if i == n then [] else search (i+1) (next (strc i) j + 1) 
    next c j | j >= 0 && (j == m || c /= patc j) = next c (kmpNext Array.! j) 
      | otherwise = j 
-} 

Ve burada yeni naif bir: değişim için

findSubstrings :: ByteString --^String to search for. 
      -> ByteString --^String to seach in. 
      -> [Int] 
findSubstrings pat str 
    | null pat   = [0 .. length str] 
    | otherwise  = search 0 str 
where 
    STRICT2(search) 
    search n s 
     | null s    = [] 
     | pat `isPrefixOf` s = n : search (n+1) (unsafeTail s) 
     | otherwise   =  search (n+1) (unsafeTail s) 

Answer 1

nedeni KMP uygulanması aslında naif sürümden daha verimsiz olmasıydı, performansa bir gözle uygulanmaktadır.