8

假设我有以下数组：

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

假设数组按viewed_at排序

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

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

其中检测将返回块评估为真的可枚举中的第一项。

我的问题是：我假设反向O(n)方法是有成本的，那么我怎样才能反向检测而不必反转阵列？还是相反的方法不是？O(n)

4

2 回答 2

23

方法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"}
于 2012-06-29T21:25:45.187 回答
1

这将从块为真的最后一个对象中获取索引（如果没有匹配，则为 nil）。

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

在对@toklands 进行基准测试之后reverse_each（令我惊讶的是）要快得多：

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)
于 2012-06-29T21:36:13.060 回答