与整数比较相比,为什么字符串比较如此之快？

Question

在我最近花了一些时间的Ruby项目中,我一直在计算两组大字符串的交集.

根据我的理解,我认为比较整数而不是字符串会很有意义(所有这些字符串都保存在数据库中,我可以很容易地将它们换成ID)

当我实际进行基准测试时,我最终找到了相反的结果.

首先,我生成了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]}

(将755个项目转储到已知在w1中的w2中),我的系统上的结果显示字符串集合操作更接近等效整数操作.

我原来的结果是:

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

在交叉元素方面使两组集更相似之后的结果,通过:

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]

我希望有所帮助; 这两个时间是在我认为的误差范围内,系统上的其他东西可能导致差异.对于这个长度的字符串,它们基本上是相等的.