回文数算法的实现 && PHP GO C 的性能对比

一直以来我都有一个疑问，大家说的编译型语言比脚本型语言效率高运行快是否属实。在书本知识上来理解，一种更接近底层，一种需要解释器进行转换感觉来说的确如此，周末闲不下来所以特地试试

目的

1. 了解回文数，并写出回文数的几种解法
2. 对比（PHP / GO / C）对单个回文数算法的执行数据

什么是回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

• 所有个位数都属于回文数

解题

因为主要从事PHP开发这边也想了3中用PHP进行解题的思路

PHP

一. 翻转字符串

function isPalindrome ($x) {
   return strrev($x) == $x ? true :  false;
}

平均执行时间 30.4ms，平均内存消耗 14.88MB

二. 转换为字符串，截断字符串 对比前后

思路

1. 统计字符串长度，除2得到中间那个数
2. 除模2判断单双数
3. 双数 -> 前部分|取(0,字符长度/2) 后部分|取（字符长度/2，字符长度/2）
4. 单数 前后多取一位
5. 对比

function isPalindrome($x) {
        $len = strlen($x);
        $centre = floor($len / 2);
        if (($len % 2) == 0) {
            $before =  substr($x, 0, $centre);
            $after = substr($x, $centre, $centre);
            if ($before == strrev($after)) {
                return true;
            } else {
                return false;
            }
        } else {
            $position = $centre + 1;
            $before = substr($x, 0, $position - 1);
            $after = substr($x, $position, $len - 1);

            if ($before == strrev($after)) {
                return true;
            } else {
                return false;
            }
        }
    }

平均执行时间 32.8ms，平均内存消耗 14.86MB

取模对比法

1. 负数都是非回文数
2. 取10模因此需要过滤掉他本身
3. 个位数都是回文数需要过滤掉0
4. x取模10得到个位数
5. rev乘10加上尾数实现’反转’效果
6. x除10 rev乘10判断中位数
7. rev 除10去除单数时的中数

注： PHP 是弱类型语言会隐式转换为浮点数，在乘除取中位数时会有干扰，说以需要强制取整

PHP

function isPalindrome ($x) {

    if ($x < 0 || ($x % 10 == 0 && $x != 0)) {
        return false;
    }

    $rev = 0;
    while (floor($x) > $rev) {
        $rev = ($rev * 10) + ($x % 10);
        $x = floor($x) / 10;
    }


    return ( (floor($rev / 10) == floor($x)) || ($rev == floor($x))) ? true : false;

}

平均执行时间 42.4ms，平均内存消耗 14.86MB

GO

func isPalindrome(x int) bool {
	
	if (x < 0) || ((x%10) == 0 && x != 0) {
		return false
	}

	var rev int
	rev = 0

	for x > rev  {
		rev = (rev*10) + (x%10)
		x = x/10
	}

	 if (rev/10 == x) || (rev == x) {
	 	return  true
	 } else {
	 	return false
	 }
}

平均执行时间 16ms，平均内存消耗 5.2MB

C

bool isPalindrome(int x){

    if( x<0 || (x%10 == 0 && x !=0)){
        return false;
    }

    int rev = 0;

    while (x > rev) {
        rev = rev*10 + x%10;
        x = x/10;
    }

    if ( (rev/10) == x || rev == x){
        return true;
    } else {
        return false;
    }
}

平均执行时间 14.4ms，平均内存消耗 7.12MB

性能比较

PHP

名称	平均耗时	平均内存消耗
翻转字符串	30.4ms	14.88MB
截断字符串,对比前后	32.8ms	14.86MB`
取模对比法	42.4ms	14.86MB

语言对比

语言	平均耗时	平均内存消耗
PHP	30.4ms	14.88MB
GO	16ms	5.2MB
C	14.4ms	7.12MB

总结

至此给我带来最大收获的可能会有如下几点

1. GO的性能消耗无限接近C
2. 脚本型语言性能弱于编译型
3. PHP内部封装函数优于我们自己用PHP语言实现的各种花里胡哨的算法（1.开发小组或多或少会选择执行性能最好的解法。 2.底层C直接执行函数，效率远远高过脚本解释成二进制再去执行。)

这里浅浅的翻了下PHP strrev 函数的C实现是通过指针向前解引实现的（C的功力有限描述不出来了，2020年绝逼去深挖一波争取可以玩玩源码）

另外作为程序员我们该做到的不是去比较语言的性能，而是在适应的场景用适应的技术顺势而为。过分的执着语言本身的性能不能通盘考虑往往是单一语言的布道者，但不是一名合格的程序员和技术管理者。