Ruby Enumerated Reverse Detection

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 sorted by viewed_ax

If I want to get the last hash in the views array for a specific user_id , I could do the following:

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

where discovery returns the first element in an enumerable, where the block evaluates to true.

My question is: I assume that there is O(n) cost of the reverse method, so how can I detect in the opposite direction without changing the array? Or is the reverse method not O(n) ?

Answer 1

The Array#reverse method is O (n) in time and space. Since you do not need the entire inverse array, you can use Array # reverse_each , which will be O (1) in space. In practice, this applies only to really large 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 it is not).

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

After benchmarking @toklands reverse_each (surprisingly for me) is much 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)