Fun with method_missing

[Glenn Parker]

I'm afraid Pickaxe2 does not have many powerful examples for using
method_missing. In particular, it does not show how to use
method_missing with a block argument, and it does not show
method_missing actually creating the missing method.

I was able to find one example of a block arguemnt to method_missing on
the ruby-talk list, which helped me over a bump. I wanted to implement
a perl-ish idiom where missing methods are defined when they are first
referenced, so that method_missing is not needed after the first time.

The initial motivation: I was trying to write code to efficiently
generate combinations from sets (e.g. 5 items taken 3 at a time),
something I've needed several times. It's a simple task, but it's easy
to write very slow code to do it. This is the fastest I've come up with
so far.

For reasonably short execution times, run with arguments like "5 50" or
"4 100".

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#!/usr/bin/ruby
# combine.rb

module Combine

# Generate all combinations of +pick+ elements from +items+ array.
def Combine.pick(pick, items, &block)
pick_recurse([], pick, items.dup, &block) if pick > 0
end

# Automatically define new pickN methods and call them.
def Combine.method_missing(method_id, *args, &block)
if method_id.to_s =~ /^pick(\d+)$/
def_pick($1.to_i).call(*args, &block)
else
raise NoMethodError, "invalid method Combine.#{method_id.to_s}"
end
end

private

# Iterate over combinations using recursion.
def Combine.pick_recurse(set, pick, items, &block)
while not items.empty?
set.push(items.shift)
if pick > 1
pick_recurse(set, pick - 1, items.dup, &block)
else
yield set
end
set.pop
end
end

# Define a pickN method and return the new Method object.
def Combine.def_pick(pick)
method_name, method_code = build_pick(pick)
module_eval(method_code)
method(method_name)
end

# Return code for pickN with recursion unrolled.
def Combine.build_pick(pick)
method_name = "pick#{pick}"
method_code = [
"def Combine.#{method_name}(items0, &block)\n",
"set = []\n",
(0...pick).collect do |p|
[ "items#{p+1} = items#{p}.dup\n",
"while not items#{p+1}.empty?\n",
"set.push(items#{p+1}.shift)\n" ]
end,
"yield set\n",
(0...pick).collect do |p|
[ "set.pop\n",
"end\n" ]
end,
"end\n" ].flatten.join('')
return method_name, method_code
end

end

if __FILE__ == $0

if ARGV.length != 2
STDERR.puts "Usage: combine.rb <pick> <from>"
exit(1)
end

P = ARGV[0].to_i
F = ARGV[1].to_i

puts "Pick 2 out of 5 (recursive):"
Combine.pick(2, (1..5).to_a) {|set| print "#{set[0]}-#{set[1]} " }
print "\n"

puts "Pick 2 out of 5 (non-recursive):"
Combine.pick2((1..5).to_a) {|set| print "#{set[0]}-#{set[1]} " }
print "\n"

items = (1..F).to_a
method_id = "pick#{P}".to_sym

require 'benchmark'

Benchmark.bm(10) do |x|
x.report("pick") do
Combine.pick(P, items) do |set|
end
end
x.report(method_id.to_s) do
Combine.send(method_id, items) do |set|
end
end
x.report(method_id.to_s + " (2)") do
Combine.send(method_id, items) do |set|
end
end
end

end

 

[Mathieu Bouchard]

I'm afraid Pickaxe2 does not have many powerful examples for using
method_missing. In particular, it does not show how to use
method_missing with a block argument, and it does not show
method_missing actually creating the missing method.

RubyX11 0.6 (http://artengine.ca/matju/RubyX11/) has examples of both. It
does a lazy compilation of type-declarations into packers and
unpackers. However I haven't insisted on releasing it because it wasn't so
much faster, and the code still only runs in Ruby 1.6 (sorry!!!).

However most other uses of method_missing I've had, don't define new
methods, they just redirect to another one, possibly changing the args a
bit, or even, the actual job is done within the body of method_missing
(!).

The initial motivation: I was trying to write code to efficiently
generate combinations from sets (e.g. 5 items taken 3 at a time),

Take the general problem of n items taken m at a time. Represent subsets
relative to the original set together with an arbitrary enumeration of its
elements. Then each subset is an element of 0..(2**n-1). The weight of a
number is its number of "1" bits (in this context, it's also subset
cardinality). The smallest such number is always 2**m-1. Then for m=3,n=5
there are ten numbers. Here are they, sorted, followed by a list of
differences (such that the first seq is the partial sums of the second
seq).

7, 11, 13, 14, 19, 21, 22, 25, 26, 28.
4, 2, 1, 5, 2, 1, 3, 1, 2.

If you can figure out a fast way to compute either sequence, then you have
a fast way to generate sets. If n>30 then it becomes slower because of the
use of Bignums.

Actually it's easy if you have a fast way to find the weight: then all you
have to do is, you take the previous number in the sequence (let's call it
x), find w(x+1), find out how much more weight you need by doing
k=m-w(x+1)), do x+=(1<<k), repeat until you actually get the correct
weight. Does that sound right?

in short, do x+=(1<<(m-w(x+1))) while w(x)<m.

I don't have a fast w function though. I might consider to accelerate
weight computation differentially using the identity
w(a^b)=w(a)+w(b)-2w(a&b) (which ought to be familiar from set theory
and/or probability theory). However I'm not sure it really would get any
faster...

Your version seems good. The efficiency of my bitset method doesn't expand
to sparse sets, and thus works best when m is not too far from n (say,
when m > n/32, possibly?).

What do you think of my solution?

_____________________________________________________________________
Mathieu Bouchard -=- Montréal QC Canada -=- http://artengine.ca/matju

 

[Glenn Parker]

RubyX11 0.6 (http://artengine.ca/matju/RubyX11/) has examples of both. It
does a lazy compilation of type-declarations into packers and
unpackers. However I haven't insisted on releasing it because it wasn't so
much faster, and the code still only runs in Ruby 1.6 (sorry!!!).

However most other uses of method_missing I've had, don't define new
methods, they just redirect to another one, possibly changing the args a
bit, or even, the actual job is done within the body of method_missing
(!).

If you run the benchmark I posted, you should note that the speedup
between the first and second tests is fairly small, while the difference
between the first two tests and the third one is significant. The first
test generates and evals a non-recursive method, then calls it. The
second test just calls the method created during the first test. The
third test calls a recursive version of the same algorithm.

The overhead of generating and evaling (in this case) is small, but the
difference between non-recursive and recursive methods is big. So, I
suppose what I _could_ do is generate and eval code to find the result
without actually adding a new method to the module. But I still like
the trick of defining new methods on demand.

Take the general problem of n items taken m at a time. Represent subsets
relative to the original set together with an arbitrary enumeration of its
elements. Then each subset is an element of 0..(2**n-1). The weight of a
number is its number of "1" bits (in this context, it's also subset
cardinality). The smallest such number is always 2**m-1.

I also thought of enumerating through bit-patterns looking for those
with the desired number of 1-bits. Bits in a byte can be counted using
a lookup table with 2**8 entries. Then you sum up the bits for each
byte in an integer.

Then for m=3,n=5
there are ten numbers. Here are they, sorted, followed by a list of
differences (such that the first seq is the partial sums of the second
seq).

7, 11, 13, 14, 19, 21, 22, 25, 26, 28.
4, 2, 1, 5, 2, 1, 3, 1, 2.

If you can figure out a fast way to compute either sequence, then you have
a fast way to generate sets. If n>30 then it becomes slower because of the
use of Bignums.

Yup, this idea runs into problems when applied to big domains, i.e. long
bit arrays. Arbitrary length bit arrays would be a useful extension for
Ruby.

Then there's the problem of using each bit pattern result to produce a
usable collection of items.

An aside: it's funny how Ruby supports Fixnum#[], but not Fixnum#[]=.
Another asymmetry arising from immutable Fixnum objects, I suppose. I
would deprecate Fixnum#[], replacing it with Fixnum#bit_test and
Fixnum#bit_assign.

Actually it's easy if you have a fast way to find the weight: then all you
have to do is, you take the previous number in the sequence (let's call it
x), find w(x+1), find out how much more weight you need by doing
k=m-w(x+1)), do x+=(1<<k), repeat until you actually get the correct
weight. Does that sound right?

Not fair... still morning... brain is cold.

Even if it is correct, it doesn't sound like it will produce a result
any faster (on average) than just iterating and testing w.

Your version seems good. The efficiency of my bitset method doesn't expand
to sparse sets, and thus works best when m is not too far from n (say,
when m > n/32, possibly?).

What do you think of my solution?

I think you should try coding it up and see what happens.

 

[Glenn Parker]

If you run the benchmark I posted, you should note that the speedup
between the first and second tests is fairly small, while the difference
between the first two tests and the third one is significant. The first
test generates and evals a non-recursive method, then calls it. The
second test just calls the method created during the first test. The
third test calls a recursive version of the same algorithm.

Oops, I forget I changed the order of the tests before I posted it.
First test is recursive, second test is eval and call non-cursive, third
test is just call non-recursive. So, they get faster at each step.