Perl Monk, Perl Meditation PerlMonks

### 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".

Create A New User
Node Status?
node history
Node Type: note [id://543792]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (6)
As of 2018-06-20 00:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (116 votes). Check out past polls.

Notices?