CODEWITHSUNDEEP
haskellindexingcomplexity-theorysequence
vpdp_pc
vpdp_pc

Reputation: 13

Longest non decrease subseq in Haskell is slow. How to improve?

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

that take about 1-2s with lenght of seq = 1000 while in python is come out imtermedialy

in 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)

and when length of seq is 10000, the haskell program run sooo long while python return the answer after 10-15s

Can we improve haskell speed?

Upvotes: 1

Views: 250

Answers (2)

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64740

With nothing more than a really mindless wrapping of your lists into Vectors I get 2.5 seconds when the input list is [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

The compilation and execution:

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

A worker-wrapper transformation on filter'and'get'max seems to shave off another second.

Also, I don't understand why you need that middle case (filter'and'get'max f [x]), shouldn't it work fine without that? I guess this changes the result if dp!x < 0. Note eliminating that saves 0.3 seconds right there.

And the python code you provided takes ~ 10.7 seconds (added a call of longest(range(1,10000));).

tommd@Mavlo:Test$ time python so.py

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

Upvotes: 3

Don Stewart
Don Stewart

Reputation: 137987

Your core problem is that you're using the wrong data structure in Haskell for this algorithm. You've translated an algorithm that depends on O(1) lookups on a sequence (as in your Python code), into one that does O(n) lookups on a list in Haskell.

Use like-for-like data structures, and then your complexity problems will take care of themselves. In this case, it means using something like Data.Vector.Unboxed to represent the sequence, which has O(1) indexing, as well as low constant overheads in general.

Upvotes: 4

Related Questions