Optimizando operaciones sobre vectores en Ruby con memoization

Ahora que estaba haciendo el clon del Missile Commander, me dieron ganas de implementar un movimiento más realista en los misiles.

En lugar de que simplemente tuvieran una velocidad lineal desde que salen hasta que explotan al llegar a su destino, quería que aceleraran a la hora de hacer su despegue.

Recordé que tengo un muy buen libro que habla sobre steering behaviors (comportamientos de dirección), y decidí implementarlos en Ruby.

Los steering behaviors usan mucha matemática de vectores, así que me puse a desarrollar una pequeña clase para realizar un par de cálculos comunes: longitud y normalización — conforme las necesite, le iré agregando otras operaciones útiles.

La clase Vector2d

Esta es la clasecita que me ayudará a darle vida a un sinnúmero de entidades virtuales en mis futuros proyectos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

require 'benchmark'
 
class Vector2d
  attr_reader :x, :y
 
  def initialize(x=0,y=0)
    clear_length
    @x = x
    @y = y
  end
 
  def clear_length
    @length = nil
    @length_sq = nil
  end
 
  def length
    Math.sqrt(length_sq)
  end
 
  def sub_memoized_length
    Math.sqrt(memoized_length_sq)
  end
 
  def memoized_length
    @length ||= Math.sqrt(length_sq)
  end
 
  def length_sq
    @x*@x + @y*@y
  end
 
  def memoized_length_sq
    @length_sq ||= @x*@x + @y*@y
  end
 
  def normalize
    Vector2d.new(@x/length, @y/length)
  end
 
  def normalize!
    @x = @x/length
    @y = @y/length
    clear_length
    self
  end
 
  def x=(x)
    clear_length
    @x = x
  end
 
  def y=(y)
    clear_length
    @y = y
  end
end
 
Benchmark.bm do |x|
  a = Vector2d.new(23,45)
 
  x.report do
    1.upto(1000000) do
      a.length
    end
  end
 
  x.report do
    1.upto(1000000) do
      a.sub_memoized_length
    end
  end
 
  x.report do
    1.upto(1000000) do
      a.memoized_length
    end
  end
end

Conforme la programaba se me ocurrió hacer unas optimizaciones, lo que dio como resultado los métodos que incluyen la palabra memoized en su nombre.

Hice unas benchmarks (pruebas de tiempo) —¡mi primer benchmark en Ruby! — para medir que tanto afectaban mis supuestas optimizaciones, y esto fue lo que descubrí:

1
2
3
4
5
6
7
8
9
10

-*- mode: compilation; default-directory: "~/development/gamedev/steering/" -*-
Compilation started at Wed Jul 29 23:52:19
 
/usr/bin/ruby -w /home/lobo/development/gamedev/steering/vehicle.rb 
      user     system      total        real
  1.460000   0.000000   1.460000 (  1.480273)
  1.310000   0.000000   1.310000 (  1.352205)
  0.270000   0.000000   0.270000 (  0.276391)
 
Compilation finished at Wed Jul 29 23:52:22

Una breve explicación

La prueba consistió en calcular la longitud de un vector determinado, un millón de veces.

La técnica de optimización usada se llama: Memoization.

En computación, memoization es una técnica de optimización que se usa principalmente para incrementar la velocidad de los programas de computadora al evitar que las llamadas repetidas a una función recalculen los resultados de entradas previamente procesadas.

El primer método medido:

1
2
3

  def length
    Math.sqrt(length_sq)
  end

Calcula calcula la raíz cuadrada cada vez que es llamado, además calcula la suma de los cuadrados de X y Y.
Tarda: 1.480273 segundos

El segundo método:

1
2
3

  def sub_memoized_length
    Math.sqrt(memoized_length_sq)
  end

Se ahorra el cálculo de los cuadrados de X y Y al guardar en una variable de instancia el cálculo realizado previamente.
Tarda: 1.352205 segundos

El tercer método:

1
2
3

  def memoized_length
    @length ||= Math.sqrt(length_sq)
  end

Se ahorra el cálculo de la raíz cuadrada mientras X y Y no cambien.
Tarda: 0.276391 segundos

¿Qué tal?

En los juegos es necesario hacer todas las optimizaciones posibles, ya que las operaciones se están realizando una y otra vez en cada ciclo del game loop.

Creo que estás me vendrán muy bien.

P.D. Estas pruebas fueron hechas con Ruby 1.9.

Artículos relacionados:

• Problemas con rake con Ruby 1.8 y Ruby 1.9 instalados
• lotu — Un framework para desarrollo de juegos en Ruby
• Cómo mostrar las sentencias SQL en la consola de Rails
• Programando un PBBG en Ruby & Rails
• Ruby steering behaviors