From: Aleksi Niemela <aleksi@...>
Date: 2001-05-07T02:44:20+09:00
Subject: [ruby-talk:14747] Re: Why's Ruby so slow in this case?

In [ruby-talk:14710] titled "Why's Ruby so slow in this case?"
Stefan Matthias Aust wrote:

> However, the following code needs more than 15 minutes to complete
> while the original C source runs in less than one second!

He also continues:

> I wonder whether there are some ways to optimize this code other than
> to completely change the algorithm.  Or can the Ruby interpreter be
> improved?  I'm using Ruby 1.6.4 if that matters.

The Ruby interpreter isn't as fast as it probably could be. I'm not
familiar with the details why and how much the interpreter itself is
slower than certain others. Neither do I know what limits the Ruby's
way for method searching imposes and how does that compare to others,
like Smalltalk.

So I'm afraid I have to say that there isn't any magic bullet to cure
all your speed problems. But there are couple of basic things you 
could try to do for optimizating your code, like:

1) reduce calling, as the searching the methods and restoring contexts
   take some time 

      def odd(x)
        x % 2 == 1
      end
      p odd(6)

   =>

      p (6%2 == 1)

2) move your hand-made logic to be done inside built-in methods

      100_000.times do
        a = (0..100).to_a
        b = []
        for i in 0..100
          b << a[i] if i%2 == 0
        end
      end

   =>

      100_000.times do
        a = (0..100).to_a
        b = a.collect do |i|
          i%2 == 0
        end
      end

3) instantiate as few objects as possible, as the garbage collecting
   takes considerable amounts of time


But as you indicated the best way around performance problems is
usually to rewrite the entire logic (replace the algorithm). When the
original took over minute to produce the 35x35 map, this version works
quite a bit faster and builds a 80x80 map under half a second on my
machine.

Here's a version I wrote. It's also a bit "rubified" compared to original.
No assurances of it's alikeness, as I didn't quite understand the
position logic for hexas.

    - Aleksi



class Hex
  attr_accessor :terrain
  def initialize(terrain = Terrain::Water)
    @terrain = terrain
  end
  def iswater?
    @terrain == Terrain::Water
  end
  def ==(hex)
    @terrain == hex.terrain
  end
end

module Terrain
  (Water, Plain, Forest, Mountain, ) = (0..100).to_a
  Terrains = [Water, Plain, Forest, Mountain]
end

class Map
  attr_accessor :map, :size, :shores

  def initialize(size)
    @size = size
    @map = (0...size*size).map{Hex.new}
    @shores = {}
    # add the initial terrain
    markTerrain(rand(@size), rand(@size), Terrain::Terrains[rand(3)+1])
  end

  def makeLand
    shores = @shores.keys
    h = shores[rand(shores.size)]
    markTerrain(h%@size, h/@size, Terrain::Terrains[rand(3)+1])
  end
  
  XD =   [ 0, +1, +1,  0, -1, -1]
  YD = [ [-1, -1,  0, +1,  0, -1],
         [-1,  0, +1, +1, +1,  0] ]
  def markTerrain(x, y, terrain)
    h = y*@size + x
    @map[h].terrain = terrain

    # this hex is certainly not an offshore anymore
    @shores.delete h

    # find new offshores
    yd = YD[x%2]
    6.times do |i|
      x1 = x + XD[i]
      y1 = y + yd[i]
      next unless x1 >= 0 && x1 < @size && y1 >= 0 && y1 < @size
      h = y1*@size + x1
      @shores[h] = 1 if @map[h].iswater?
    end
  end

  def to_s
    s = ""
    terrainChar = ['~', 'p', 'f', 'm']
    for y in (0...@size)
      for x in (0...@size)
	s.concat terrainChar[@map[y*@size + x].terrain]
      end
      s.concat "\n"
    end
    s
  end
  
end

def createMap
  size = 80
  map = Map.new(size)
  (size*size/2-1).times do map.makeLand end
  print map
end

createMap