Práctica: Matrices Dispersas

Considere el desarrollo de una aplicación que contemple la creación de Matrices. Se ha de utilizar una representación para matrices densas y otra diferente para matrices dispersas.

Una matriz se considerará dispersa si tiene más de un 60% de ceros. Se ha de establecer una relación de herencia entre las clases que se utilicen para su representación. Las operaciones básicas con matrices son diferentes en cada caso.

  1. El entregable de esta práctica tiene que ser una Gema Ruby. Véase Creando Gemas 90

  2. Partiendo de la implementación que se ha realizado en prácticas anteriores para Fracciones y Matrices reorganice el código.
  3. Escribir un conjunto de pruebas unitarias (Unit Testing) test/tc_ordenacion.rb. Véase Test/Unit 16.1

  4. Escribir un fichero de expectativas de comportamiento (TDD) spec/ordenacion_spec.rb. Véase Test Driven Development (TDD) y Rspec 17
  5. Comprobar el correcto funcionamiento en distintas plataformas (Continuous Integration) travis. Véase Integración Contínua: Travis 20 y Custom Bundler arguments and Gemfile locations 20.1
  6. Realizar un seguimiento continuo de las pruebas (Continuous Testing) guard. Véase Guard 21

Sugerencias:

[~/srcLPPruby/matrices_dispersas]$ cat sparse_matrix.rb 
require 'pp'

class SparseVector 
  attr_reader :vector

  def initialize(h = {})
    @vector = Hash.new(0)
    @vector = @vector.merge!(h)
  end

  def [](i)
    @vector[i] 
  end

  def to_s
    @vector.to_s
  end
end

class SparseMatrix 

  attr_reader :matrix

  def initialize(h = {})
    @matrix = Hash.new({})
    for k in h.keys do 
      @matrix[k] = if h[k].is_a? SparseVector
                     h[k]
                   else 
                     @matrix[k] = SparseVector.new(h[k])
                   end
    end
  end

  def [](i)
    @matrix[i]
  end

  def col(j)
    c = {}
    for r in @matrix.keys do
      c[r] = @matrix[r].vector[j] if @matrix[r].vector.keys.include? j
    end
    SparseVector.new c
  end
end

if __FILE__ == $0 
  z = SparseMatrix.new 1000 => { 100 => 1, 500 => 200}, 20000 => { 1000 => 3, 9000 => 200}
  puts "z[1000] = #{z[1000]}"
  puts "z[1000][1] = #{z[1000][1]}"
  puts "z[1000][500] = #{z[1000][500]}"
  puts "z.col(500) = #{z.col(500)}"
  puts "z.col(4000) = #{z.col(4000)}"

[~/srcLPPruby/matrices_dispersas]$ ruby sparse_matrix.rb 
z[1000] = {100=>1, 500=>200}
z[1000][1] = 0
z[1000][500] = 200
z.col(500) = {1000=>200}
z.col(4000) = {}

Casiano Rodriguez León 2015-01-07