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

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

目的

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

什么是回文数

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

示例 1:

1
2
输入: 121
输出: true

示例 2:

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

示例 3:

1
2
3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
  • 所有个位数都属于回文数

解题

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

PHP

一. 翻转字符串

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

翻转字符串

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

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

思路

  1. 统计字符串长度,除2得到中间那个数
  2. 除模2判断单双数
  3. 双数 -> 前部分|取(0,字符长度/2) 后部分|取(字符长度/2,字符长度/2)
  4. 单数 前后多取一位
  5. 对比
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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年绝逼去深挖一波争取可以玩玩源码)

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

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

请我喝杯咖啡吧~