của Ruby đếm ngược phát hiện

Question

giả sử tôi có các mảng sau:

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

giả sử mảng được sắp xếp theo viewed_at

Nếu tôi muốn lấy lại băm xem cuối cùng trong xem mảng cho cụ thể user_id, tôi có thể làm như sau:

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

trong đó phát hiện sẽ trả về mục đầu tiên trong một liệt kê trong đó khối đánh giá là đúng.

Câu hỏi của tôi là: Tôi giả sử có O(n) chi phí cho phương thức đảo ngược, vậy làm thế nào tôi có thể phát hiện ngược lại mà không phải đảo ngược mảng? Hoặc là phương pháp đảo ngược không phải là O(n)?

Answer 1

Phương pháp Array#reverse là O (n) theo thời gian và không gian. Vì bạn không cần toàn bộ mảng bị đảo ngược, bạn có thể sử dụng Array#reverse_each, đó sẽ là O (1) trong không gian. Trong thực tế, điều đó chỉ phù hợp với các mảng thực sự lớn.

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

Answer 2

Điều này sẽ lấy chỉ mục từ đối tượng cuối cùng mà khối đó là đúng (hoặc không nếu không khớp).

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

Sau benchmarking @toklands reverse_each là (đáng ngạc nhiên đối với tôi) nhanh hơn rất nhiều:

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)