# Performance and style advice requested

I’m trying to learn some Ruby, so I want to write some Ruby code, starting
with my usual favourite fun field – combinatorial arithmetic related to
the game of contract bridge. As a warm-up, I begin with the “probability
of pointcount”. Problem definition: a hand is a set of 13 cards out of 52.
16 of those cards (Aces, Kings, Queens, Jacks) are known as “honors” and
are assigned a “pointcount” (4 for each Ace, 3 for each King, 2 for each
Queen, 1 for each Jack). Consider all possible hands and determine the
exact probability of each possible point-count.

Basically, this boils down to considering each of the 2**16 possible
sets of honors – each has an easily computed total pointcount – and
for each of them computing in how many different ways it can occur –
which is C(36, 13-numberofhonors) – the ways of choosing out of the
36 non-honors in the deck the 13-numberofhonors non-honors in this
hand. (That’s with C(x,y) extended to be 0 for y<0, of course).

So I sit down and code it in the simplest way – in Python first for
practice, since that’s what I’m familiar with, then in Ruby. Fine
both ways, except that (on my laptop, which is all I have at hand as
I’m on a business trip – with Python 2.3 and Ruby 1.8 and Win/XP)
the Python version runs in just above 4 seconds while the Ruby one
takes over 9. Hmmm, probably my lack of Ruby instincts, of course,
but anyway – just as of course – this needs to be optimized by
quite a bit (not for its own sake, but because later I’ll extend it
to compute much more interesting stuff, such as correlations between
points, controls and shape, etc, etc) so who cares about performance
for the “coded in the simplest way” versions (oh, I should clarify:
simplest except that I have of course memoized C(), computing
combinations aka binomial coefficients, and the factorial it calls).

So I start optimizing and squeezing every cycle I can – and I get
down to about 0.65 seconds for Python, 2.3 seconds for Ruby (best
case, for each of them). Eep – the ratio keeps increasing, so my
lack of sound Ruby instincts must be really hurting. Oh well, say
I, let’s try “ruby -rprofile”. EEK! After a couple of times where
I was convinced it had just seized up I decided to let it run all
the way – and it took almost 1000 seconds. Is a slowdown of over
400 times normal for Ruby profiling, or is something weird in my
installation…? (It’s the one-exe native Ruby 1.8 install for Win
which comes with a lot of goodies such as SciTE, Programming Ruby
in HTML-Help format, etc).

Anyway, the profiler’s output isn’t illuminating to me at all, so
that’s when I decide to turn to the famous Ruby community – I’m
sure you’ll find lots to critique in my Ruby program, particularly
with an eye to performance but not necessarily just that (I am
quite aware that I may be guilty of “coding Python in Ruby” – and
this may produce suboptimal performance and other issues).

So, first, for reference, here’s the optimized Python program:

···

# Memoized implementation of factorial

def fact(x, _fact_memo = {0:1, 1:1, 2:2, 3:6, 4:24, 5:120, 6:720, 7:5040} ):
" factorial of x (0 if x<0) "
try: return _fact_memo[x]
except KeyError:
if x < 0: return 0
return _fact_memo.setdefault(x, x * fact(x-1))

# Memoized implementation of C(x, y) [binomial coefficient, aka comb]

def comb(x, y, _comb_memo = {}):
" combinations of x things y at a time (0 if x<0, y<0, or y>x) "
try: return _comb_memo[x, y]
except KeyError:
if x<0 or y<0 or y>x: return 0
return _comb_memo.setdefault((x, y), fact(x) / (fact(y)*fact(x-y)))

# we represent a “honor” by a its points-worth

honors = [ p for p in range(1,5) for s in range(4) ]

# we represent a “honors set” by a pair (points-worth, total-#-of-cards)

def honor_subsets(lis, fromindex=0):
""" recursive generator of all sets from a list and starting point;
each set is represented by a honor-set as above, while the list
must hold points-worths representing “honors” again as above.
"""
ph = lis[fromindex]
if fromindex == len(lis)-1:
yield 0, 0
yield ph, 1
return
for pw, le in honor_subsets(lis, fromindex+1):
yield pw, le
yield ph+pw, 1+le

def main():
" main computation "
# hist: histogram points -> number of occurrences
hist = {}
# totcom: total number of occurrences
totcom = 0L
# range over all possible honorsets
for hs in honor_subsets(honors):
# compute number of honors and pointcount for this honorset
pt, nh = hs
# compute number of possible occurrences of this honorset
nc = comb(36, 13-nh)
# update histogram and total
hist[pt] = hist.get(pt, 0) + nc
totcom += nc
# print total and eyeball-check it
print totcom, comb(52, 13)

# sort histogram by decreasing frequency
aux = [ (nc, pt) for pt, nc in hist.iteritems() ]
aux.sort()
aux.reverse()

# compute frequencies as relative percentages
divis = 100.0 / totcom

# give top 10 possibilities
for nc, pt in aux[:10]:
print "%2d %d (%.2f)" % (pt, nc, nc * divis)

# run the computation

import time
start = time.time()
main()
stend = time.time()
print stend-start

and here is the corresponding optimized Ruby program:

# factorial, memoized via an Array

\$_fact_memo=[1,1,2,6,24,120,720]
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

# binomial factor (aka comb), memoized via a Hash

\$_comb_memo={}
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]]
if !result
return 0 if x<0 or y<0 or y>x
result = \$_comb_memo[[x, y]] = fact(x)/(fact(y)*fact(x-y))
end
return result
end

# a pair [total-pointcount, number-of-honors]

class Array
def each_subset(from=0)
if from==size-1:
#
# end of array, so, return 2 only possible subsets remaining:
# empty set, or singleton set with the last element in it
#
yield [0, 0]
yield [self[from], 1]
else
#
# 2+ elements remaining, so, loop iteratively, extracting
# the current element and getting all possible subsets of
# all later ones – for each of those, return 2 possible
# subsets, i.e., either without or with the current element
#
thispoints = self[from]
each_subset(from+1) do |subpoints, sublength|
yield subpoints, sublength
yield thispoints + subpoints, 1 + sublength
end
end
end
end

def main()
# main computation
# hist: histogram (Hash) points -> number of occurrences
hist = Hash.new(0)
# totcon: total number of occurrences
totcom = 0
# range over all possible honor-sets
honors = Array(1…4) * 4
honors.each_subset do |pt, nh|
# receive number of honors and pointcount for this honorset,
# then compute number of possible occurrences of this honorset
nc = comb(36, 13-nh)
# update histogram and total
hist[pt] += nc
totcom += nc
end
# print total and eyeball-check it
print totcom, ’ ', comb(52, 13), “\n”

# sort histogram by decreasing frequency
aux = hist.sort {|a,b| b[1]<=>a[1]}

# compute frequencies as relative percentages
divis = totcom / 100.0

# give top 10 possibilities
for pt, nc in aux[0,10]
printf "%2d %d (%.2f)\n" , pt, nc, nc/divis
end

end

# run the computation

start = Time.now
main
stend = Time.now
puts stend-start

Finally, FWIW, here’s the start of the profiler’s output…:

C:\Python23>ruby -rprofile alco2.rb
635013559600 635013559600
10 59723754816 (9.41)
9 59413313872 (9.36)
11 56799933520 (8.94)
8 56466608128 (8.89)
7 50979441968 (8.03)
12 50971682080 (8.03)
13 43906944752 (6.91)
6 41619399184 (6.55)
14 36153374224 (5.69)
5 32933031040 (5.19)
948.294
% cumulative self self total
time seconds seconds calls ms/call ms/call name
34.90 317.57 317.57 16 19848.44 909790.50 Array#each_subset
13.12 437.00 119.43 65537 1.82 6.56 Object#comb
10.56 533.11 96.11 131073 0.73 2.54 Hash#[]
8.20 607.70 74.59 65385 1.14 1.82 Array#eql?
8.11 681.49 73.79 65552 1.13 1.79 Array#hash
6.17 737.65 56.16 161735 0.35 0.35 Fixnum#+
4.87 781.99 44.34 130770 0.34 0.34 Numeric#eql?
4.80 825.63 43.65 131104 0.33 0.33 Kernel.hash
4.14 863.31 37.68 100426 0.38 0.38 Bignum#+
2.59 886.84 23.53 65551 0.36 0.36 Hash#[]=
2.48 909.38 22.54 65613 0.34 0.34 Fixnum#-
0.02 909.57 0.19 91 2.09 38.57 Object#fact
0.02 909.75 0.18 1 180.00 180.00
Profiler__.start_profile
0.02 909.92 0.17 1 170.00 190.00 Hash#sort
0.01 910.02 0.10 350 0.29 0.29 Fixnum#<
0.01 910.10 0.08 193 0.41 0.41 Hash#default
0.01 910.16 0.06 59 1.02 1.19 Fixnum#*

I’ve truncated starting from where the “%time” goes to 0.00.

Thanks for any feedback!

Alex

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

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

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):

def fact(x)
return 0 if x<0
\$fact_memo[x] ||= x*fact(x-1)
end

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.

The rest is more complex so I’ll quit while I’m ahead.

Ben

···

On Sunday, September 14, 2003, at 12:44 PM, Alex Martelli wrote:

Alex Martelli aleaxit@yahoo.com skrev den Mon, 15 Sep 2003 01:44:09 +0900:

So I start optimizing and squeezing every cycle I can – and I get
down to about 0.65 seconds for Python, 2.3 seconds for Ruby (best
case, for each of them). Eep – the ratio keeps increasing, so my
lack of sound Ruby instincts must be really hurting. Oh well, say
I, let’s try “ruby -rprofile”. EEK! After a couple of times where
I was convinced it had just seized up I decided to let it run all
the way – and it took almost 1000 seconds. Is a slowdown of over
400 times normal for Ruby profiling, or is something weird in my
installation…? (It’s the one-exe native Ruby 1.8 install for Win
which comes with a lot of goodies such as SciTE, Programming Ruby
in HTML-Help format, etc).

No, slowdowns in the range 20-500 times (depending on the code) is
to be expected. For speedier profiling you can try my rbprof profiler
which is part of AspectR. I haven’t updated it in 1.5 years or so
though so it might not work out-of-the-box. Its faster and gives more
information.

Anyway, the profiler’s output isn’t illuminating to me at all, so
that’s when I decide to turn to the famous Ruby community – I’m
sure you’ll find lots to critique in my Ruby program, particularly
with an eye to performance but not necessarily just that (I am
quite aware that I may be guilty of “coding Python in Ruby” – and
this may produce suboptimal performance and other issues).

While I doubt you should compare these languages on performance merits
and sincerely hope this post is not a subtle troll post (I assume it
isn’t so: Welcome to the Ruby community, Alex!) let’s give this a
try.

When it comes to performance I would first look at the algorithm. what
strikes me is that you can also parameterize on the point count
for each honor. This way you would not need to traverse all 2**16
combinations.

Second observation is that you should use Process.times.utime to time
this since you only want the time spent by the Ruby process.

Third observation is that I don’t like globals so I wrap the
fact and comb methods in a module.

Fourth is some minor changes to use common Ruby idioms.

So my version is:

module Comb

# memoize results for speed

FactMemo, CombMemo = [1, 1, 2, 6, 24, 120, 720], {}

# factorial

def Comb.fact(n)
return 0 if n < 0
FactMemo[n] ||= (n * fact(n-1))
end

# binomial factor (aka comb), memoized via a Hash

def Comb.comb(x, y)
return 0 if x<0 or y<0 or y>x
CombMemo[[x,y]] ||= fact(x)/(fact(y) * fact(x-y))
end
end

···

# [total-pointcount, number-of-honors, number-of-combs]

class Array
def each_subset(from=0)
v = self[from]
if from == length
yield 0, 0, 1
else
each_subset(from+1) do |pointcount, num_honors, num_combs|
(0…4).each do |m| yield pointcount + m*v, num_honors + m, num_combs * Comb.comb(4,m)
end
end
end
end
end
def main

# hist: histogram (Hash) points -> number of occurrences

histogram = Hash.new(0)

total_count = 0

# range over all possible honor-value-subsets

honor_values = (1…4).to_a
honor_values.each_subset do |pt, nh, count|
# receive number of honors and pointcount and combinations
# for this honor-value-set, then compute number of possible occurrences # of this honor-value-set
num_combs = count * Comb.comb(36, 13-nh)

# update histogram and total
histogram[pt] += num_combs
total_count += num_combs

end

# print total and eyeball-check it

print total_count, ’ ', Comb.comb(52, 13), “\n”

# sort histogram by decreasing frequency

aux = histogram.sort {|a,b| b[1]<=>a[1]}

# compute frequencies as relative percentages

divisor = total_count / 100.0

# give top 10 possibilities

aux[0,10].each do |point, count|
printf “%2d %d (%.2f)\n” , point, count, count / divisor
end
end

def time
start = Process.times.utime
yield
stend = Process.times.utime
stend-start
end

elapsed = time {main}
puts “#{elapsed} seconds”

and comparing that to your version (only changed to use Process.times.utime)
I get:

\$ time ruby am_better_timing.rb
635013559600 635013559600
10 59723754816 (9.41)
9 59413313872 (9.36)
11 56799933520 (8.94)
8 56466608128 (8.89)
7 50979441968 (8.03)
12 50971682080 (8.03)
13 43906944752 (6.91)
6 41619399184 (6.55)
14 36153374224 (5.69)
5 32933031040 (5.19)
0.531

real 0m0.553s
user 0m0.561s
sys 0m0.000s

feldt@novomundo1 /tmp/alex_martelli
\$ time ruby feldt.rb
635013559600 635013559600
10 59723754816 (9.41)
9 59413313872 (9.36)
11 56799933520 (8.94)
8 56466608128 (8.89)
7 50979441968 (8.03)
12 50971682080 (8.03)
13 43906944752 (6.91)
6 41619399184 (6.55)
14 36153374224 (5.69)
5 32933031040 (5.19)
0.0 seconds

real 0m0.033s
user 0m0.062s
sys 0m0.000s

and I’m ok with that so I’ll stop there for now. But the change
I did in the algorithm is also available for you in python so I guess
the ratio between the languages might not change much…

Best regards,

Robert Feldt

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

“Ben Giddings” bg-rubytalk@infofiend.com schrieb im Newsbeitrag
news:059CAA7E-E703-11D7-88E6-00039381462A@infofiend.com

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

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

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):

def fact(x)
return 0 if x<0
\$fact_memo[x] ||= x*fact(x-1)
end

Since recursions are costly and abort the interpreter for large n I
suggest this implementation:

def fact(n)
return 0 if n<1

@facts ||= [0,1]

last = @facts.size - 1

for i in @facts.size … n
@facts[i] = @facts[last] * i
last = i
end

@facts[n]
end

Regards

robert
···

On Sunday, September 14, 2003, at 12:44 PM, Alex Martelli wrote:

Robert Feldt wrote:

Fourth is some minor changes to use common Ruby idioms.

So my version is:

module Comb

# memoize results for speed

FactMemo, CombMemo = [1, 1, 2, 6, 24, 120, 720], {}

# factorial

def Comb.fact(n)
return 0 if n < 0
FactMemo[n] ||= (n * fact(n-1))
end

I like the fact you wrapped the functionality in a module, but if we’re
using Ruby idioms, the FactMemo and CombMemo variables should really not
be named with leading uppercase letters. They look like classes (or
constants) and may be treated as such by Ruby. I’d recommend instead
fact_memo and comb_memo.

Ben

Robert Feldt wrote:

While I doubt you should compare these languages on performance merits
and sincerely hope this post is not a subtle troll post…

I think Alex’s reputation in the Python community more than speaks for
the fact that he’s not a troll. This is a very reasonable question
about Python versus Ruby performance.

Ben Giddings 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

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
[] ||=
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

···

On Sunday, September 14, 2003, at 12:44 PM, Alex Martelli wrote:

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

svg% ruby -e 'a = {[1, 2] => 12}; p a.keys[0].class'
Array
svg%

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

then forget it

Guy Decoux

Alex Martelli wrote:

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

Simon is mistaken here. There may be some kind of
speed hit when storing an array as a hash key, but
the key is definitely stored as an array.

Hal

Lyle Johnson lyle@knology.net skrev den Mon, 15 Sep 2003 22:47:12 +0900:

While I doubt you should compare these languages on performance merits
and sincerely hope this post is not a subtle troll post…

I think Alex’s reputation in the Python community more than speaks for the fact that he’s not a troll. This is a very reasonable question about Python versus Ruby performance.

Ok. I hope it was clear that I wasn’t implying that he is.
My remark has nothing to do with Alex really; recent threads here on the list just makes “comparisons” between Ruby and Python a bit “infected” right now I guess.

Sorry if it came out the wrong way.

Then I guess we should be delighted that a python "hot-shot"
is willing to check Ruby out. Again: Welcome here, Alex.

Regards,

Robert

Ben Giddings bg-rubytalk@infofiend.com skrev den Mon, 15 Sep 2003 22:35:14 +0900:

So my version is:

module Comb

# memoize results for speed

FactMemo, CombMemo = [1, 1, 2, 6, 24, 120, 720], {}

# factorial

def Comb.fact(n)
return 0 if n < 0
FactMemo[n] ||= (n * fact(n-1))
end

I like the fact you wrapped the functionality in a module, but if we’re using Ruby idioms, the FactMemo and CombMemo variables should really not be named with leading uppercase letters. They look like classes (or constants) and may be treated as such by Ruby. I’d recommend instead fact_memo and comb_memo.

Yeah, I guess you’re right in a way. On the other hand they are constants since the array and the hash are the same objects
even if their contents change…

To me its more a question of what feels right than its about
what is more of a Ruby idiom. I could be wrong though…

The more logical to me following your thinking would be @fact_memo
and @comb_memo. Or to use the memoize extension.

/Robert

Dave Brown dagbrown@LART.ca skrev den Tue, 16 Sep 2003 02:48:04 +0900:

def fact(x)
@facts[x] ||= (1…x).inject(1) { |a,i| a*i }
end

Nice one. With the risc of losing readability here is an even
more efficient one:

@facts = [1]
def fact(n)
@facts[n] ||= (@facts.last…n).inject(1) {|f, i| @facts[i] = i * f}
end

since you won’t need to recalc more than the ones between largest memoized
and your new one. In practice this tweak would probably make
very little difference…

/Robert

Why not use a constant? In my unrolled implementation, that’s what I
do. It’s is a bit slower (but, as far as I can tell, not in the
unrolled implementations), but doesn’t take advantage of the
algorithmic shortcut hinted at in earlier messages.

FACT_MEMO = [1, 1, 2, 6, 24, 120, 720]

def fact!(x)
return 0 if x < 0
result = FACT_MEMO[x]

unless result
((FACT_MEMO.size)..x).each do |i|
FACT_MEMO[i] = i * FACT_MEMO[i - 1]
end
result = FACT_MEMO[x]
end

result

end

I’m sure there’s other improvements that can be done; I went for

If it’s not meant to be public at all, then since I’m using a class
here, I can use an instance variable (e.g., @fact_memo or
@fact_memo).

I’d much rather use a constant (FACT_MEMO) than a global
(_fact_memo). (This does point out a problem with the VIM syntax highlighting for Ruby, in that it doesn't properly highlight fact_memo because it finds \$.)

I don’t think that I’ve used a single global variable in my Ruby
programming.

I’m attaching my version to this message.

-austin

pointcount.rb (2.55 KB)

···

On Tue, 16 Sep 2003 02:07:53 +0900, Alex Martelli wrote:

Ben Giddings wrote:

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

austin ziegler * austin@halostatue.ca * Toronto, ON, Canada
software designer * pragmatic programmer * 2003.09.15
* 15.28.27

Ironically, I find @var far uglier than \$var - the @ is denser and
blockier, so it takes up a disproportionate amount of visual attention.

martin

···

Dave Brown dagbrown@lart.ca wrote:

It just makes it worse. The \$ is ugly for a reason–the use of
global variables is discouraged. The Ruby Way to do it would be

Alex Martelli wrote:

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

Sorry, I wasn’t completely clear. It’s the leading underscores that I
object to. I don’t mind underscores_in_names at all. The reason I
dislike leading underscores is that they tend to be holdovers to
languages that don’t have proper access control. (C mostly)

In any situation where someone is tempted to use them, I find that they
normally should be using something else (like using instance variables
which are by their nature private).

As for the ugliness of ‘\$’, it has been said that it is supposed to be
ugly. Global variables in general are ugly code, and so people tend to
avoid using ‘\$’, making their programs better.

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

Ah, I see what you mean. I’m sure you’re right that it’s faster the way
you now have it. I didn’t think things through fully and realize that
95% of the time the number will be positive and so it will have to
evaluate the conditional then do the array lookup. It is also going to
be much faster to do the array lookup rather than the triple
conditional for the “comb” case.

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.

Yeah. That “||=” is a little hard the first time you notice it, but
once you realize how useful it is, you’ll use it so often it becomes
second nature.

You could also use the other form, which as a C++ coder I’m sure you’d
recognize:

\$_fact_memo[x] ||= (x<0) ? 0 : fact(x-1)

Which also works in Ruby. I don’t like it as much, but it’s a
preference I guess.

Very good point, and an excellent suggestion at least for concision &
readability purposes – I’ll definitely keep the idiom
[] ||=
in mind for the future – thanks!

Note it also works for non container objects:

var ||= “new val”;

and in other types of expression:

var = other_var || “default val”

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;-)].

If you have the chance to try it on Ruby 1.8 I (and others I’m sure)
would be interested in hearing how it stacks up both to Python and to
Ruby 1.6.

(In another post) Alex Martelli wrote:

While I doubt you should compare these languages on performance merits
blink why not, pray? While clarity, productivity, simplicity, and so on,
are surely all crucial attributes in a language, what’s wrong with wanting
to ascertain how it performs (when used in the best/fastest way, at least)
in typical problems in one’s domains of interest…?

I don’t think that it’s wrong to compare the speed of the languages. I
just wouldn’t be surprised if Python is faster by a healthy margin,
especially for a very simple numerical program like this. In Ruby,
everything is an object, including numbers. This has certain
advantages, but definitely carries some speed penalties.

By using a scripting language rather than assembly or C, you’ve already
decided you’re willing to sacrifice some performance for ease of use. I
expect that both Perl and Python would beat Ruby in nearly any
benchmark, but I find Ruby much easier to use than both. For tasks
where a scripting language is appropriate, I choose Ruby.

ts wrote:

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) –

svg% ruby -e 'a = {[1, 2] => 12}; p a.keys[0].class’
Array
svg%

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

then forget it

…while remembering that some who post here may NOT be as knowledgeable
as Ruby as they sound by the certainty of their assertions (just like on
most other Usenet groups, of course). OK, thanks!

Alex

Hal Fulton wrote:

Alex Martelli wrote:

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

Simon is mistaken here. There may be some kind of
speed hit when storing an array as a hash key, but
the key is definitely stored as an array.

Ah! Good to know, thanks – I was (mistakenly, of course) taking all the
pronouncements of the c.l.ruby readership as if they came from Ruby
experts – unless of course corrected by others at the time I got to read
them (I always read news and mail backwards in time to cover for that),
while Simon’s remark had been left unchallenged until now. Still, the
move from [x,y] to x<<16+y did accelerate Ruby a bit (while the same
change slowed Python down a bit) so it does seem the “some kind of speed
hit” may in certain cases be (though not by much) noticeable.

Alex

Robert Feldt wrote:

Lyle Johnson lyle@knology.net skrev den Mon, 15 Sep 2003 22:47:12 +0900:

While I doubt you should compare these languages on performance merits

blink why not, pray? While clarity, productivity, simplicity, and so on,
are surely all crucial attributes in a language, what’s wrong with wanting
to ascertain how it performs (when used in the best/fastest way, at least)
in typical problems in one’s domains of interest…? A 10% or 20%
difference is hardly ever going to matter, but factors of 2 or 3 might
well make the difference, in practice, between two languages of otherwise
comparable merits – and that’s what I am observing here, so far (at least
in the toy/starting problem which I’m using as a warm-up exercise – we’ll
see what happens when I move to bigger and more interesting problems, e.g.
I cannot exclude that Ruby’s performance might “scale up” better, or
whatever).

and sincerely hope this post is not a subtle troll post…

I think Alex’s reputation in the Python community more than speaks for
the fact that he’s not a troll. This is a very reasonable question
about Python versus Ruby performance.

Ok. I hope it was clear that I wasn’t implying that he is.
My remark has nothing to do with Alex really; recent threads here on the
list just makes “comparisons” between Ruby and Python a bit "infected"
right now I guess.

Were there highly contentious threads on Ruby vs Python here recently?
Sorry, I did look around briefly for such recent things (mostly to avoid
re-asking what might have recently been answered) but didn’t find them
(maybe my ISP has expired them already, or maybe I made some mistake).

Sorry if it came out the wrong way.

No problem!

Then I guess we should be delighted that a python "hot-shot"
is willing to check Ruby out. Again: Welcome here, Alex.

Thanks! I’m always willing to check out new things (or else I’d hardly
have found Python 3+ years ago, being somewhat of a C++ “hot-shot” then;-),
and was interested in Python since Linux Magazine (without telling me in
advance) ran my Python article and Thomas and Hunt’s Ruby article smack
one against the other in the same issue. So I was quite glad to have the
opportunity to take Thomas’s Ruby tutorial at OSCON, get and study the
pickaxe book, and starting to try things out for real – the only way to
really learn a language (or other technology or tool), IMHO, particularly
with good support from an online community such as this one.

Alex

Robert Feldt feldt@ce.chalmers.se skrev den Tue, 16 Sep 2003 03:14:05 +0900:

@facts = [1]
def fact(n)
@facts[n] ||= (@facts.last…n).inject(1) {|f, i| @facts[i] = i * f}
end

Oops, it should be

@facts = [1]
def fact(n)
@facts[n] ||= (@facts.length…n).inject(@facts.last) {|f, i| @facts[i] = i * f}
end

/R