ruby - Ruby でのセット VS 配列のパフォーマンス

Question

Ruby では、重複する要素を含まない (おそらく大きい) 配列を構築して返すメソッドを構築しています。セットを使用してから配列に変換すると、パフォーマンスが向上しますか? それとも.uniq、使用している配列を返す前に呼び出すほうがよいでしょうか? または&、の代わりに配列にアイテムを追加するために使用するのは+=どうですか? <=>また、セットを使用する場合、セットに入れるオブジェクトにメソッドを持たないとパフォーマンスに影響しますか? （よくわからない場合は、これをテストする方法を知っていますか？）

Answer 1

本当の答えは、最も読みやすく保守しやすいコードを記述し、それがボトルネックであることを示した後でのみ最適化することです。線形時間のアルゴリズムを見つけることができれば、それを最適化する必要はありません。ここで見つけるのは簡単です...

どの方法を提案しているのかよくわかりませんが、私のfruity宝石を使用しています：

require 'fruity'
require 'set'

enum = 1000.times

compare do
  uniq { enum.each_with_object([]){|x, array| array << x}.uniq }
  set  { enum.each_with_object(Set[]){|x, set| set << x}.to_a }
  join { enum.inject([]){|array, x| array | [x]} }
end

# set is faster than uniq by 10.0% ± 1.0%
# uniq is faster than join by 394x ± 10.0

明らかに、3番目の方法のように中間配列を構築することは意味がありません。そうでなければ、あなたはにいるので、それは大きな違いを生むことはありませんO(n)。それが主なものです。

ところで、両方sets、uniqおよびをArray#|使用eql?しhash、オブジェクトではなく<=>。eql?デフォルトでは、オブジェクトが同じでない限りオブジェクトは存在しないため、これらは適切な方法で定義する必要がありますobject_id（この質問を参照） 。

Answer 2

Benchmarkライブラリを使用してみましたか? 通常、テストは非常に簡単に作成でき、Ruby の特定のバージョンでの動作を適切に反映します。