From: Alex Martelli <aleaxit@...>
Date: 2003-09-16T02:27:57+09:00
Subject: Re: performance and style advice requested

Simon Strandgaard wrote:
   ...
>> def comb(x, y)
>>     # combinations of x things y at a time (0 if x<0, y<0, or y>x)
>>     result = $_comb_memo[[x, y]]
> 
>                            ^^^^^^
>                            ^^^^^^
> 
>                          very slow!!
> 
> Ruby converts it the array into a string.. this takes time!

Oh my!  I had no idea Ruby suffered under such a handicap wrt to Python
(that arrays had to be converted to strings to index into hashes, while
Python can use "tuples", its equivalent of frozen arrays, for that) --
then I must definitely be very sparing in using hashes with multi-dim
indexes in Ruby, at least in any bottleneck.  Thanks!  Just the kind of
things I'm trying to learn (I don't remember noticing any such caveat
in Thomas and Hunt's excellent book).

> 
> Try this instead, and tell me if it works ?
> 
> 
> def comb(x, y)
>     # combinations of x things y at a time (0 if x<0, y<0, or y>x)
>     result = $_comb_memo[x << 16 + y]
>     if !result
>         return 0 if x<0 or y<0 or y>x
>         result = $_comb_memo[x << 16 + y] = fact(x)/(fact(y)*fact(x-y))
>     end
>     return result
> end

I had already reworked comb (as per other advice from c.l.ruby( to a
slightly different and slightly faster form than my original one:

def comb(x, y)
    # combinations of x things y at a time (0 if x<0, y<0, or y>x)
    $_comb_memo[[x, y]] ||= 
        if x<0 or y<0 or y>x then 0 
        else fact(x)/(fact(y)*fact(x-y)) end
end

this gave a best-case performance (on Linux, and w. Ruby 1.6.8 -- a
far faster combo than Ruby 1.8.0 on Win/XP, apparently, see my latest
post) of 1.38 reported, 1.44 total.

The tiny change you suggest for indexing into the hash, i.e. changing
the only occurrence of indexing in this form of the method to

    $_comb_memo[x<<16 + y] ||= 

does make things even better -- we're now at 1.20 reported, 1.25 total,
best run of many (against 0.694 reported, 0.788 total for Python).
"Rubier and rubier", said Alice!-)

With Ruby now taking less than twice as long as Python, I guess I could
be satisfied here and move on to richer and more complicated cases, but
I can't help wondering if there might not be some crucial optimization
waiting to happen in the recursive iterator, which is (according to the
profiler, with its 400-times slowdown;-) by far the bottleneck...
any suggestions are welcome!


And thanks again for the suggestions so far...!


Alex