生成此數組時產生無限循環

我製作了KMP算法失敗表的實現。生成此數組時產生無限循環

kmp s = b 
    where a = listArray (0,length s-1) s 
      b = 0:list 0 (tail s) 
      list _ [] = [] 
      list n (x:xs) 
      | x==a!n = (n+1):list (n+1) xs 
      | n > 0  = list (b!!(n-1)) (x:xs) 
      | otherwise = 0:list 0 xs

b是一個列表，並b!!(n-1)最後一行是緩慢的，因此，我要加快速度，也做了以下內容。

kmp s = b 
    where a = listArray (0,length s-1) s 
      t = listArray (0,length s-1) b 
      b = 0:list 0 (tail s) 
      list _ [] = [] 
      list n (x:xs) 
      | x==a!n = (n+1):list (n+1) xs 
      | n > 0  = list (t!(n-1)) (x:xs) 
      | otherwise = 0:list 0 xs

注意，唯一的區別是由t!取代b!!並聲明t是從b產生的陣列。

對於相同的輸入，原始代碼具有正確的輸出，但新輸出只輸出<<loop>>。

如何解決這個問題？

來源

2012-12-03 Chao Xu

你的問題是，列表b需要數組t來確定它的結構（長度）。但t需要列表的長度陣列之前，它的存在：

listArray :: Ix i => (i,i) -> [e] -> Array i e 
listArray (l,u) es = runST (ST $ \s1# -> 
    case safeRangeSize (l,u)   of { [email protected](I# n#) -> 
    case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) -> 
    let fillFromList i# xs s3# | i# ==# n# = s3# 
           | otherwise = case xs of 
      [] -> s3# 
      y:ys -> case writeArray# marr# i# y s3# of { s4# -> 
        fillFromList (i# +# 1#) ys s4# } in 
    case fillFromList 0# es s2#   of { s3# -> 
    done l u n marr# s3# }}})

正如你所看到的，第一個適當大小的原始數組分配，則充滿了arrEleBottom（這是一個error呼叫與消息未定義的數組元素），然後遍歷列表並將列表元素寫入數組（列表元素可以毫無問題地引用數組值）。最後，數組被凍結。在數組被凍結之前，它不能從填充代碼之外訪問（它基本上是一個ST s計算）。

修復它是IMO在ST s單子使用一個可變的陣列的最簡單方式，

kmp s = elems b 
    where 
    l = length s - 1 
    a = listArray (0, l) s 
    b = runSTArray $ do 
      t <- newArray_ (0,l) 
      writeArray t 0 0 
      let fill _ _ [] = return t 
       fill i n (x:xs) 
       | x == a!n = do 
         writeArray t i (n+1) 
         fill (i+1) (n+1) xs 
       | n > 0 = do 
         k <- readArray t (n-1) 
         fill i k (x:xs) 
       | otherwise = do 
         writeArray t i 0 
         fill (i+1) 0 xs 
      fill 1 0 (tail s)

是一個非常直接的（和位低效）代碼的翻譯。

來源

2012-12-03 03:40:14

該算法的教科書命令版本（參見例如CLRS）僅使用數組的懶惰構造直接轉換爲快速版本（無「O（n^2）」查找）。另外，Bird的書「功能算法設計珍珠」有一個KMP的推導，它不使用數組，但是這肯定與OP的算法看起來有很大的不同。 – Fixnum

@Fixnum'STArray'版本中沒有O（n2），它是我知道的教科書算法的未優化版本，非常線性。當然，將數組轉換爲一個列表後效率不高，應該使用數組[實際上，應該從開始使用unboxed數組]。 –

對不起！我指的是OP對列表索引的抱怨，我錯誤地認爲這會導致漸近放緩。我只是想指出，你可以消除沒有可變數組的'（!!）'，並且對OP代碼的侵入性更小）。 – Fixnum

這並不直接回答你的問題，但給出了比使用STArray s的建議版本更簡單的修復方法。

算法的當務之急版本直接轉化爲不使用重複列表索引或狀態，只是懶惰陣列結構的一個版本：

import Data.Array.IArray 

kmp :: String -> Array Int Int 
kmp s = b 
    where 
    a :: Array Int Char 
    a = listArray (0,l-1) s 
    b = listArray (1,l) (0:map (\q -> f (b!(q-1)) q) [2..l]) 
    f k q 
     | k > 0 && (a ! k) /= (a ! (q-1)) = 
     f (b ! k) q 
     | a ! k == a ! (q-1) = k + 1 
     | otherwise = k 
    l = length s

不過，我還沒有這個基準。

來源

2012-12-03 06:49:09 Fixnum

生成此數組時產生無限循環

回答

相關問題