日々の流転

λ. 文字列検索の性能

こないだの ICFP Programming Contest 2007 の時に以下のような文字列検索関数を書いた(実際にはリストではなくData.Sequenceが対象だったけど)。 書いたときは「文字列上を逆に戻ることが無いから、少しは速そう」とか思っていたんだけど、そもそも比較回数は全然減っていないので全然速くない。アホだ、私。

findSubstring :: Eq a => [a] -> [a] -> Maybe Int
findSubstring [] = const (Just 0)
findSubstring pat = f [] 0
  where
    f ([]:_) n _ = Just $ n - length pat
    f s n xs =
        case xs of
          (x:xs') -> f [s' | (c:s') <- (s++[pat]), x==c] (n+1) xs'
          [] -> Nothing

毎日HaskellのKMP法検索(2006-05-03)とBM法検索(2006-06-16)と比較してみる。

Prelude Test> findSubstring (replicate 1000 'a' ++ ['b']) (replicate 10000 'a')
Nothing
(2.54 secs, 253290572 bytes)
Prelude Test> kmp_search (replicate 1000 'a' ++ ['b']) (replicate 10000 'a')
False
(0.03 secs, 525604 bytes)
Prelude Test> bm_search (replicate 1000 'a' ++ ['b']) (replicate 10000 'a')
False
(0.21 secs, 2622592 bytes)

この程度の短い文字列でも最悪ケースだと全然性能が違うんだな。