Alex Martelli
9/15/2003 4:40:00 PM
Ben Giddings wrote:
> Some style advice:
>
> On Sunday, September 14, 2003, at 12:44 PM, Alex Martelli wrote:
>> #
>> # factorial, memoized via an Array
>> #
>> $_fact_memo=[1,1,2,6,24,120,720]
>
> Ugh. This is what really bothers me about python programs. Ugly
> underscores.
Heh -- matter of taste, I guess; what _I_ personally find ugly is
that leading $, and I left the underscores in to try to ameliorate
that. Of course, nothing stops you from moving to a camelCaseish
$factMemo -- however, not only do I personally find that less
readable, but I''d also like to leave a hint that the memo is an
internal implementation detail, not a feature meant for external
consumption, and I like the convention of a leading _ for that.
(Of course, I _could_ wrap up the fact function and its memo in
a single package in any of various ways, I''m sure, so the "hint"
aspect is quite secondary).
>> def fact(x)
>> # factorial of x (0 if x<0)
>> result = $_fact_memo[x]
>> if !result
>> return 0 if x<0
>> result = $_fact_memo[x] = x*fact(x-1)
>> end
>> return result
>> end
>
> Hmm, how about
>
> def fact(x)
> $fact_memo[x] ||= if x<0
> 0
> else
> x*fact(x-1)
> end
> end
>
> Although I''m pretty sure that a simple conditional is faster than an
> array lookup so this might be faster (and is easier to read):
However, it will be very rare for any given x to NOT be already
memoized (i.e., fact is called with a very modest variety of
arguments, compared to the number of calls to it, in any typical
combinatorial-arithmetic application); while calls with x<0 are
going to be exceedingly rare. So, the relative costs of array
indexing vs (operator< + conditional) shouldn''t matter -- trying
to get the result off the array first _should_ be a win anyway
(or at least, that''s what my optimization experience as built on
a wide variety of languages tells me -- admittedly I have no such
experience in Ruby, but I fail to see how it would differ on this
specific point).
> def fact(x)
> return 0 if x<0
> $fact_memo[x] ||= x*fact(x-1)
> end
Actually, I find the oneliner body
$_fact_memo[x] ||= if x<0 then 0 else x * fact(x-1) end
quite clear and readable, given that one must grok the semantics
of ||= anyway.
> You can take advantage of the fact Ruby expressions return their last
> value, and the return value of a function is the last expression''s
> value.
Very good point, and an excellent suggestion at least for concision &
readability purposes -- I''ll definitely keep the idiom
<container>[<index>] ||= <value>
in mind for the future -- thanks!
Performance-wise, there ain''t all that much in it for this app.
I''ve managed to scrounge some diskspace on Linux and compile both
Python and Ruby (1.6.8 only, unfortunately -- the link I downloaded
from mentioned 1.8, but I found out only when everything was built
that I had 1.6.8 instead [how I found out: I had thoughtlessly left
a trailing colon on an "if" statement -- 1.8 was quite cool about
it, while 1.6.8 gave me three weird errors for that one mistake;-)].
First observation is that the performance ratio is only 2:1 in
favour of Python, not 3:1 as in the Windows version -- thus I
strongly suspect that part of the issue with the Windows version
is that it may not be compiled as optimally as Python is. Second
observation is that on Linux I can run the benchmarks under the
time command so I get an objective measurement of overall elapsed
time as well as what the program itself tells me about it -- i.e.
measuring all of the startup overhead -- and that is, by a tiny
margin, favourable to Ruby too.
So, under these conditions, I get:
for Python 2.3: 0.694 reported, 0.788 total
for Ruby 1.6.8:
my original code: 1.47 reported, 1.52 total
new and improved: 1.45 reported, 1.50 total
each of these measurements is the best out of many, many runs
(as I''m measuring elapsed times and can''t put this Linux box in
anything like "isolated benchmarking conditions", unsurprisingly
the numbers over a few dozens of run are all over the place --
but the "best out of 24 runs" IS quite repeatable, so that giving
3 digits'' precision in the reported results is just about right).
So, I tried applying the same idea to the comb method, makint it:
$_comb_memo={}
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
(the if-else expression is too long for a oneliner here, so I had to
fold it), and that does give a slightly more substantial improvement:
for Ruby 1.6.8:
further improved: 1.38 reported, 1.44 total
I also tried bending it the other way as you recommended for fact:
$_comb_memo={}
def comb(x, y)
# combinations of x things y at a time (0 if x<0, y<0, or y>x)
if x<0 or y<0 or y>x then 0
else $_comb_memo[[x, y]] ||= fact(x)/(fact(y)*fact(x-y)) end
end
but that slows it down substantially (to 1.52 reported, 1.58 total,
best case) so I regressed this last change.
> The rest is more complex so I''ll quit while I''m ahead. :)
Thanks, though! The performance has not changed by much, but I do
see the style is now more Ruby-ish, and that, after all, is half of
what I''m trying to learn (the other half being how to speed it up:-).
Alex