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

# add to Array a recursive iterator over honor-subsets

# a honor is represented by its point-value (1…4); a honor-subset is

# 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