Rubí enumerables inversa detectar

asumiendo Tengo la siguiente matriz:Rubí enumerables inversa detectar

views = [ 
    { :user_id => 1, :viewed_at => '2012-06-29 17:03:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:04:28 -0400' }, 
    { :user_id => 2, :viewed_at => '2012-06-29 17:05:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:06:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:07:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:08:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:09:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:16:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:26:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:36:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:47:28 -0400' }, 
    { :user_id => 2, :viewed_at => '2012-06-29 17:57:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:67:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:77:28 -0400' } 
]

suponiendo que la matriz está ordenada por viewed_at

Si quiero recuperar la última vista de hash en los vistas matriz para un particular user_id, podría hacer lo siguiente:

views.reverse.detect { |view| view[:user_id] == 1 }

donde detecta devolvería el primer elemento en un enumerable donde el bloque se evalúa como verdadero.

Mi pregunta es: Asumo que es O(n) costo para el método inverso, así que ¿cómo puedo detectar en sentido inverso sin tener que invertir la matriz? ¿O es el método inverso no O(n)?

Fuente

2012-06-29 Patrick Klingemann

lo que realmente tienen '17: 77' como un tiempo? –

Cuando encadena métodos, siempre desea encadenar enumeradores. La cadena del enumerador solo itera el objeto una vez y es O (n). El ejemplo más común es '" hola ".each_char.map {| x | x.succ}' – texasbruce

@texasbruce: eso será totalmente cierto con Ruby 2.0, donde todo tipo de operaciones perezosas serán posibles (ahora vuelven muchas operaciones) matrices, no enumeradores) – tokland

El método Array#reverse es O (n) en tiempo y espacio. Como no necesita toda la matriz invertida, puede usar Array#reverse_each, que sería O (1) en el espacio. En la práctica, eso solo es relevante para grandes arreglos.

views.reverse_each.detect { |view| view[:user_id] == 1 } 
#=> {:user_id=>1, :viewed_at=>"2012-06-29 17:77:28 -0400"}

Fuente

2012-06-29 21:25:45 tokland

esto es muy interesante. Vi el reverso de cada método en la documentación de Ruby 1.9.3 enumerable, pero su nombre implica que itera a través de cada objeto en un enumerable. Veo con tu ejemplo que no (potencialmente podría). ¿Le importaría explicar la diferencia entre el tiempo y el espacio en este contexto? ¡Gracias por tu respuesta! –

"su nombre implica que itera a través de cada objeto en un enumerable". 'cada 'método en Ruby es siempre flojo, iteran todo el enumerable si se le pide, pero aquí se detendrá cuando' detecte' deje de pedir más valores. "¿Te importaría explicar la diferencia entre el tiempo, un espacio en este contexto". Usando reverse_each: time) es posible que necesite atravesar toda la entrada para encontrar la que coincida, por lo que es O (n) lineal en el peor de los casos, espacio) solo necesita acumular el elemento actual que se está verificando, eso es O (1). Ejemplos en Python: http://wiki.python.org/moin/TimeComplexity – tokland

¡muchas gracias! –

Esto obtendrá el índice del último objeto para el que el bloque es verdadero (o nulo si ninguno coincide).

views.rindex{|view| view[:user_id] == 1}

Después @toklands evaluación comparativa es reverse_each (sorprendente para mí) mucho más rápido:

require 'benchmark' 
ar = Array.new(100){rand(100)} 
target = rand(100) 

Benchmark.bm(15) do |x| 
    x.report('reverse_each'){1000.times{ar.reverse_each.detect(target)}} 
    x.report('rindex'){1000.times{ar.rindex(target)}} 
end 


#      user  system  total  real 
#reverse_each  0.000000 0.000000 0.000000 ( 0.002981) 
#rindex   0.020000 0.000000 0.020000 ( 0.012078)

Fuente

2012-06-29 21:36:13 steenslag

eso es realmente sorprendente, conceptualmente es la misma operación, los tiempos deberían ser muy similares. – tokland

Respuesta

Cuestiones relacionadas