なぜ文字列比較は整数比較に比べて速いのですか？

Question

最近私が少し時間を費やしてきたRubyプロジェクトでは、2つの大きな文字列の交点を数えています。

文字列の代わりに整数を比較するのは大変意味があると判断しました（これらの文字列はすべてデータベースに保持されていますが、簡単にidsの代わりに使用できます）

私が実際にベンチマークをしたとき、私は完全な反対を見つけることになった。

まず私は850の文字列、および〜850大きな整数の集合の集合生成：

r = Random.new 
w1 = (1..850).collect{|i| w="";(0..3).collect{|j| (rand*26 + 10).to_i.to_s(35)}.each{|l| w+=(l.to_s)};w}.to_set 
w2 = (1..850).collect{|i| w="";(0..3).collect{|j| (rand*26 + 10).to_i.to_s(35)}.each{|l| w+=(l.to_s)};w}.to_set 

i1 = (1..2000).collect{|i| (r.rand*1000).to_i**2}.to_set; 
i2 = (1..2000).collect{|i| (r.rand*1000).to_i**2}.to_set; 

をし、私は比較を時限：

私はクレイジーだと思った

t=Time.now;(0..1000).each {|i| w1 & w2};Time.now-t 
=> 0.301727 
t=Time.now;(0..1000).each {|i| i1 & i2};Time.now-t 
=> 0.70151 

！私はいつも整数比較がずっと速かったと思った。

だから、スタックの世界の誰かが、文字列の比較がルビーのほうがずっと速いのかどうか知っていたのだろうか、本当にあなたの考えを聞いていただければ幸いです。

Answer 1

積集合演算の速度に優れた比較が交差する要素の数によって影響されるようです。

あなたの整数作成コードは、より小さいセット（1000）から2000個のエントリを選択しているため、おそらくより多くの交差要素を作成しています。

たとえば、i1の857エントリのうち755個がi2に複製されましたが、w1の849エントリのうち2つだけがw2に複製されました。

私は、単純な変更走ったとき：

755.times {|x| w2 << w1.to_a[x]} 

（W1であることが知られているW2に755の項目をダンプする）、私のシステム上の結果が同等に非常に近くなるように、文字列の集合演算を示したが整数演算。

私のオリジナルの結果は以下の通りであった：

1.9.2p180 :051 > 755.times {|x| w2 << w1.to_a[x]} 
1.9.2p180 :052 > w2 = w2.to_a[-849..-1].to_set 

であった：

1.9.2p180 :053 > t=Time.now;(0..1000).each {|i| w1 & w2};Time.now-t 
=> 2.014967 
1.9.2p180 :054 > t=Time.now;(0..1000).each {|i| i1 & i2};Time.now-t 
=> 2.037542 
1.9.2p180 :055 > [i1.length, i2.length, w1.length, w2.length, (i1 & i2).length, (w1 & w2).length] 
=> [857, 884, 849, 849, 755, 754] 

を介して交差する要素の点でより似組の二組を行った後

1.9.2p180 :006 > t=Time.now;(0..1000).each {|i| w1 & w2};Time.now-t 
=> 1.020355 
1.9.2p180 :007 > t=Time.now;(0..1000).each {|i| i1 & i2};Time.now-t 
=> 2.057535 

私の結果、

私はいくつか役立つことを願っています。 2つのタイミングは、システム上の他のものがその違いを引き起こす可能性があるという誤差の余裕を考慮する範囲内である。これらは、本質的に、この長さのストリングに対して等しい。

Answer 2

まだ整数比較が最も高速です。このリンクアウト
チェック：

• ruby-comparisons-benchmark、種々のRubyバージョン

Answer 3

それよりも遅いのは、一致するアイテムが多くないからです。時間がかかるのは、実際の照合そのものではなく、新しい交点の配列を構築することです。