回文数判定算法的深入研究(JavaScript)

学校里做到了回文数的判定算法（当时用的是VB，能过就行了，但是我怎么会就这么满足呢

:twisted:

）。决定使用现在最凉的JavaScript重写该算法，把自己的一些想法在这里做一个总结。 注：运行环境使用NodeJS v11.9.0

https://cdn.daidr.me/wp-content/uploads/2019/07/%E5%B0%81%E9%9D%A2%E5%9B%BE-1024x697.png?x-oss-process=image/format,webp

一、不成熟的想法

判断回文数嘛…戴兜的第一想法是将提供的数转换为字符串，把字符串倒置，然后和原来的比较一下不就好了，多简单的事。

JS中数组提供了reverse方法以返回一个倒序的数组，那么不难想到，字符串的倒置应该依靠数组实现。首先使用split方法将字符串分割为数组，倒置，再使用join将其拼合为字符串。那么，反转”abcd”的代码大概是这样的：

let raw = "abcd";
let rawArray = raw.split("");
let processedArray = rawArray.reverse();
processedArray.join(""); // => "dcba"

用链式写法让代码看起来优美一些：

"abcd".split("").reverse().join(""); // => "dcba"

那么，现在有一个参数x储存了需要判断的回文数，如何将这个x转换为字符串呢？

首先最简单的一种，x.toString()，效率怎么样呢？在我的设备上执行1000万次耗时618±5ms。有没有效率更高的方法呢？答案是有，通过让数值与字符串做加法运算来使其转换为字符，大概这样：""+x，执行1000万次耗时97±4ms。（这里不是本文重点，本没有必要吹毛求疵，但请允许我凑一点字数

:cry:

）

这已经很快了，还有没有更快的呢？这里要介绍的是JS在ES6标准中引入的一个新的字面量——模板字面量(Template literals)，倘若使用使用模板字符串，我们可以让耗时缩短至80±3ms，可以这么写： `${x}`

最后， 再结合与原字符串的比较（完整代码判定100万次耗时1250±100ms，效率超低有没有），你所得到的完整代码应该是：

function isPalindrome(x) {
return `${x}` === `${x}`.split("").reverse().join("");
}

二[1]、继续深入

使用第一种方法效率不是很高，一是因为数据类型的转换消耗性能，二是因为JS的数组效率本身就不是很高。我们尝试直接对数进行判断。下面是我的第一次尝试：

function isPalindrome(x) {
    let mod = 0, result = 0, tmp=x;
    while (Math.floor(tmp / 10) != 0) {
        mod = tmp % 10;
        tmp = Math.floor(tmp / 10);
        result = result * 10 + mod;
    }
    result = result * 10 + tmp;
    return result == x;
}

每次循环将 result 的值乘以10后加上 tmp 的余数（最后1位），并将 tmp 整除10（去掉最后1位），即可完成数值的倒置，对数值 123454321 进行100万次判定耗时169±5ms，其实作为第一次的尝试结果我还是很满意的，若吹毛求疵一点，可以使用按位非操作符（~）替换取整操作，原理可以参考MDN，将 Math.floor(tmp / 10) 修改为 ~~(tmp / 10) 替换后同样运行100万次只需耗时60±3ms。

二[2]、特殊情况

第一种情况，负数。负数倒置后一定与原数不等，所以我们可以直接对负数返回false。

第二种情况，0。0作为一个一直很特殊的存在，怎么能忘了它？当一个数末位数为0时，倒置后仍与原数相等的，只有0。那么，我们能对这些情况进行特殊的判断。补充后的代码如下：

function isPalindrome(x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) {
        return false; //若x为负数或x能被10整除且不为0，直接返回false
    }
    let mod = 0, result = 0, tmp=x;
    while (Math.floor(tmp / 10) != 0) {
        mod = tmp % 10;
        tmp = Math.floor(tmp / 10);
        result = result * 10 + mod;
    }
    result = result * 10 + tmp;
    return result == x;
}

这样修改后，对于一些特殊情况，可以迅速完成判断。

三[1]、还能优化？

倒置全部效率真的好低唉

:cry:

。仔细想想，有必要倒置所有数字么？只需要让首位与末尾比较，第二位与倒数第二位比较……我们要做的，就是从首位开始取一半的数字，从末尾开始取一半的数字。（也就是只倒置一半的数字）

可能会有人问，万一数字有奇数个呢？影响其实不是很大，因为若为偶数个，能直接取完；奇数个的话，中间的数字永远和自己相等，可以直接忽略。

三[2]、如何实现？

说出来你可能不信，我们只需将循环条件修改为 tmp > result 。这是因为当 tmp 小于 result 的时候，我们已经完成了一半数字的转换。为了提高效率，我们甚至可以去掉 tmp 和 mod 辅助变量，直接操作 x ，修改完成的代码大概是下面这个样子：

function isPalindrome(x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) {
        return false; //若x为负数或x能被10整除且不为0，直接返回false
    }
    let result = 0;
    while(x > result) {
        result = result * 10 + x % 10;
        x = ~~(x/10);
    }
    return x == result || x == ~~(result/10);
}

最后一句添加判断条件 x == ~~(result/10) 能让 x 与 result 不相等时考虑「三[1]、还能优化？」中提到的最后一种情况，忽略中间一位再次比较。最后我们100万次判定只需耗时42ms左右。

code{background: #f5f2f0;}