Return to Answer

replaced http://stackoverflow.com/ with https://stackoverflow.com/

edited May 23, 2017 at 12:40

Community Bot

• 1

Inline Side-by-side Side-by-side Markdown

answered Mar 22, 2012 at 11:45

Rik Poggi

• 1.2k
• 7
• 9

PEP8 is the python style guide. To improve your style a start is to run the pep8 script against your file. Other style "problems" you'll have to find them yourself (or ask here on core review :)

Comments and docstrings

Check the PEP8 session Comments.

This:

## Returns the longest subsequence (non-contiguous) of X that is strictly increasing.
def subsequence(X):

Should be a docstring:

def subsequence(X):
 """Returns the longest subsequence (non-contiguous) of X that is strictly
 increasing.
 
 """

Variable names

I know that you kept the wikipedia variable names, but you should try to make your script conistent with itself. So, squeeze your variable name imagination, and choose something short, sweet and meaningful. You can always leave a note at the beginning, linking to the wikipedia page and say which variable is which.

With this:

L = 1 ## length of longest subsequence (initially: just first element)

I'd do:

# length of longest subsequence (initially: just first element)
len_longest = 1

Since the comment was a bit too long to be an inline comment I moved it. A good name for X might be seq. For M maybe pos_smallest and for P pos_predecessor or something like that, maybe with a better understanding of the underling algorithm you can find better names :)

range() and xrange()

Check the link above and you'll see that one is a list and the other an itertor (genrator).

So, this:

for i in range(1,len(X)):

Should be:

for i in xrange(1, len(seq)):

Note that in Python 3 xrange() become range().

Reverse a list

This line:

return list(reversed(result))

Should be:

return result[::-1]

Other than being more clear, it will be Python 3 compatible.

Useless brackets are useless

Python is not C so don't put brackets everywhere.

Here:

while (trace_idx >= 0):

Could just be:

while trace_idx >= 0:

Do the same thing in another couple of places.

Binary search

Your use of bisect_left looks really strange:

j = bisect_left([X[M[idx]] for idx in range(L)], X[i])

And even more the previous version:

while True:
 if (start == end):
 if (X[M[start]] < X[i]):
 j = start
 break
 else:
 partition = 1 + ((end - start - 1) / 2)
 if (X[M[start + partition]] < X[i]):
 start += partition
 j = start
 else:
 end = start + partition - 1

Which could have easily been:

while start != end:
 partition = 1 + (end - start - 1) / 2
 if X[M[start + partition]] < X[i]:
 start += partition
 j = start
 else:
 end = start + partition - 1
if X[M[start]] < X[i]:
 j = start

But you shouldn't do it like that anyway. Take a look at Binary Search in Python, there are both solution, the accepted is in "pure" Python (the one that I like the most) and there's the one with bisect_left. If you care about performances time them both.

This is just a pointing and I would have really liked to give you the code of the binary search, but you didn't really explained how your algorithm works (and it's quite different from the one showed in the wikipedia article), so I wasn't able to improve yours without changing its core.

Usually what one should do is instantiate at the beginning the entire M and P list, something like:

M = [0] * len(seq)

So you won't have to deal with append and so on... that are quite hard to follow.
I couldn't also get around your -1 offestes, are they really necessary? That's the main different I've found with the "official" algorithm.