Ruby enumerable reverse detect

Question

assuming I have the following 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' }
]

assuming the array is ordered by viewed_at

If I want to retrieve the last view hash in the views array for a particular user_id, I could do the following:

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

where detect would returns first item in an enumerable where the block evaluates to true.

My question is: I assume there is O(n) cost to the reverse method, so how can I detect in reverse without having to reverse the array? Or is the reverse method not O(n)?

Answer 1

Method Array#reverse is O(n) in time and space. As you don't need the whole reversed array, you may use Array#reverse_each, that would be O(1) in space. In practice, that's only relevant for really big arrays.

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

Answer 2

This will get the index from the last object for which the block is true (or nil if none matches).

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

After benchmarking @toklands reverse_each is (surprising for me) a lot faster:

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)