UINavigationController震动推送过渡(UINavigationController jarring push transition)

 和user5402一样，我很好奇是否等效（对于某些等价的值）C程序会在时限内完成还是超时。 如果愿意的话，看看使用ByteString的等效程序是否可以及时完成将会很有趣。 - 并不是ByteString本身比Text更快，但由于输入必须转换为Text的内部表示，而ByteString按原样转换，这可能会有所不同。 ByteString可能更快的另一个可能原因 - 如果测试机器具有32位GHC - 那么文本的融合至少需要比32位架构上通常可用的寄存器更多才能获得全部利润[很久以前在text-0.5 to text-0.7的日子里，在我的32位盒子里， bytestring过去相当快，不知道是否仍适用于较新的文本版本]。 
 
 好的，既然user5402已经验证了天真的算法在C语言中足够快，那么我就继续使用ByteString编写了一个天真算法的实现。 
 
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C
import qualified Data.ByteString.Unsafe as U
import Control.Monad
import Data.Word

main :: IO ()
main = do
    cl <- C.getLine
    case C.readInt cl of
      Just (cases,_) -> replicateM_ cases (C.getLine >>= print . similarity)
      Nothing -> return ()

-- Just to keep the condition readable.
(?) :: B.ByteString -> Int -> Word8
(?) = U.unsafeIndex

similarity :: B.ByteString -> Int
similarity bs
    | len == 0  = 0
    | otherwise = go len 1
      where
        !len = B.length bs
        go !acc i
            | i < len   = go (acc + prf 0 i) (i+1)
            | otherwise = acc
        prf !k j
            | j < len && bs ? k == bs ? j   = prf (k+1) (j+1)
            | otherwise = k
 
 并在一些不良案例中将其与OP的Text版本进行了比较。 在我的盒子上，这比Text版本快四倍以上，所以有趣的是它是否足够快（C版本是另一个快4.5倍，所以它可能不是）。 
 
 但是，我认为由于使用具有二次最坏情况行为的天真算法，更有可能超出时间限制。 可能有一些测试用例会引起天真算法的最坏情况。 
 
 因此，解决方案是使用可以更好地，最佳地线性扩展的算法。 计算字符串相似性的一种线性算法是Z算法 。 
 
 这个想法很简单（但是，像大多数好主意一样，不容易）。 让我们调用一个（非空）子字符串，它也是字符串前缀子字符串的前缀。 为避免重新计算，该算法使用prefix-substring的窗口，该窗口在当前被认为是最右边扩展的索引之前开始（最初，窗口为空）。 
 
 使用的变量和算法的不变量： 
 
 
 
 i ，正在考虑的索引从1开始（对于基于0的索引;不考虑整个字符串）并且递增到length - 1 
 
 
 left和right ，prefix-substring窗口的第一个和最后一个索引; 不变量： 
  
 
   
 left < i ， left <= right < length(S) ， left > 0或right < 1 ， 
 
   
 如果left > 0 ，那么S[left .. right]是S和S[left .. ]的最大公共前缀， 
 
   
 如果1 <= j < i并且S[j .. k]是S的前缀，则k <= right 
 
  
 
 
 数组Z ，不变量：对于1 <= k < i ， Z[k]包含S[k .. ]和S的最长公共前缀的长度。 
 
 
 算法： 
 
 
 
 设置i = 1 ， left = right = 0 （允许left <= right < 1任何值），并且对于所有索引1 <= j < length(S)设置Z[j] = 0 。 
 
 
 如果i == length(S) ，请停止。 
 
 
 如果i > right ，找到S和S[i .. ]的最长公共前缀的长度l ，将其存储在Z[i] 。 如果l > 0我们发现一个窗口比前一个延伸得更远，那么设置left = i和right = i+l-1 ，否则保持不变。 递增i并转到2。 
 
 
 这里left < i <= right ，所以子串S[i .. right]是已知的 - 因为S[left .. right]是S的前缀，它等于S[i-left .. right-left] 。 
 现在考虑S的最长公共前缀，其中子串从索引i - left开始i - left 。 它的长度是Z[i-left] ，因此S[k] = S[i-left + k] 0 <= k < Z[i-left]和 
 S[Z[i-left]] ≠ S[i-left+Z[i-left]] 。 现在，如果Z[i-left] <= right-i ，则i + Z[i-left]在已知窗口内，因此 
S[i + Z[i-left]] = S[i-left + Z[i-left]] ≠ S[Z[i-left]]
S[i + k]         = S[i-left + k]         = S[k]   for 0 <= k < Z[i-left]
 并且我们看到S和S[i .. ]的最长公共前缀的长度具有长度Z[i-left] 。 然后设置Z[i] = Z[i-left] ，递增i ，然后转到2。 
 否则， S[i .. right]是S的前缀，我们检查它的扩展距离，开始比较right+1和right+1 - i的索引。 让长度为l 。 设置Z[i] = l ， left = i ， right = i + l - 1 ，增加i ，然后转到2。 
 
 
 由于窗口从不向左移动，并且比较总是在窗口结束后开始，因此字符串中的每个字符最多成功一次与字符串中的较早字符进行比较，并且对于每个起始索引，最多只有一个不成功。比较，因此算法是线性的。 
 
 代码（使用ByteString出于习惯，应该简单地移植到Text ）： 
 
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C
import qualified Data.ByteString.Unsafe as U
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Control.Monad
import Data.Word

main :: IO ()
main = do
    cl <- C.getLine
    case C.readInt cl of
      Just (cases,_) -> replicateM_ cases (C.getLine >>= print . similarity)
      Nothing -> return ()

-- Just to keep the condition readable.
(?) :: B.ByteString -> Int -> Word8
(?) = U.unsafeIndex

-- Calculate the similarity of a string using the Z-algorithm
similarity :: B.ByteString -> Int
similarity bs
    | len == 0  = 0
    | otherwise = runST getSim
      where
        !len = B.length bs
        getSim = do
            za <- newArray (0,len-1) 0 :: ST s (STUArray s Int Int)
            -- The common prefix of the string with itself is entire string.
            unsafeWrite za 0 len
            let -- Find the length of the common prefix.
                go !k j
                    | j < len && (bs ? j == bs ? k) = go (k+1) (j+1)
                    | otherwise = return k
                -- The window with indices in [left .. right] is the prefix-substring
                -- starting before i that extends farthest.
                loop !left !right i
                    | i >= len  = count 0 0 -- when done, sum
                    | i > right = do
                        -- We're outside the window, simply
                        -- find the length of the common prefix
                        -- and store it in the Z-array.
                        w <- go 0 i
                        unsafeWrite za i w
                        if w > 0
                          -- We got a non-empty common prefix and a new window.
                          then loop i (i+w-1) (i+1)
                          -- No new window, same procedure at next index.
                          else loop left right (i+1)
                    | otherwise = do
                        -- We're inside the window, so the substring starting at
                        -- (i - left) has a common prefix with the substring
                        -- starting at i of length at least (right - i + 1)
                        -- (since the [left .. right] window is a prefix of bs).
                        -- But we already know how long the common prefix
                        -- starting at (i - left) is.
                        z <- unsafeRead za (i-left)
                        let !s = right-i+1 -- length of known prefix starting at i
                        if z < s
                          -- If the common prefix of the substring starting at
                          -- (i - left) is shorter than the rest of the window,
                          -- the common prefix of the substring starting at i
                          -- is the same. Store it and move on with the same window.
                          then do
                              unsafeWrite za i z
                              loop left right (i+1)
                          else do
                              -- Otherwise, find out how far the common prefix
                              -- extends, starting at (right + 1) == s + i.
                              w <- go s (s+i)
                              unsafeWrite za i w
                              loop i (i+w-1) (i+1)
                count !acc i
                    | i == len  = return acc
                    | otherwise = do
                        n <- unsafeRead za i
                        count (acc+n) (i+1)
            loop 0 0 1

Like user5402, I'd be curious whether an equivalent (for certain values of equivalent) C programme would finish within the time limit or also time out. If it would, it would be interesting to see whether an equivalent programme using ByteStrings could finish in time. - Not that ByteStrings are per se faster than Text, but since the input must be converted to the internal representation of Text while ByteString takes it as is, that might make a difference. Another possible reason that ByteStrings might be faster - if the testing machines have 32-bit GHCs - would be that text's fusion at least used to need more registers than generally available on 32 bit architectures to get full profit [a long time ago, in the days of text-0.5 to text-0.7, on my 32-bit box, bytestring used to be quite a bit faster, no idea whether that still holds for newer text versions].
 
Okay, since user5402 has verified that the naïve algorithm is fast enough in C, I've gone ahead and wrote an implementation of the naïve algorithm using ByteStrings
 
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C
import qualified Data.ByteString.Unsafe as U
import Control.Monad
import Data.Word

main :: IO ()
main = do
    cl <- C.getLine
    case C.readInt cl of
      Just (cases,_) -> replicateM_ cases (C.getLine >>= print . similarity)
      Nothing -> return ()

-- Just to keep the condition readable.
(?) :: B.ByteString -> Int -> Word8
(?) = U.unsafeIndex

similarity :: B.ByteString -> Int
similarity bs
    | len == 0  = 0
    | otherwise = go len 1
      where
        !len = B.length bs
        go !acc i
            | i < len   = go (acc + prf 0 i) (i+1)
            | otherwise = acc
        prf !k j
            | j < len && bs ? k == bs ? j   = prf (k+1) (j+1)
            | otherwise = k
 
and compared it to the OP's Text version on some bad cases. On my box, that is more than four times faster than the Text version, so it'd be interesting whether that's fast enough (the C version is another 4.5 times faster, so it may well not be).
 
However, I consider it more likely that the time limit is exceeded due to using the naïve algorithm that has quadratic worst-case behaviour. Probably there are test cases that evoke the worst-case for the naïve algorithm.
 
So the solution would be to use an algorithm that scales better, optimally linear. One linear algorithm to compute the similarity of a string is the Z-algorithm.
 
The idea is simple (but, like most good ideas, not easy to have). Let us call a (non-empty) substring that is also a prefix of the string a prefix-substring. To avoid recomputation, the algorithm uses a window of the prefix-substring starting before the currently considered index that extends farthest to the right (initially, the window is empty).
 
Variables used and invariants of the algorithm:
 
 
 
i, the index under consideration, starts at 1 (for 0-based indexing; the entire string is not considered) and is incremented to length - 1
 
 
left and right, the first and last index of the prefix-substring window; invariants: 
  
 
   
left < i, left <= right < length(S), either left > 0 or right < 1,
 
   
if left > 0, then S[left .. right] is the maximal common prefix of S and S[left .. ],
 
   
if 1 <= j < i and S[j .. k] is a prefix of S, then k <= right
 
  
 
 
An array Z, invariant: for 1 <= k < i, Z[k] contains the length of the longest common prefix of S[k .. ] and S.
 
 
The algorithm:
 
 
 
Set i = 1, left = right = 0 (any values with left <= right < 1 are allowed), and set Z[j] = 0 for all indices 1 <= j < length(S).
 
 
If i == length(S), stop.
 
 
If i > right, find the length l of the longest common prefix of S and S[i .. ], store it in Z[i]. If l > 0 we have found a window extending farther right than the previous, then set left = i and right = i+l-1, otherwise leave them unchanged. Increment i and go to 2.
 
 
Here left < i <= right, so the substring S[i .. right] is known - since S[left .. right] is a prefix of S, it is equal to S[i-left .. right-left].
 
Now consider the longest common prefix of S with the substring starting at index i - left. Its length is Z[i-left], hence S[k] = S[i-left + k] for 0 <= k < Z[i-left] and
 S[Z[i-left]] ≠ S[i-left+Z[i-left]]. Now, if Z[i-left] <= right-i, then i + Z[i-left] is inside the known window, therefore
 
S[i + Z[i-left]] = S[i-left + Z[i-left]] ≠ S[Z[i-left]]
S[i + k]         = S[i-left + k]         = S[k]   for 0 <= k < Z[i-left]
 
and we see that the length of the longest common prefix of S and S[i .. ] has length Z[i-left]. Then set Z[i] = Z[i-left], increment i, and go to 2.
 
Otherwise, S[i .. right] is a prefix of S and we check how far it extends, starting the comparison of characters at the indices right+1 and right+1 - i. Let the length be l. Set Z[i] = l, left = i, right = i + l - 1, increment i, and go to 2.
 
 
Since the window never moves left, and the comparisons always start after the end of the window, each character in the string is compared at most once successfully to an earlier character in the string, and for each starting index, there is at most one unsuccessful comparison, therefore the algorithm is linear.
 
The code (using ByteString out of habit, ought to be trivially portable to Text):
 
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C
import qualified Data.ByteString.Unsafe as U
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Control.Monad
import Data.Word

main :: IO ()
main = do
    cl <- C.getLine
    case C.readInt cl of
      Just (cases,_) -> replicateM_ cases (C.getLine >>= print . similarity)
      Nothing -> return ()

-- Just to keep the condition readable.
(?) :: B.ByteString -> Int -> Word8
(?) = U.unsafeIndex

-- Calculate the similarity of a string using the Z-algorithm
similarity :: B.ByteString -> Int
similarity bs
    | len == 0  = 0
    | otherwise = runST getSim
      where
        !len = B.length bs
        getSim = do
            za <- newArray (0,len-1) 0 :: ST s (STUArray s Int Int)
            -- The common prefix of the string with itself is entire string.
            unsafeWrite za 0 len
            let -- Find the length of the common prefix.
                go !k j
                    | j < len && (bs ? j == bs ? k) = go (k+1) (j+1)
                    | otherwise = return k
                -- The window with indices in [left .. right] is the prefix-substring
                -- starting before i that extends farthest.
                loop !left !right i
                    | i >= len  = count 0 0 -- when done, sum
                    | i > right = do
                        -- We're outside the window, simply
                        -- find the length of the common prefix
                        -- and store it in the Z-array.
                        w <- go 0 i
                        unsafeWrite za i w
                        if w > 0
                          -- We got a non-empty common prefix and a new window.
                          then loop i (i+w-1) (i+1)
                          -- No new window, same procedure at next index.
                          else loop left right (i+1)
                    | otherwise = do
                        -- We're inside the window, so the substring starting at
                        -- (i - left) has a common prefix with the substring
                        -- starting at i of length at least (right - i + 1)
                        -- (since the [left .. right] window is a prefix of bs).
                        -- But we already know how long the common prefix
                        -- starting at (i - left) is.
                        z <- unsafeRead za (i-left)
                        let !s = right-i+1 -- length of known prefix starting at i
                        if z < s
                          -- If the common prefix of the substring starting at
                          -- (i - left) is shorter than the rest of the window,
                          -- the common prefix of the substring starting at i
                          -- is the same. Store it and move on with the same window.
                          then do
                              unsafeWrite za i z
                              loop left right (i+1)
                          else do
                              -- Otherwise, find out how far the common prefix
                              -- extends, starting at (right + 1) == s + i.
                              w <- go s (s+i)
                              unsafeWrite za i w
                              loop i (i+w-1) (i+1)
                count !acc i
                    | i == len  = return acc
                    | otherwise = do
                        n <- unsafeRead za i
                        count (acc+n) (i+1)
            loop 0 0 1