4
\$\begingroup\$

This is an \$O(n \sqrt n)\$ solution to the the following problem:

Given a sequence, compute the number of non-empty increasing subsequences

The algorithm is to compute g(i) = # of increasing subsequences that end at index i using dynamic programming, and then sum over i. A full description of the algorithm used can be found here. However, naively using dynamic programming yields an \$O(n^2)\$ solution, which is too slow. It's possible to get \$O(n \log n)\$ using a BIT, but I opted for the \$O(n \sqrt n)\$ "hacker's" BIT, implemented below. As I am a novice (relatively), my question is: how could I have implemented it better? Specifically, I generally prefer to program in a more functional style, but this code is very imperative. How could I have made it more functional?

from math import sqrt
from bisect import bisect_left

def count_sequences(seq):
    # Normalize seq
    seq_sorted = sorted(seq)
    seq = list(map(lambda x: bisect_left(seq_sorted, x), seq))

    # Initialize the memoization arrays
    n = len(seq); f = [0]*n
    nn = int(sqrt(len(seq))); ff = [0]*(nn+2)

    # Compute g(i) = f(s[i])
    for s in seq:
        res = sum([
            1,
            sum(ff[: (s // nn)]),
            sum(f[(s // nn)*nn : s])
        ])

        f[s] += res 
        ff[s // nn] += res

    # Sum all g(i)
    return sum(ff) 
\$\endgroup\$
3
\$\begingroup\$

I wouldn't go as far to say that functional programming and Python don't mix, but you should really consider what you're going for while writing it whatever language you are writing in. I would not make your goal:

How could I have made it more functional?

while writing Python. If you are used to writing in Haskell (for example) you shouldn't expect to always write like that in Python, so I think you should reconsider your ideal.

As for an actual correction to your code:

If you're going to call list on map, you might as well use a list comprehension, change:

seq = list(map(lambda x: bisect_left(seq_sorted, x), seq))

to:

seq = [ bisect_left(seq_sorted, x) for x in seq ] 
\$\endgroup\$
  • \$\begingroup\$ wow, I always write list(map(; its a habit from my Python 2 days, when I would prefer map to list comprehensions. Thanks for pointing this out! Re your comment on functional programming: ya, it's just messing with state freaks me out, it's too easy to shoot yourself in the foot... \$\endgroup\$ – Elliot Gorokhovsky Mar 29 '17 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.