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

这就是算法的力量….

这个算法思路是，如果数据集非常的大，从一个大数据集中一个一个测试数据，不如直接构造出要求的数据，再验证数据是否符合范围

 

——————-  2018年1月30日 —————

PHP 7.2.1 本地测试：

第一个算法 1.57s
第二个算法 0.08s

PHP7 运算性能真的是提高了很多