La forma más rápida de obtener el máximo valor de un Rango exclusivo en ruby ​​

Question

Ok, así que digamos que tiene un Rango muy grande en rubí. Quiero encontrar una manera de obtener el valor máximo en el Rango.

El rango es exclusivo (se define con tres puntos) lo que significa que no incluye el objeto final en sus resultados. Podría estar formado por Entero, Cadena, Tiempo o realmente cualquier objeto que responda a #<=> y #succ. (Que son los únicos requisitos para el objeto de inicio/fin en Rango)

He aquí un ejemplo de una gama exclusiva:

past = Time.local(2010, 1, 1, 0, 0, 0) 
    now = Time.now 
    range = past...now 

    range.include?(now) # => false 

Ahora sé que sólo podía hacer algo como esto para obtener el valor máximo:

range.max # => returns 1 second before "now" using Enumerable#max 

Pero esto llevará una cantidad de tiempo no trivial para ejecutar. También sé que puedo restar 1 segundo de lo que sea que sea el objeto final. Sin embargo, el objeto puede ser distinto de Time, y es posible que ni siquiera sea compatible con #-. Preferiría encontrar una solución general eficiente, pero estoy dispuesto a combinar un código de caso especial con una solución general (más sobre esto más adelante).

Como se mencionó anteriormente usando Range#last tampoco funcionará, porque es un rango exclusivo y no incluye el último valor en sus resultados.

El enfoque más rápido que podía pensar era la siguiente:

max = nil 
    range.each { |value| max = value } 

    # max now contains nil if the range is empty, or the max value 

Esto es similar a lo que Enumerable#max hace (que hereda de Campo), excepto que explota el hecho de que cada valor va a ser mayor que la anterior, por lo que podemos omitir el uso de #<=> para comparar cada valor con el anterior (la forma en que Range#max lo hace) ahorrando un poco de tiempo.

El otro enfoque en el que estaba pensando era tener un código de caso especial para tipos de rubí comunes como entero, cadena, hora, fecha, fecha y hora, y luego usar el código anterior como alternativa. Sería un poco feo, pero probablemente mucho más eficiente cuando se encuentren esos tipos de objetos porque podría usar la resta desde Range#last para obtener el valor máximo sin iterar.

¿Alguien puede pensar en un enfoque más eficiente/más rápido que esto?

Answer 1

La solución más simple que puedo pensar, que va a trabajar para incluyente, así como líneas exclusivas:

range.max 

algunas otras soluciones posibles:

range.entries.last 
range.entries[-1] 

Estas soluciones son O (n), y será muy lento para grandes rangos. El problema en principio es que los valores de rango en Ruby se enumeran utilizando el método succ iterativamente en todos los valores, empezando por el principio. Los elementos no tienen que implementar un método para devolver el valor anterior (es decir, pred).

El método más rápido sería encontrar el predecesor del último elemento (un O (1) solución):

range.exclude_end? ? range.last.pred : range.last 

Esto funciona solamente para los rangos que tienen elementos que implementan pred. Las versiones posteriores de Ruby implementan pred para enteros. Debe agregar el método usted mismo si no existe (esencialmente equivalente al código de caso especial que sugirió, pero un poco más fácil de implementar).

Algunos evaluación comparativa rápida muestra que este último método es el más rápido en muchos órdenes de magnitud para las gamas grandes (en este caso range = 1...1000000), porque es O (1):

          user  system  total  real 
r.entries.last      11.760000 0.880000 12.640000 (12.963178) 
r.entries[-1]      11.650000 0.800000 12.450000 (12.627440) 
last = nil; r.each { |v| last = v } 20.750000 0.020000 20.770000 (20.910416) 
r.max        17.590000 0.010000 17.600000 (17.633006) 
r.exclude_end? ? r.last.pred : r.last 0.000000 0.000000 0.000000 ( 0.000062) 

Benchmark code is here.

En los comentarios se sugiere utilizar range.last - (range.exclude_end? ? 1 : 0). Funciona para fechas sin métodos adicionales, pero nunca funcionará para rangos no numéricos. String#- no existe y no tiene sentido con los argumentos enteros. String#pred, sin embargo, can be implented.

Answer 2

no estoy seguro acerca de la velocidad (y las pruebas iniciales no parecen increíblemente rápido), pero el siguiente podría hacer lo que necesita:

past = Time.local(2010, 1, 1, 0, 0, 0) 
now = Time.now 
range = past...now 

range.to_a[-1] 

prueba muy básico (contando en mi cabeza) mostraron que tomó aproximadamente 4 segundos mientras que el método que proporcionó tomó alrededor de 5-6. Espero que esto ayude.

Editar 1: Se eliminó la segunda solución porque era totalmente incorrecta.

Answer 3

No puedo pensar que haya forma de lograr esto que no implique enumerar el rango, al menos a menos que, como ya se mencionó, tenga otra información sobre cómo se construirá el rango y, por lo tanto, pueda inferir el valor deseado sin enumeración. De todas las sugerencias, iría con #max, ya que parece ser más expresivo.

require 'benchmark' 
N = 20 
Benchmark.bm(30) do |r| 
    past, now = Time.local(2010, 2, 1, 0, 0, 0), Time.now 
    @range = past...now 
    r.report("range.max") do 
    N.times { last_in_range = @range.max } 
    end 
    r.report("explicit enumeration") do 
    N.times { @range.each { |value| last_in_range = value } } 
    end 
    r.report("range.entries.last") do 
    N.times { last_in_range = @range.entries.last } 
    end 
    r.report("range.to_a[-1]") do 
    N.times { last_in_range = @range.to_a[-1] } 
    end 
end 
           user  system  total  real 
range.max      49.406000 1.515000 50.921000 (50.985000) 
explicit enumeration   52.250000 1.719000 53.969000 (54.156000) 
range.entries.last    53.422000 4.844000 58.266000 (58.390000) 
range.to_a[-1]     49.187000 5.234000 54.421000 (54.500000) 

Me di cuenta de que la tercera y cuarta opción han aumentado significativamente el tiempo del sistema. Supongo que eso está relacionado con la creación explícita de una matriz, lo que parece ser una buena razón para evitarlos, incluso si obviamente no son más caros en el tiempo transcurrido.