Haskell中最長的非遞減子搜索緩慢。如何提高？

longest'inc'subseq seq = maximum dp 
    where dp = 1 : [val n | n <- [1..length seq - 1]] 
      val n = (1 +) . filter'and'get'max ((<= top) . (seq!!)) $ [0..pred n] 
      where top = seq!!n 
      ----- 
      filter'and'get'max f []  = 0 
      filter'and'get'max f [x] = if f x then dp!!x else 0 
      filter'and'get'max f (x:xs) = if f x then (if vx > vxs then vx else vxs) else vxs 
      where vx = dp!!x 
        vxs = filter'and'get'max f xs

稱取約1-2S與SEQ的lenght = 1000 而在Python是出來imtermedialyHaskell中最長的非遞減子搜索緩慢。如何提高？

在python

def longest(s): 
    dp = [0]*len(s) 
    dp[0] = 1 
    for i in range(1,len(s)): 
     need = 0 
     for j in range (0, i): 
      if s[j] <= s[i] and dp[j] > need: 
       need = dp[j] 
     dp[i] = need + 1 
    return max(dp)

和SEQ時的長度是10000，Haskell的程序運行sooo long python在10-15s後返回答案

我們可以提高Haskell速度嗎？

來源

2011-05-20 vpdp_pc

你的核心問題是你在這個算法中使用Haskell中的錯誤數據結構。您已經將依賴於序列查找的算法（如在Python代碼中）翻譯爲一個在Haskell中的列表上查找的O（n）。

使用類似於數據結構，然後您的複雜性問題將自行處理。在這種情況下，它意味着使用類似於Data.Vector.Unboxed的東西來表示序列，其具有索引，以及一般的低恆定開銷。

來源

2011-05-20 23:42:47

感謝，你們讓我相信在Haskell的:) – 2011-05-21 05:11:52

速度比Data.Vector.Unboxed陣列更有效，如DiffUArray例如？如果是這樣，你能解釋一下爲什麼？ – is7s 2011-05-21 14:43:04

DiffArray特別慢，因爲它相對天真。它幾年前從核心庫設置中刪除。有關數組庫的比較，請參閱：http://stackoverflow.com/questions/6006304/what-haskell-representation-is-recommended-for-2d-unboxed-pixel-arrays-with-mill/6007139#6007139 – 2011-05-21 16:55:06

沒有什麼比將您的列表真正無意識地包裝到矢量中時，輸入列表爲[1..10000]時得到2.5秒。

import qualified Data.Vector as V 
import Data.Vector (Vector, (!)) 

main = print $ liss [0..10000] 

liss :: [Int] -> Int 
liss seqL = V.maximum dp 
    where dp = V.fromList $ 1 : [val n | n <- [1..length seqL - 1]] 
      seq = V.fromList seqL 
      val n = (1 +) . filter'and'get'max ((<= top) . (seq!)) $ [0..pred n] 
      where top = seq!n 
      ----- 
      filter'and'get'max :: (Int -> Bool) -> [Int] -> Int 
      filter'and'get'max f []  = 0 
      filter'and'get'max f [x] = if f x then dp!x else 0 
      filter'and'get'max f (x:xs) = if f x then (if vx > vxs then vx else vxs) else vxs 
      where vx = dp!x 
        vxs = filter'and'get'max f xs

的編譯和執行：

[email protected]:Test$ ghc --version 
The Glorious Glasgow Haskell Compilation System, version 7.0.3 
[email protected]:Test$ ghc -O2 so.hs 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
[email protected]:Test$ time ./so 
10001 

real 0m2.536s 
user 0m2.528s

一名工人，包裝改造上filter'and'get'max似乎剃掉另一個第二。

此外，我不明白爲什麼你需要中間情況（filter'and'get'max f [x]），不應該沒有這個工作正常嗎？我想這會改變結果，如果dp!x < 0。注意消除，那裏保存0.3秒。

你提供的python代碼需要大約10.7秒（增加了一個longest(range(1,10000));的調用）。

[email protected]:Test$ time python so.py 

real 0m10.745s 
user 0m10.729s

來源

2011-05-21 02:11:14

謝謝。對不起，因爲我的英語。但我不明白你對fillter'and'get'max f [x]的評論。我認爲這是一個以列表爲參數的函數模式。和dp！x不能<0，因爲它是一個計數變量 – 2011-05-21 05:18:26

Haskell中最長的非遞減子搜索緩慢。如何提高？

回答

相關問題