Ruby
英文原文：
Ruby Is Too Slow for Programming Competitions
上个周末，我参加了Google Code Jam 2013的资格赛。今年是我第三次参加了，也是我使用Ruby作为主要语言的第三个年头。
因为之前没有参加编程竞赛的经验，再加上我工作中使用Ruby，所以我从来没想过选择别的语言。当然，我早就知道Ruby不是那么的快，但我始终认为只要选择了正确的解决方案并且写出高效的代码（内存空间，值存取，限制搜索空间等等），比起处理速度而言，更让人担心的是我是否能快速地写出简洁的代码。
我错了.
2013资格赛的问题C 叫‘Fair and Square’, 简单讲就是:
给定数字X和Y，返回其中包括多少个数字，数字本身是回文数，同时也是另一个回文数的平方。
Given two numbers X and Y, return how many numbers in that range
(inclusive) are palindromes, and also the square of a palindrome.
这个问题看起来很简单明了.很明显，我需要一个函数判断一个给定的数字是否是回文数。所以，我比较了两个函数的性能，一个先转换为字符串再判断是否是回文，一个使用整数计算来判断是否是回文数，因为我听说计算机做整数计算相当快.
Rehearsal -------------------------------------------------------------
Integer palindrome method 7.700000 0.000000 7.700000 ( 7.705190)
String palindrome method 4.890000 0.010000 4.900000 ( 4.907374)
--------------------------------------------------- total: 12.600000sec
user system total real
Integer palindrome method 7.770000 0.000000 7.770000 ( 7.773088)
String palindrome method 4.720000 0.010000 4.730000 ( 4.726223)
该测试的源码
在过去的编码大赛中，当可以使用整数计算时，如果我用了字符串来处理就会被搞得很受伤。所以这个结果使我很吃惊。但是，毕竟数字不会说谎，而且现在我需要写出高效率的Ruby代码，所以这个测试结果还是很有用的。
很快, 我写了一个Ruby程序测试通过了示例输入，以及小输入集.
def string_palindrome?(num)
s = num.to_s
s == s.reverse
end
ARGF.readline
count = 0
ARGF.each do |input|
count += 1
found = 0
start, finish = input.split(" ").map(&:to_i)
sqrt_start = Math.sqrt(start).to_i
sqrt_finish = Math.sqrt(finish).to_i
(sqrt_start..sqrt_finish).each do |x|
if string_palindrome?(x)
square = x ** 2
if string_palindrome?(square) && (start..finish).cover?(square)
found += 1
end
end
end
puts "Case ##{count}: #{found}"
end
首先，在检查回文的两个方法中我选择了最快的那个，而且我通过只遍历边界的平方根，大大减少了搜索空间。所以，我指望这个算法很有可能表现良好。
这个问题的第一个大输入集包含了10000个测试用例，每个测试用例使用的范围从 1 到 1014 (文件在这). 编码大赛需要你在8分钟内运行输入并上传正确的结果 - 但我的实现却用了53分钟运行。
这个结果让我很吃惊，让我们仔细看看为什么。测试部分输入的性能测试结果如下：
%self total self wait child calls name
49.89 1549.912 984.824 0.000 565.087 326068740 Object#string_palindrome?
21.47 1974.150 423.798 0.000 1550.352 499 Range#each
16.34 322.536 322.536 0.000 0.000 326069738 Fixnum#to_s
12.29 242.552 242.552 0.000 0.000 326068740 String#reverse
0.02 0.409 0.409 0.000 0.000 557447 Fixnum#**
大约50%的执行时间花在string_palindrome?。这个结果不好，但是也还合理。起码我们知道如果使用integer_palindrome??结果会更糟糕。更大的麻烦是Range#each占用了21.47%的执行时间。这意味着全部运行的50分钟里面，10.5分钟花在递增数字。这太不科学了，对吧？经过明智的思考，我决定不使用Range来优化它:
file = File.new(ARGV[0], "r")
file.gets
count = 0
while (input = file.gets)
start, finish = input.split(" ").map(&:to_i)
sqrt_start = Math.sqrt(start).to_i
sqrt_finish = Math.sqrt(finish).to_i
x = sqrt_start
while(x <= sqrt_finish) do
x += 1
end
end
最终结果是…
real 5m42.952s
user 5m42.787s
sys 0m0.153s
哇. 只遍历我们需要的数字就花了5分半种。简单推断一下，几乎所有的时间花在递增和比较数字，这里应该没有GC，但是Fixnum提升为Bignum可能还是花了些时间.
很明显，我必须做大改动了，所以我用Go语言重写了这个代码(more on that experience at a later date).
package main
import (
"fmt"
"math"
)
func palindrome(num int) bool {
var n, reverse, dig int
n = num
reverse = 0
for (num > 0){
dig = num % 10
reverse = reverse * 10 + dig
num = num / 10
}
return n == reverse
}
func main() {
var cases int
fmt.Scan(&cases)
for i := 0; i < cases; i++ {
var found, start, finish, sqrt_start, sqrt_finish, square int
fmt.Scan(&start, &finish)
sqrt_start = int(math.Sqrt(float64(start)))
sqrt_finish = int(math.Sqrt(float64(finish)))
for j := sqrt_start; j <= sqrt_finish; j++ {
if palindrome(j){
square = j*j
if palindrome(square) && square >= start && square <= finish {
found += 1
}
}
}
fmt.Print("Case #", (i + 1), ": ", found, "
")
}
}
我没有为了让这个程序通过测试做更多算法上的修改，这个代码和Ruby的算法一样，只是跑起来更快。
real 0m0.740s
user 0m0.482s
sys 0m0.189s
我知道作为解释性语言，Ruby的性能不高，但是只是简单的遍历整数就花了好几分钟还是让我大吃一惊。将来，我肯定不会在时间敏感的编码竞赛中使用Ruby了。
本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。
2KB翻译工作遵照
CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。
2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务
