Ruby可枚举的反向检测

Question

假设我有以下数组:

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

假设数组按照seen_at排序

如果我想检索特定user_id的views数组中的最后一个视图哈希,我可以执行以下操作:

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

其中,检测会返回第一个项目在一个枚举,其中块评估为true.

我的问题是:我认为反向方法有O(n)成本,所以如何反向检测而不必反转数组？或者相反的方法不是吗？O(n)

Answer 1

方法Array#reverse是时间和空间上的O(n).由于您不需要整个反转数组,因此可以使用Array#reverse_each,即空间中的O(1).在实践中,这仅适用于真正的大型阵列.

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