更新日: 2014年2月12日
Ruby

Ruby の配列で重複する値のみを取り出す

Array#uniq の反対のようなことがやりたくて調べました。配列内から、重複する値のみを抽出して配列を返す処理。一発で取り出せるメソッドはなさそうだったので、二通りの書き方を試してベンチマークを取ってみました。

【お知らせ】英単語を画像イメージで楽に暗記できる辞書サイトを作りました。英語学習中の方は、ぜひご利用ください！

画像付き英語辞書 Imagict | 英単語をイメージで暗記
【開発記録】
英単語を画像イメージで暗記できる英語辞書サービスを作って公開しました

— 環境 —
Ruby 2.0.0
Macbook Air 2012 mid
プロセッサ 1.8 GHz Intel Core i5
メモリ 4 GB 1600 MHz DDR3

ベンチマーク計測用のスクリプトを作成

1つ目は、index, rindex を使う方法。2つ目は、ソートして前後の値を比較する単純な方法。

extract_overlaps.rb

require 'benchmark'

a = ((1..10000).to_a + (3001..8000).to_a + (5001..6000).to_a).shuffle
puts "data size: #{a.size}"

Benchmark.bm do |bench|
  overlaps = []
  bench.report("index:") do
    overlaps = a.select{ |i| a.index(i) != a.rindex(i) }
  end
  puts "index overlaps all: #{overlaps.size}"
  puts "index overlaps uniq: #{overlaps.uniq.size}"

  overlaps = []
  bench.report("sort:") do
    a.sort!
    overlaps = a.select.with_index{ |e,i| e==a[i+1] }
    overlaps += overlaps.uniq
  end
  puts "sort overlaps all: #{overlaps.size}"
  puts "sort overlaps uniq: #{overlaps.uniq.size}"
end

require 'benchmark'

a = ((1..10000).to_a + (3001..8000).to_a + (5001..6000).to_a).shuffle

puts "data size: #{a.size}"

Benchmark.bm do |bench|

overlaps = []

bench.report("index:") do

overlaps = a.select{ |i| a.index(i) != a.rindex(i) }

end

puts "index overlaps all: #{overlaps.size}"

puts "index overlaps uniq: #{overlaps.uniq.size}"

overlaps = []

bench.report("sort:") do

a.sort!

overlaps = a.select.with_index{ |e,i| e==a[i+1] }

overlaps += overlaps.uniq

end

puts "sort overlaps all: #{overlaps.size}"

puts "sort overlaps uniq: #{overlaps.uniq.size}"

end

ベンチマーク計測の結果


$ ruby extract_overlaps.rb
data size: 16000
       user     system      total        real
index:  7.410000   0.000000   7.410000 (  7.413552)
index overlaps all: 11000
index overlaps uniq: 5000
sort:  0.000000   0.000000   0.000000 (  0.006221)
sort overlaps all: 11000
sort overlaps uniq: 5000

$ ruby extract_overlaps.rb

data size: 16000

user system total real

index: 7.410000 0.000000 7.410000 ( 7.413552)

index overlaps all: 11000

index overlaps uniq: 5000

sort: 0.000000 0.000000 0.000000 ( 0.006221)

sort overlaps all: 11000

sort overlaps uniq: 5000

ベンチマーク計測の結果、2つ目の sort を使う単純な方法が遥かに速いです。一応計算結果に間違いないことを確認するため、それぞれ overlaps all, overlaps uniq のサイズを出力しています。

a = ((1..10000).to_a + (3001..8000).to_a + (5001..6000).to_a).shuffle

1	a = ((1..10000).to_a + (3001..8000).to_a + (5001..6000).to_a).shuffle

上記テスト用配列の初期化の行では、16000件の値からなる配列を作成しています。5001〜6000 の値は各々重複する値が3つ、3001〜5000 と 6001〜8000 は重複する値が2つとなります。で、最後にシャッフル。

ベンチマーク1つ目 a.select{ |i| a.index(i) != a.rindex(i) } の書き方は検索して知ったのですがカッコイイ。しかし、これは計算回数が多くなり、配列のサイズが大きいと遅くなると思う。

自分で思いついたのは、Benchmark スクリプトの2つ目、素朴に配列を sort した後、次の値と比べるという単純な方法だったのですけど、こちらの方がやはり遥かに高速です。ただし、重複する値が n 個だった場合 n-1 個が抽出されます。

例えば、[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5].shuffle という配列の場合、以下のような結果となる。ソート後の配列から取り出す際、重複のある値のうち最後の値が落ちる。


pry(main)> a = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5].shuffle
=> [5, 3, 2, 3, 4, 3, 4, 1, 4, 4, 2]
pry(main)> a.sort!
=> [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5]
pry(main)> a.select.with_index{ |e,i| e==a[i+1] }
=> [2, 3, 3, 4, 4, 4]

pry(main)> a = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5].shuffle

=> [5, 3, 2, 3, 4, 3, 4, 1, 4, 4, 2]

pry(main)> a.sort!

=> [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5]

pry(main)> a.select.with_index{ |e,i| e==a[i+1] }

=> [2, 3, 3, 4, 4, 4]

本来は、[2, 2, 3, 3, 3, 4, 4, 4, 4] と抽出して欲しい場合もあるかもしれません。この問題を解消するために、overlaps += overlaps.uniq として、重複した各々の値を1つずつ足してやってます。配列の足し算ができる Ruby 素晴らしい。

ということで、sort のほうを使用することにしました。