Old Emmanuel Oga's Weblog (new one is at www.emmanueloga.com)

Sets en ruby

Posted in Uncategorized by emmanueloga on septiembre 5, 2007

En una aplicacion necesitaba crear “sets” de valores conocidos.

Cada vez que creaba un valor nuevo, lo agregaba al set para saber que ya lo habia procesado. Algo asi:

valores=["1", "2", "3", "4", "2", "4", "6", "1", "2", "3"]

set= []

valores.each do |val|
if !set.include? val.intern
set << val.intern
puts(val) # > 1 2 3 4 6
end
end

Ok! Todo perfecto. El asunto es que el metodo include? de array esta implementado como una busqueda lineal de su contenido, por lo cual su tiempo de busqueda es O(n), busqueda lineal.

Me han preguntado porque no usar valores.uniq. “valores” es solo una fuente de valores dispersos cualquiera. En este caso, los he metido en un array, pero estos valores podrian no siempre estar todos juntos en un array: los valores para el set podrian venir de cualquier fuente. Por otro lado, Array.uniq conserva el problema que quiero solucionar: su implementacion se basa en una busqueda lineal ya que los elementos de un array no siempre estan ordenados. En esencia, Array.uniq funciona igual que el codigo anterior.

Bien, la solucion logica es usar un hash, cuyo tiempo de busqueda es O(log n), ya que implementa una busqueda binaria:

valores=["1", "2", "3", "4", "2", "4", "6", "1", "2", "3"]

set= {}

valores.each do |val|
if !set.has_key? val.intern
set[val.intern]= nil
puts(val) # > 1 2 3 4 6
end
end

El truco aca es asignarle a la key del hash el valor nil. No necesitamos asociar datos a la key sino mantener un listado de keys. Al asociar una key con nil, esta devuelve nil al indexar el hash por su valor (igual que si no estuviera). La diferencia es que al preguntar has_key? devolvera true independientemente de su valor asociado, y figurara en la lista de keys del hash (has.keys).

Aun asi, esta solucion se me hacia un poco desprolija. Estaba a punto de escribir una clase Set basada en Hash cuando se me ocurrio escribir en mi linea de comandos “qri Set”. Voila!

> qri Set
---------------------------------------------------------- Class: Set
Set implements a collection of unordered values with no duplicates.
This is a hybrid of Array's intuitive inter-operation facilities
and Hash's fast lookup.

Several methods accept any Enumerable object (implementing +each+)
for greater flexibility: new, replace, merge, subtract, |, &, -, ^.

The equality of each couple of elements is determined according to
Object#eql? and Object#hash, since Set uses Hash as storage.

Finally, if you are using class Set, you can also use
Enumerable#to_set for convenience.

Excelente! no tengo que trabajar🙂 La clase set implementa el metodo que yo usaba, excepto que en vez de usar nil como valor asociado a la key usa true. A efectos practicos, es lo mismo.

Un ultimo tema es el asunto del .intern que adjunto a la llave. Me acostumbre a usar symbols como keys de mis hashes, por lo que tengo como una especie de reflejo de agregar .intern a todas las strings que encuentro en mis programas!

El tema es que al indexar un hash con una string, el .intern no es necesario: la cadena es tratada como inmutable. Conclusion: puedo remover el .intern de mis keys sin cargos de conciencia.

Ojo! esto no quiere decir que indexando el hash como string o como symbol devolvera lo mismo.

Lo que quiere decir es que puedo hacer lo siguiente:

hash= {}
key= "HOLA"
hash[key]= "QUE TAL"
key= "CHAU"
hash["CHAU"] # >> ni
hash[key] # >> nil
hash["HOLA"] # >> "QUE TAL"
hash[:HOLA] # >> nil

Ok, la version final seria:

require 'set'

valores=["1", "2", "3", "4", "2", "4", "6", "1", "2", "3"]

set= Set.new

valores.each do |val|
if !set.has_key? val.intern
set << val.intern
puts(val) # > 1 2 3 4 6
end
end

Por ultimo, un pequeño benchmark para que comparen los resultados:

indexando 10.000 valores
user system total real
hash .intern 0.141000 0.000000 0.141000 ( 0.141000)
hash String 0.156000 0.000000 0.156000 ( 0.156000)
Set intern 0.188000 0.000000 0.188000 ( 0.187000)
Set String 0.203000 0.000000 0.203000 ( 0.202000)
array String 28.313000 0.000000 28.313000 ( 28.678000)
array intern 26.844000 0.000000 26.844000 ( 27.883000)

Removemos los array para comparar sets y hashes cuando estoy indexando mas valores:

indexando 100.000 valores!
user system total real
hash String 1.875000 0.000000 1.875000 ( 1.871000)
hash .intern 1.922000 0.015000 1.937000 ( 1.933000)
Set String 2.141000 0.015000 2.156000 ( 2.151000)
Set intern 2.282000 0.016000 2.298000 ( 2.291000)

Mi conclusion es que, aunque la indireccion agregada por Set genera un pequeño overhead, vale la pena en virtud de la sintaxis mas correctosa.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: