Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re^2: Puzzle: Longest Increasing Sequence

by spurperl (Priest)
on Apr 17, 2006 at 09:59 UTC ( #543792=note: print w/replies, xml ) Need Help??

in reply to Re: Puzzle: Longest Increasing Sequence
in thread Puzzle: Longest Increasing Sequence

Just for kicks, here is the same implemented in Ruby. I noticed that the original page has a bug you fixed - towards the end of the main loop, there is:
if ($low > $n_las) { $n_las++; }
While in the pseudocode it's "if (low .ge. n_as) n_as += 1" and I presume .ge. means "greater or equal" ?!

Anyways, here's my implementation. It is notably cleaner than yours, but twice slower:

def find_lis_greedy(seq) n = seq.length terminals = [0] * (n + 1) backptrs = [-1] + [0] * (n - 1) lis = [] n_lis = 1 1.upto(n - 1) do |i| low = 1 high = n_lis while low <= high mid = (low + high) / 2 if seq[i] <= seq[terminals[mid]] high = mid - 1 else low = mid + 1 end end terminals[low] = i if low <= 1 backptrs[i] = -1 else backptrs[i] = terminals[low - 1] end n_lis += 1 if low > n_lis end lis[n_lis - 1] = seq[terminals[n_lis]] temp = terminals[n_lis] (n_lis - 2).downto(0) do |i| temp = backptrs[temp] lis[i] = seq[temp] end return lis end

Replies are listed 'Best First'.
Re^3: Puzzle: Longest Increasing Sequence
by ikegami (Pope) on Apr 17, 2006 at 16:41 UTC

    It is indeed a bug fix, not a typo.

    The other thing I did was to clean up the code that builds the return value by using unshift. I no longer needed a counting loop, so I removed the counter variable ("i") and replaced the counting loop with a while loop (implemented as a for loop). "temp" was a bad name — even i, j, etc would be better since temp holds an index — so I renamed it to "i".

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://543792]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (8)
As of 2017-06-22 18:59 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (528 votes). Check out past polls.