Почему сравнение строк так быстро по сравнению с целочисленными?

Question

В проекте Ruby, на который я в последнее время проводил некоторое время, я подсчитывал пересечение двух больших наборов строк.

Исходя из того, что я понял, я решил, что будет иметь смысл сравнивать целые числа вместо строк (все эти строки хранятся в базе данных, и я легко могу их поменять наидентификаторы)

Когда я действительно провел сравнительный анализ, я обнаружил, что все наоборот.

Сначала я создал наборы из 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

Скорость заданной операции пересечения, по-видимому, зависит от количества пересекающихся элементов.

Ваш целочисленный код создания создает значительно большее количество пересекающихся элементов, возможно, потому что он выбирает 2000 записей из меньшегоset (1000).

Например, в одном тесте 755 из 857 записей в i1 были продублированы в i2, но только 2 из 849 записей в w1 были продублированы в w2.

Когда я запустил простое изменение:

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

(сброс 755 элементов в w2, которые, как известно, находятся в w1), результаты в моей системе показали, что операция набора строк была намного ближе к эквивалентной операции целого числа.

Мои исходные результаты были:

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]

Надеюсь, это поможет некоторым;эти два момента времени находятся в пределах того, что я бы посчитал допустимым пределом погрешности, что другие вещи в системе могут вызывать разницу.Они, по сути, равны для строк такой длины.

Answer 2

Причина в том, что он медленнее, в том, что вы не получаете столько подходящих предметов.Требуется время для создания нового массива пересечения, а не фактического сопоставления.

Answer 3

Целочисленные сравнения по-прежнему самые быстрые.
Проверьте эту ссылку:

• ruby-Сравнения-Benchmark , отличное сравнение на различных версиях Ruby