Asp Forum - Fun with method_missing

Glenn Parker

3/22/2005 4:06:00 PM

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

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

3 Answers

Mathieu Bouchard

3/23/2005 11:57:00 AM

Glenn Parker

3/23/2005 2:51:00 PM

Mathieu Bouchard wrote:
>
> RubyX11 0.6 (http://artengine.ca/matj...) 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.

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

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 | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

Glenn Parker

3/23/2005 3:59:00 PM

Glenn Parker wrote:
>
> 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.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

comp.lang.ruby

Fun with method_missing

Glenn Parker

Mathieu Bouchard

Glenn Parker

Glenn Parker

x Login to ForumsZone