Ruby przeliczalny odwrotnej wykryć

Question

zakładając Mam następującą tablicę:

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

zakładając tablicy jest sortowana według viewed_at

Jeśli chcę odzyskać ostatnią hash widok w poglądów tablica dla konkretny user_id, mógłbym wykonać następujące czynności:

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

gdzie wykryje, że zwróci pierwszy element w liczbie wyliczeniowej, gdzie blok jest prawdziwy.

Moje pytanie brzmi: Zakładam, że jest O(n) koszt metody odwrotnej, więc jak mogę wykryć w odwrotnej bez konieczności odwrócenia tablicy? Czy jest to metoda odwrócona, a nie ?

Answer 1

Metoda Array#reverse jest O (n) w czasie i przestrzeni. Ponieważ nie potrzebujesz całej odwróconej macierzy, możesz użyć Array#reverse_each, czyli O (1) w przestrzeni. W praktyce ma to znaczenie tylko w przypadku naprawdę dużych tablic.

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

Answer 2

Spowoduje to pobranie indeksu z ostatniego obiektu, dla którego blok jest prawdziwy (lub zero, jeśli żaden nie pasuje).

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

Po benchmarkingu @toklands reverse_each jest (zaskakujące dla mnie) dużo szybciej:

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)