From: Robert Feldt <feldt@...>
Date: 2003-09-15T20:25:59+09:00
Subject: Re: performance and style advice requested

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

#
# add to Array a recursive iterator over honor-value-subsets
#
# a honor is represented by its point-value (1..4); a honor-value-subset is
#  [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)
  # totcon: total number of occurrences
  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