무책님의 커멘트도 있고 해서 String matching 방법에 대한 BM 테스트를 해봤습니다.
#!/usr/local/bin/ruby -w
require “benchmark”
str=”some stuff NL is chunky”
leagues=%w{1D 2D U16 U19 LR RR JNL NL}
N = 1000
puts “Short str: #{str}”
puts “Long pattern: #{leagues.join(“,”)}”
Benchmark.bmbm(10) { |x|
x.report(“select”) { for i in (1..N); leagues.select { |m| str.include?(m) }; end }
x.report(“&1”) { for i in (1..N); leagues & str.split; end }
x.report(“&2”) { for i in (1..N); str.split & leagues; end }
}
str2 = str
chars = (“A”..”Z”).to_a + (“a”..”z”).to_a + [” “]
for i in 1..N
if rand(10) < 1
str2 += " #{leagues[rand(leagues.length)]}"
else
str2 += chars[rand(chars.length)]
end
end
puts "\nLong str: #{str2}"
puts "Short pattern: #{leagues.join(",")}"
Benchmark.bmbm(10) { |x|
x.report("select") { for i in (1..N); leagues.select { |m| str2.include?(m) }; end }
x.report("&1") { for i in (1..N); leagues & str2.split; end }
x.report("&2") { for i in (1..N); str2.split & leagues; end }
}
leagues2 = leagues.clone
patterns = ("AA".."ZZ").to_a << " "
for i in 1..N
leagues2 << patterns[rand(patterns.length)]
end
puts "\nShort str: #{str}"
puts "Long pattern: #{leagues2.join(",")}"
Benchmark.bmbm(10) { |x|
x.report("select") { for i in (1..N); leagues2.select { |m| str.include?(m) }; end }
x.report("&1") { for i in (1..N); leagues2 & str.split; end }
x.report("&2") { for i in (1..N); str.split & leagues2; end }
}
puts "\nLong str: #{str2}"
puts "Long pattern: #{leagues2.join(",")}"
Benchmark.bmbm(10) { |x|
x.report("select") { for i in (1..N); leagues2.select { |m| str2.include?(m) }; end }
x.report("&1") { for i in (1..N); leagues2 & str2.split; end }
x.report("&2") { for i in (1..N); str2.split & leagues2; end }
}
[/code]
결과만 오려오면 다음과 같습니다.
(1) short str/short pattern
user system total real
select 0.010000 0.000000 0.010000 ( 0.013188)
&1 0.020000 0.000000 0.020000 ( 0.018512)
&2 0.020000 0.000000 0.020000 ( 0.015597)
(2) long str/short pattern
user system total real
select 0.020000 0.000000 0.020000 ( 0.020589)
&1 0.470000 0.000000 0.470000 ( 0.466879)
&2 0.280000 0.000000 0.280000 ( 0.272942)
(3) short str/long pattern
user system total real
select 1.520000 0.000000 1.520000 ( 1.523304)
&1 0.210000 0.000000 0.210000 ( 0.207155)
&2 0.730000 0.000000 0.730000 ( 0.727703)
(4) long str/long pattern
user system total real
select 14.360000 0.000000 14.360000 ( 14.811840)
&1 1.050000 0.000000 1.050000 ( 1.048801)
&2 1.200000 0.000000 1.200000 ( 1.202971)
일단 실험에서 str과 leagues를 1,000이란 매직 넘버를 가지고 늘렸는데 사실 이것도 단계적으로 100씩 늘리면서 제대로 해봐야겠지만 그정도의 정성은 없는지라 ㅎㅎ
대강 드러나는건 str이 길고 pattern이 짧으면 select가 빠르지만, str이 짧고 pattern이 길면 그 반대의 상황이 되며 둘 다 길면 & 가 가장 낫다는 것입니다. 이에 대해 어느 한쪽이 긴 경우에대해서는 설명을 잘 못하겠습니다. 아마도 어느쪽이 인접한 메모리를 사용하여 cpu에서의 캐시 히트를 높히는가라던가, 한번에 메모리에서 fetch하는 양이 어느쪽에서 유리한가의 문제일 것 같지만 설명은 못하겠네요. 그러나 & 의 경우에는 양쪽 array를 sort한다음 merge하므로 str과 pattern이 둘 다 길때 가장 빠르게 나온것이 아닌가 하는 추측을 해봅니다. (추측만 하는 것도 저의 정성이 부족하여;;)
Leave a Reply