Самая длинная последовательность без снижения в Haskell медленная. Как улучшить? - PullRequest
Новая
       27

Самая длинная последовательность без снижения в Haskell медленная. Как улучшить?

1 голос
/ 21 мая 2011 
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-2 с с длиной seq = 1000, в то время как в питоне выходят безвозвратно

в питоне 

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 работает так долго, а python возвращает ответ через 10-15 с

Можем ли мы улучшить скорость на Haskell?

Ответы [ 2 ]

4 голосов
/ 21 мая 2011

Ваша основная проблема в том, что вы используете неправильную структуру данных в Haskell для этого алгоритма. Вы перевели алгоритм, который зависит от O (1) поиска в последовательности (как в вашем коде Python), в алгоритм, который выполняет O (n) поиска в списке в Haskell.

Используйте структуры данных, похожие на подобные, и тогда ваши проблемы сложности сами позаботятся о себе. В этом случае это означает использование чего-то вроде Data.Vector.Unboxed для представления последовательности, которая имеет индексирование O (1) , а также низкие постоянные издержки в целом.

3 голосов
/ 21 мая 2011

Не имея ничего, кроме по-настоящему бессмысленной упаковки ваших списков в векторы, я получаю 2,5 секунды, когда входной список равен [1..10000]. 

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

Компиляция и исполнение: 

tommd@Mavlo:Test$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.3
tommd@Mavlo:Test$ ghc -O2 so.hs
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo: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));). 

tommd@Mavlo:Test$ time python so.py

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