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

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

スポンサーリンク

— 環境 —
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

ベンチマーク計測の結果

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

上記テスト用配列の初期化の行では、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 という配列の場合、以下のような結果となる。ソート後の配列から取り出す際、重複のある値のうち最後の値が落ちる。

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

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

スポンサーリンク
私は以下の本で Ruby を覚えました。メタプログラミングRubyは入門を超える内容で難しめです。
スポンサーリンク
 
Twitterを使っていますのでフォローお願いたします!ブログの更新情報もつぶやいてます^^
(英語学習用)

Leave Your Message!