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.reverse.detect { |view| view[:user_id] == 1 }

where detectは、ブロックが true と評価される列挙型の最初の項目を返します。

私の質問は次のとおりです。逆の方法には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

これは、ブロックが true (一致しない場合は nil) である最後のオブジェクトからインデックスを取得します。

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

ベンチマーク後、@toklandsreverse_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 に答える