डेटा में बाइटस्ट्रिंग और ब्रेकसस्ट्रिंग ढूंढें। बाइटस्ट्रिंग

Question

Data/ByteString.hs के स्रोत में यह कहता है कि findSubstrings फ़ंक्शन breakSubstring के पक्ष में बहिष्कृत कर दिया गया है। हालांकि मुझे लगता है कि 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) 

Answer 1

बदलाव का कारण वास्तव में अनुभवहीन संस्करण की तुलना में अधिक अक्षम था कि KMP के कार्यान्वयन था, जो प्रदर्शन पर नजर के साथ लागू किया जाता है।