subsequences

[Eli Bendersky]

Hello all,

How would you code, in the most Rubyish way possible: (1) given an
array, decide whether it is strictly increasing, and (2) given two
arrays, decide whether the first is a subsequence of the second.

Here are my trivial implementations:

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end

return true
end


def is_subsequence_of?(seq, other_seq)
i = 0
seq.each do |x|
while other_seq != x
i += 1
return false if (i >= other_seq.length)
end
end

return true
end

I'm wondering if (1) is there a more Rubyish way to implement this ?
and (2) is there a more efficient way to implement this in pure Ruby ?

Thanks

 

[Eli Bendersky]

This doesn't quite work:
irb(main):625:0> is_subsequence_of?([4, 4, 6], [1, 2, 3, 4, 5, 4, 5, 6,
7, 8])
=> true
Basically it optimistically just keeps checking whether any remaining
elements of the first sequence are interspersed among the other
sequence. I don't think this is what you intended.

Perhaps I didn't explain myself clearly enough. Subsequence is not
necessarily consecutive, so [4, 4, 6] *is* indeed a subsequence of [1,
2, 3, >4, 5, >4, 5, >6, 7, 8])

I referred to non-consecutive subsequences

Eli

 

[Robert Klemme]

Hello all,

How would you code, in the most Rubyish way possible: (1) given an
array, decide whether it is strictly increasing, and (2) given two
arrays, decide whether the first is a subsequence of the second.

Here are my trivial implementations:

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end

return true
end

This cries out for inject:

module Enumerable
def increasing?
inject {|a,b| return false if a >= b; b}
true
end
end

Kind regards

robert

 

[Robert Klemme]

I came up with a more Rubyesque increasing_sequence? (called monotone?
since it works in either direction):
def monotone?(a, test=lambda {|x, y| x < y})
a.inject {|x, y| if test.call(x, y) then y else break end}
end

The default behavior checks for increasing sequences:
irb(main):675:0> monotone?([1, 2, 6])
=> 6
irb(main):676:0> monotone?([1, 2, 6, 4])
=> false

But we can check for decreasing sequences too:
irb(main):677:0> monotone?([1, 2, 6], lambda {|x, y| x > y})
=> false
irb(main):678:0> monotone?([3, 2, 1], lambda {|x, y| x > y})
=> 1

There's probably a simpler way to pass in Comparable.> above, but I
don't know what it is yet.

If doing a general solution I'd work with a block instead of a lambda
because it's syntactically easier for the caller and feels more natural
in Ruby land. Also you can check more constraints than just monotony
with this so there should be a more general name (but which?).

module Enumerable
def pairs_comply?
inject {|a,b| yield a,b or return false; b}
true
end
end

# test whether the sequence alternates between
# increasing and decreasing
arr=[1,2,0,10,4,5,-20,-3]
up=false
puts arr.pairs_comply? {|a,b|
up = !up
up ? b>a : b<a
}




Kind regards

robert

 

[Robert Klemme]

def is_subsequence_of?(seq, other_seq)
i = 0
seq.each do |x|
while other_seq != x
i += 1
return false if (i >= other_seq.length)
end
end

return true
end

I'm wondering if (1) is there a more Rubyish way to implement this ?
and (2) is there a more efficient way to implement this in pure Ruby ?

I'd get rid of one of the loops:

module Enumerable
def includes_nested?(arr)
i = 0

each do |x|
if x == arr
i += 1
return true if i == arr.size
end
end

false
end
end

Main advantage: only the small sequence must be indexable which allows
for efficient tests against large sequences (e.g. files).

Kind regards

robert

 

[Eli Bendersky]

Hello all,

How would you code, in the most Rubyish way possible: (1) given an
array, decide whether it is strictly increasing, and (2) given two
arrays, decide whether the first is a subsequence of the second.

Here are my trivial implementations:

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end

return true
end

This cries out for inject:

module Enumerable
def increasing?
inject {|a,b| return false if a >= b; b}
true
end
end

Nice ! The inject version is faster by almost 30% as well, but a simple
'loop' version was even faster.

require 'pp'
require 'benchmark'

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end

return true
end

def increasing_sequence_inj?(seq)
seq.inject {|mem, x| return false if mem >= x; x}
true
end

def increasing_sequence_loop?(seq)
for i in 1 ... seq.length
return false if seq[i - 1] >= seq
end
true
end

seq1 = [1, 2, 4, 8, 16, 32, 64]
seq2 = [1, 2, 4, 8, 16, 15, 21]

ntimes = 100_000
Benchmark.bmbm(10) do |x|
x.report("my") do
ntimes.times do
increasing_sequence?(seq1)
increasing_sequence?(seq2)
end
end

x.report("inj") do
ntimes.times do
increasing_sequence_inj?(seq1)
increasing_sequence_inj?(seq2)
end
end

x.report("loop") do
ntimes.times do
increasing_sequence_loop?(seq1)
increasing_sequence_loop?(seq2)
end
end
end


Rehearsal ---------------------------------------------
my 5.640000 0.078000 5.718000 ( 5.766000)
inj 4.063000 0.032000 4.095000 ( 4.406000)
loop 3.828000 0.047000 3.875000 ( 3.937000)
----------------------------------- total: 13.688000sec

user system total real
my 5.610000 0.046000 5.656000 ( 5.765000)
inj 3.985000 0.016000 4.001000 ( 4.062000)
loop 3.860000 0.047000 3.907000 ( 3.953000)


Is there anything faster than the loop ?

Eli

 

[Robert Klemme]

Hello all,

How would you code, in the most Rubyish way possible: (1) given an
array, decide whether it is strictly increasing, and (2) given two
arrays, decide whether the first is a subsequence of the second.

Here are my trivial implementations:

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end

return true
end

This cries out for inject:

module Enumerable
def increasing?
inject {|a,b| return false if a >= b; b}
true
end
end

Nice ! The inject version is faster by almost 30% as well, but a simple
'loop' version was even faster.

require 'pp'
require 'benchmark'

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end

return true
end

def increasing_sequence_inj?(seq)
seq.inject {|mem, x| return false if mem >= x; x}
true
end

def increasing_sequence_loop?(seq)
for i in 1 ... seq.length
return false if seq[i - 1] >= seq
end
true
end

seq1 = [1, 2, 4, 8, 16, 32, 64]
seq2 = [1, 2, 4, 8, 16, 15, 21]

ntimes = 100_000
Benchmark.bmbm(10) do |x|
x.report("my") do
ntimes.times do
increasing_sequence?(seq1)
increasing_sequence?(seq2)
end
end

x.report("inj") do
ntimes.times do
increasing_sequence_inj?(seq1)
increasing_sequence_inj?(seq2)
end
end

x.report("loop") do
ntimes.times do
increasing_sequence_loop?(seq1)
increasing_sequence_loop?(seq2)
end
end
end


Rehearsal ---------------------------------------------
my 5.640000 0.078000 5.718000 ( 5.766000)
inj 4.063000 0.032000 4.095000 ( 4.406000)
loop 3.828000 0.047000 3.875000 ( 3.937000)
----------------------------------- total: 13.688000sec

user system total real
my 5.610000 0.046000 5.656000 ( 5.765000)
inj 3.985000 0.016000 4.001000 ( 4.062000)
loop 3.860000 0.047000 3.907000 ( 3.953000)


Is there anything faster than the loop ?

You can write a C extension. Seriously, I'd stick with the inject
variant because it's a) most elegant, b) is not much slower than the
loop and c) works for *arbitrary* Enumerables while both of your
versions work only for arrays.

Btw, how do benchmark results change if you do this?

seq1 = (1..1_000_000).to_a

IOW, is any of these algorithms better for short sequences vs. long
sequences?

Kind regards

robert

 

[Daniel Schierbeck]

def increasing_sequence?(seq)
seq.each_with_index do |x, i|
return false if i > 0 and seq[i - 1] >= x
end
return true
end

module Enumerable
def increasing?
inject{|a, b| if a > b then return false else b end}
return true
end
end

[1, 2, 3].increasing? => true
[3, 2, 1].increasing? => false

Cheers,
Daniel

 

[Eli Bendersky]

Is there anything faster than the loop ?

You can write a C extension. Seriously, I'd stick with the inject
variant because it's a) most elegant, b) is not much slower than the
loop and c) works for *arbitrary* Enumerables while both of your
versions work only for arrays.

True, it is more elegant. But I'm not sure that (c) is a good reason,
since I don't think sequences will be represented by anything other
than arrays.

Btw, how do benchmark results change if you do this?

seq1 = (1..1_000_000).to_a

The results surprised me. Running with ntimes = 10 on the 1 mln long
string, I get:

Rehearsal ---------------------------------------------
my 45.297000 0.313000 45.610000 ( 47.015000)
inj 35.672000 0.406000 36.078000 ( 37.000000)
loop 16.625000 0.031000 16.656000 ( 16.922000)
----------------------------------- total: 98.344000sec

user system total real
my 45.172000 0.438000 45.610000 ( 46.485000)
inj 35.875000 0.266000 36.141000 ( 40.234000)
loop 16.672000 0.093000 16.765000 ( 17.406000)


A significant advantage to the loop ! What could make inject slow down
so much for longer arrays ?

Eli

 

[Robert Klemme]

True, it is more elegant. But I'm not sure that (c) is a good reason,
since I don't think sequences will be represented by anything other
than arrays.

You can still have the general implementation in module Enumerable and
have a specialized implementation in Array. *You* might use only
Arrays but the problem is not restricted to arrays.

The results surprised me. Running with ntimes = 10 on the 1 mln long
string, I get:

Rehearsal ---------------------------------------------
my 45.297000 0.313000 45.610000 ( 47.015000)
inj 35.672000 0.406000 36.078000 ( 37.000000)
loop 16.625000 0.031000 16.656000 ( 16.922000)
----------------------------------- total: 98.344000sec

user system total real
my 45.172000 0.438000 45.610000 ( 46.485000)
inj 35.875000 0.266000 36.141000 ( 40.234000)
loop 16.672000 0.093000 16.765000 ( 17.406000)


A significant advantage to the loop ! What could make inject slow down
so much for longer arrays ?

Block calls maybe. A block call is like a method invocation which does
not happen for the loop if I remember the code correctly.

Cheers

robert

 

[Eli Bendersky]

A significant advantage to the loop ! What could make inject slow down

Block calls maybe. A block call is like a method invocation which does
not happen for the loop if I remember the code correctly.

This is a good place for optimization inside Ruby. If code in blocks
can be inlined, it can surely run at least as fast as a loop - and I
suspect that even faster, because a loop is somewhat more general.

As it stands now, it's a realy pity that the elegant and idiomatic way
is slower. This is one of my problems with Common Lisp actually - you
can write very beautiful code, but it will most likely be slow. To
write fast code, you use the ugly 'loop' macro anyway, so the beauty of
the language fades away. I think that a better internal optimization
can solve this problem for Ruby.

Eli

 

[shortcutter]

This is a good place for optimization inside Ruby. If code in blocks
can be inlined, it can surely run at least as fast as a loop - and I
suspect that even faster, because a loop is somewhat more general.

It's not easy to inline this because a block and a loop body are really
two different things although they might look alike. For example, a
block may introduce new variables that are not seen outside of it and
it accesses a completely different binding, so a new environment has to
be created for the block. Then, there is always only one body for a
given loop but there may be multiple blocks that are executed from on
method (just think of the block form of File.open - you'll likely find
several blocks that are handed over to this method in a reasonable
sized script / application. A block is really an anonymous function.
You would rather have to inline the method that calls the block into
the method where the block sits than inline the block into the method
that actually invokes it.

As it stands now, it's a realy pity that the elegant and idiomatic way
is slower. This is one of my problems with Common Lisp actually - you
can write very beautiful code, but it will most likely be slow. To
write fast code, you use the ugly 'loop' macro anyway, so the beauty of
the language fades away. I think that a better internal optimization
can solve this problem for Ruby.

We (at least I) all hope for the next generation Ruby which hopefully
runs on a Java VM and thus can use all the VM's runtime optimizations.

Kind regards

robert

PS: Posting through Google Groups because Thunderbird seems to choke on
c.l.r at the moment. Does anybody else experience this?

 

[ChrisH]

Since there were several responses to the increasing sequence, I
figured I'd post my solution to the subsequence:

module Enumerable
def hasSubSeq?(other)
#return true if other is a sub-sequence of self, false otherwise

ta = self.dup
other.each{ |el|
return false if ta.index(el).nil?
ta = ta[ta.index(el)..ta.size-1]
}
true
end
end

cheers

 

[ChrisH]

err...make that:
ta = ta[(ta.index(el)+1)..(ta.size-1)]


Nothing like posting to make errors more evident...9^)

 

[Daniel Schierbeck]

This is actually a great use case for #to_b:

class Object
def to_b
self ? true : false
end
end

module Enumerable
def increasing?
inject{|a, b| break false if a > b; b}.to_b
end
end


Daniel