在Data.ByteString中的findSubstrings和breakSubstring

Question

在Data.ByteString中的findSubstrings和breakSubstring

haskellperformancestring-matchingbytestring

6

在Data/ByteString.hs的源代码中，它说函数findSubstrings已被弃用，推荐使用breakSubstring。然而，我认为使用KMP算法实现的findSubstrings比breakSubstring使用的朴素算法更加高效。有人知道为什么会这样吗？

下面是旧实现的代码：

{-# 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
-}

这里是新的幼稚版本：

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)

- sob7y

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Don Stewart · Accepted Answer

更改的原因是KMP算法的实现实际上比朴素版本更加低效，而朴素版本则是为了提高性能而实现的。