《Ruby太慢了》PHP实现,两种算法

http://www.oschina.com 之前 有一篇文章 http://www.oschina.net/translate/ruby-is-too-slow-for-programming-competitions
一下子掀起了各语言实现这个算法的狂潮

转帖呢,首先看看题目要求:给定数字X和Y,返回其中包括多少个数字,数字本身是回文数,同时也是另一个回文数的平方。

这里有一个PHP 实现,是仿照的 JAVA 算法:http://www.oschina.net/code/snippet_1023425_20741
实际上这样没有完全利用PHP本身的特点,运算速度颇慢,我本地大概27s
我以这个算法为基础,优化如下:

<?php
set_time_limit(0);
$t1 = microtime(true);
$min = 1;
$max = 100000000000000;
$i = (int) sqrt($min);
$end = (int) sqrt($max) + 1;
for (; $i < $end; $i++) {
if (($i % 10) > 0 && $i == strrev($i)) {
$n = $i * $i;
if ($n == strrev($n)) {
echo "$n ($i)<br>";
}
}
}
echo 'Time:', (microtime(true) - $t1), 's';

1、使用 strrev 可以让对回文的判断快非常多,本地测试减少了10s
2、去掉了独立的 isPlalindrome 函数。第一,调用纯PHP写的函数花费时间很多,这个修改可以节省了大约4s;第二,上一步修改后的 $i == strrev($i) 已经足够简洁
3、$min 和 $max,sqrt 后手动转成 int,否则 for 时PHP会有自动类型转换,浪费 2s 左右
4、增加了 ($i % 10) > 0,还是能快几百毫秒吧,聊胜于无
5、拆成了两个,经过测试,拆开要比写成一个 if 快一点
6、去掉了 showPlalindrome,简单到底,没必要封装,反正肯定会快那么无法察觉的一点
7、$end + 1,如果 $max 是 4000008000004 这样的符合条件的回文数,不这么写会漏掉

经过以上修改,执行大概需要 8.1s

然后,正戏来了,参考:http://www.oschina.net/code/snippet_169326_20803,中的算法:

<?php
set_time_limit(0);
$t1 = microtime(true);
$min = 1;
$max = 0xffffffffffffffff;
$palindromes = array();
$s = (string) sqrt($min);
$l = strlen($s);
$i = (int) substr($s, 0, $l / 2 + $l % 2); 
while (true)
{
$s1 = (string) $i;
$s2 = strrev($s1);
$p = (int) ($s1 . substr($s2, 1));
$pp = $p * $p;
if ($pp > $max)
{
break;
}
if ($pp >= $min and $pp == strrev($pp))
{
$palindromes[$p] = $pp;
}
$p = (int) ($s1 . $s2);
$pp = $p * $p;
if ($pp >= $min and $pp <= $max and $pp == strrev($pp))
{
$palindromes[$p] = $pp;
}
++$i;
}
ksort($palindromes);
foreach($palindromes as $p => $pp)
{
echo $pp, ' (', $p, ')<br />';
}
echo 'Time:', (microtime(true) - $t1), 's';

1 ~ 0xffffffffffffffff 只需要 0.4s
上一个算法中,那个 1 ~ 100000000000000 只需要 0.04s

这就是算法的力量….

发表评论

电子邮件地址不会被公开。 必填项已用*标注