たぐってつづる

配列内の重複する値を抽出する方法を測ってみた

Ruby | 21:12 |

Rubyで配列内の重複する値を抽出する方法

というエントリを見て触発されてベンチマークを取ってみました．

紹介されている方法は下記のようなコード

a = [1, 2, 3, 4, 5, 6, 5, 4]
a.uniq.map{|v| v if a.inject(Hash.new(0)) {|h, key| h[key] += 1; h}[v] >= 2}.compact

mapのブロック内でのイテレートはコストが高く，

下記のエントリのようにArray#indexとArray#rindex を使う方法が簡潔で早いと思います．

Rubyで配列から重複したモノ（要素）を抜き出す（Uniqの逆）

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

ついでに，上記エントリにある方法に追加して「Hashに集計して重複しないものを削除」

a.inject(Hash.new 0){|h, k| h[k] += 0; h}.delete_if{|k,v| v < 2}.keys

も測定してみました．

# delete_if の条件を変えて取り出す値を変更することを想定．

ベンチマーク用のコード

#! /usr/bin/env ruby
#-*- coding: utf-8 -*-

require 'benchmark'

class Array
  # (1) map内で集計
  def inject_in_map
    self.uniq.map{|v| v if self.inject(Hash.new(0)) {|h, k| h[k] += 1; h}[v] >= 2}.compact
  end

  # (2) Hashに集計して重複しないものを削除
  # Hash#select だとruby 1.8系では配列で返ってくるのでHash#delete_ifを採用
  def inject_delete_if
    self.inject(Hash.new 0){|h, k| h[k] += 0; h}.delete_if{|k,v| v < 2}.keys
  end

  # (3) Array#index Array#rindex を使う方法
  def index_rindex
    self.uniq.select{|e| self.index(e) != self.rindex(e)}.uniq
  end
end

# 1000回の反復ベンチマーク
n = 1000

# 配列サイズを4種
[10, 100, 1000, 10000].each {|size|
        # 対象となる配列は一桁の数値をランダムで
	a = size.times.collect{rand(10)}

	p "array size: #{a.size}"
	Benchmark.bm(16) do |x|
	  x.report("inject in map") {n.times do; a.inject_in_map; end}
	  x.report("inject delete_if") {n.times do; a.inject_delete_if; end}
	  x.report("index rindex") {n.times do; a.index_rindex; end}
	end
}

ベンチマーク結果

ベンチマークには，

• Macbook(2008) 2.4GHz Intel Core 2 Duo, Memory: 4GB, Snow Leopard
• ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]

を使いました．

予想していたように，反復が多いmap内でのinjectは処理が遅いようです．

追加してみたinject -> delete_if はHashを生成する分配列が大きくなると遅くなりますね．

単に重複だけ見る場合はArray#index とArray#rindexを使う方法が早いようです．

# Rubyらしくてもっといい書き方があれば知りたいです :-)

ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]
"array size: 10"
                      user     system      total        real
inject in map     0.060000   0.010000   0.070000 (  0.057868)
inject delete_if  0.010000   0.000000   0.010000 (  0.011259)
index rindex      0.010000   0.000000   0.010000 (  0.010686)

"array size: 100"
                      user     system      total        real
inject in map     0.370000   0.000000   0.370000 (  0.365121)
inject delete_if  0.030000   0.000000   0.030000 (  0.036980)
index rindex      0.030000   0.000000   0.030000 (  0.029389)

"array size: 1000"
                      user     system      total        real
inject in map     3.020000   0.010000   3.030000 (  3.056347)
inject delete_if  0.300000   0.000000   0.300000 (  0.298579)
index rindex      0.110000   0.000000   0.110000 (  0.107295)

"array size: 10000"
                      user     system      total        real
inject in map    29.840000   0.090000  29.930000 ( 30.700796)
inject delete_if  2.900000   0.010000   2.910000 (  2.910935)
index rindex      0.870000   0.000000   0.870000 (  0.921698)

ツイートする