문자열 비교가 정수 비교에 비해 왜 빠른가요?

최근 루비 프로젝트에서 나는 몇 시간을 보내고있다. 두 개의 큰 문자열 세트의 교차점을 세고있다.문자열 비교가 정수 비교에 비해 왜 빠른가요?

나는 내가 이해할 것이라고 생각했기 때문에 문자열 대신 정수를 비교하는 것이 합리적이라고 결정했다. (이 모든 문자열은 데이터베이스에 저장되어 있으며 쉽게 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

미쳤다고! 나는 항상 정수 비교가 훨씬 빨랐다 고 생각했다.

그래서 스택 세계에서 루비로 문자열 비교가 왜 더 빠른지 아무도 모른다면 궁금했다. 나는 정말로 당신의 생각을 듣는 것에 감사 할 것이다.

출처

2012-01-13 BananaNeil

교집합 조작의 속도에 우수한 비교 교차하는 소자의 개수에 의해 영향을받는 것으로 보인다.

더 작은 세트 (1000)에서 2000 개의 항목을 선택했기 때문에 정수 생성 코드가 교차 요소 수가 상당히 많습니다.

예를 들어, i1의 857 개 항목 중 755 개가 i2에서 복제되었지만 w1의 849 항목 중 2 개만 w2에서 중복되었습니다.

나는 간단한 변경을 실행하는 경우 : (W1있는 것으로 알려져있다 W2에 755 개 항목을 덤핑), 내 시스템에 결과 문자열 집합 연산을 보였다

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

가 동등한 훨씬 더 가까이 될를 정수 연산.

내 원래의 결과는 :

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

내 결과,

일부 도움이 되길 바랍니다. 두 가지 타이밍은 시스템의 다른 것들이 차이를 유발할 수 있다는 오류의 여백을 고려할 것입니다. 그것들은 본질적으로이 길이의 문자열과 같습니다.

출처

2012-01-13 11:58:22 Cyberfox

위대한 답변 .. 잘 쓰여지고 설명 적입니다. 도와 주셔서 감사합니다. :] – BananaNeil