Menu
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)?
631
Array#select() : select() is a Array class method which returns a new array containing all elements of array for which the given block returns a true value. Return: A new array containing all elements of array for which the given block returns a true value.
In Ruby, we call an object enumerable when it describes a set of items and a method to loop over each of them. The built-in enumerables get their enumeration features by including the Enumerable module, which provides methods like #include? , #count , #map , #select and #uniq , amongst others.
What you are seeing is the & operator applied to a :symbol . In a method argument list, the & operator takes its operand, converts it to a Proc object if it isn't already (by calling to_proc on it) and passes it to the method as if a block had been used.
Some Ruby classes include Enumerable: Array. Dir. Hash.
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"}
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
