整数の集合演算が高速に行えるFigureSetをリリースしました。
整数の集合の演算が高速に行えるFigureSetをリリースしました。
https://github.com/tsukasaoishi/figure_set
以下でインストールできます。
sudo gem install figure_set
以前、Rejuicerというライブラリを作ったのですが、その中で集合演算を高速に行う必要があって、RejuicerSetというライブラリを作っていました。いろいろ触っていくうちに、RejuicerよりもRejuicerSetのほうが重要になってきたため、名前を変えて分離した上で改めてリリースすることにしました。
基本的にはRejuicerSetと大きく変わったところはありません。末端ノードで保持するデータを64ビットに対応させたことと、メモリの節約のために枝ノードが持つ腕の数を256から16に減らしています。また、いくつかのバグも修正しました。
Readmeを見れば使い方は一目瞭然かと思いますが、ざっくりと紹介すると以下のように使えます。
require 'figure_set'
set1 = FigureSet.new
set1 << 1
set1 << 3
set1.to_a #=> [1,3]
set2 = FigureSet.new([2,3,4])
set2.to_a #=> [2,3,4]
set_and = set1 & set2
set_and.size #=> 1
set_and.to_a #=> [3]
set_or = set1 | set2
set_or.size #=> 4
set_or.to_a #=> [1,2,3,4]
set1.empty? #=> false
set1.clear
set1.empty? #=> true
set1.to_a => []
処理速度に関しては、RejuicerSetと比較して大差ありません。集合の要素にもよりますが、0から100万までの間の3の倍数の集合と5の倍数の集合の、積集合、和集合の計算はすこし速くなっています。
figure_set and 0.001000 0.000500 0.001500 ( 0.001521)
rejuicer_set and 0.001800 0.001200 0.003000 ( 0.007694)
figure_set or 0.000800 0.000000 0.000800 ( 0.000836)
rejuicer_set or 0.002200 0.000000 0.002200 ( 0.004325)
まだパフォーマンス的にちょっと問題があるのでREADMEには載せていませんが、sampleというメソッドが用意されていてランダムに集合の中から指定した数の要素を取得することができます。
set = FigureSet.new((0...1000000).to_a)
set.sample(2) #=> [285093, 889242]
サンプル数が一桁ならパフォーマンスは問題になることはないと思います。RejuicerSetでは、to_aしたあとにランダムソートしてピックアップする必要がありましたが、それに比較すると相当に速いでしょう。