配列内の重複する値を抽出する方法を測ってみた
というエントリを見て触発されてベンチマークを取ってみました.
紹介されている方法は下記のようなコード
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)