Rubino enumerabile inverso rilevare

Question

assumendo Ho il seguente array:

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' } 
] 

assumendo l'array è ordinato da viewed_at

Se voglio recuperare l'ultima vista hash nei viste array per un particolare user_id, potrei fare quanto segue:

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

dove rileva restituisce il primo elemento in una enumerazione in cui il blocco restituisce true.

La mia domanda è: suppongo ci sia il costo O(n) al metodo inverso, quindi come posso rilevare al contrario senza dover invertire l'array? Oppure il metodo inverso non è O(n)?

Answer 1

Il metodo Array#reverse è O (n) nel tempo e nello spazio. Dato che non è necessario l'intero array invertito, è possibile utilizzare , che sarebbe O (1) nello spazio. In pratica, ciò è rilevante solo per array molto grandi.

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

Answer 2

Questo otterrà l'indice dall'ultimo oggetto per il quale il blocco è vero (o nullo se nessuno corrisponde).

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

Dopo @toklands di benchmarking reverse_each è (sorprendente per me) molto più veloce:

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)