首先声明我并不是想证明某一个语言比另外一个好，因为每一个语言都是图灵完备的
撰写该博客的起因是看到朋友转发了一条这样的微博：
为了保证公平，三种语言的代码逻辑都是一致的，并且都是在同一个电脑上运行的
话不多说，直接上代码
Python 代码（3.6.5）
import time # 判断是否为质数 def isPrime(num): for i in range(2, (int)(num / 2)): if num % i == 0: return False return True # 获取3出现的次数 def getThreeNumbers(num): res = 0 for i in range(3, num, 2): n = i while(n > 0): if n % 10 == 3: res = res + 1 n = int(n / 10) print ('3出现的次数：' + str(res)) # 获取微信ID def getWechatID(num): for i in range(2, int(num / 2)): if num % i != 0: continue div = int(num / i) if !isPrime(i) or !isPrime(div): continue res = '' if div > i: res = res + str(div) + str(i) else: res = res + str(i) + str(div) getThreeNumbers(int(res)) print('微信ID：NY' + res) return start = time.time() getWechatID(707829217) end = time.time() print ('Time cost:' + str((end - start)))
Node(JavaScript)代码（10.15.3）
console.time('Time cost') //判断一个数是否为质数 const isPrime = num => { for(let i = 2; i < Math.floor(num / 2); i++){ if(num % i == 0) return false } return true }; //得到3出现的次数 const getThreeNumbers = num => { let res = 0 for(let i = 3; i <= num; i+=2){ let n = i while(n > 0){ if(n % 10 == 3) res++ n = Math.floor(n / 10) } } return res }; //得到微信ID const getWechatID = num => { for(let i = 2; i < Math.floor(num / 2); i++){ if(num % i != 0) continue let div = num / i if(isPrime(i) && isPrime(div)){ let res = div > i ? `${div}${i}` : `${i}${div}` console.log(`3的次数：${getThreeNumbers(res)}`); return res } } } console.log(`微信ID：NY${getWechatID(707829217)}`); console.timeEnd('Time cost')
Java 代码（1.8.0_201）
public class Test { public static void main(String[] args) { long startTime=System.currentTimeMillis(); getWechatID(707829217); long endTime=System.currentTimeMillis(); System.out.println("Time cost： " + (endTime - startTime) + "ms"); } //判断是否是质数 public static boolean isPrime(int num){ for(int i = 2; i < num / 2; i++){ if(num % 2 == 0) return false; } return true; } //获取微信ID public static void getWechatID(int num){ for(int i = 2; i < num / 2; i++){ if(num % i != 0) continue; int div = num / i; if(!isPrime(div) || !isPrime(i)) continue; String res = ""; if(div > i){ res = res + div + i; }else{ res = res + i + div; } getThreeNumbers(Integer.parseInt(res)); System.out.println("微信ID：NY" + res); return; } } //获取3出现的次数 public static void getThreeNumbers(int num){ int res = 0; for(int i = 3; i <= num; i += 2){ int n = i; while(n > 0){ if(n % 10 == 3){ res ++; } n = n / 10; } } System.out.println("3出现的次数：" + res); } }
运行结果
- Python
注意一下，这里的单位是秒不是毫秒（ms），转化成毫秒就是 1926298ms
-
Node
-
Java
分析
且不谈优化，我知道我的解法肯定有待优化，至少这里三种代码的逻辑是一致的
从结果数字来看，python 的确是慢了很多，Java 的确是快很多
Java：15277ms
Node：70327ms
Python：1926298ms
下面分析原因：
算法复杂度
由于用到了双层循环，所以算法的时间复杂度是
其实准确的说，这里的时间复杂度是
只保留最高次项，同时忽略最高项的系数得到
代码编写时间
在这里具体的编写代码时间不好测量，因为我对每个语言的熟练程度不一样
但是 java 代码的行数最多，至少能说明键盘敲得次数更多
语言特性
- 强弱类型（动静态类型）
Java 是强类型语言（静态类型）
而 Python，Node（JavaScript）是弱类型语言（动态类型）
这意味着 Python 跟 Node 需要在运行时作类型检查以及转换，所以速度自然会受影响 - 语言类型
Java 是编译型语言
Node（JavaScript）是混合型语言（为啥是混合型，我也是 Google 了一下，感兴趣的自己 Google）
Python 是解释型语言
Python 需要对代码进行读取，词法分析，解析，编译，解释和运行
Node 第一次也需要如上步骤，但是执行相同的逻辑时，将会跳过读取，词法分析，解析，编译，解释，直接运行
Java 则是先编译，然后直接运行
结论
- 语言本身并无优劣之分
- 当需要重复计算时，Python 的速度的确慢很多，Java 的确有优势
- 选择哪一种语言取决于你想用它做什么以及你的成本是多少，包括硬件成本，时间成本，只有根据你的具体需求才能选择对的语言去开发，不能空谈效率
算法优化
想了想还是继续优化一下算法吧，之前给出的复杂度计算有误，已经改正
循环边界判断优化
感谢（@kafuly）给出的建议
将 isPrime() 以及 getWechatID() 函数中的循环边界都改成 i <= num / 3，这里三种语言代码稍稍有点区别：
- Java 直接修改即可
i <= num / 3 - Node 需要调用 Math.floor()
i <= Math.floor(num / 3) - Python 需要调用 int()函数
i <= int(num / 3)
优化完毕后，复杂度是：
进一步思考
这里我们先计算一下复杂度里第一项与第二项的大小：
- 第一项:
这里 n 的最大值是 8171
所以计算次数是
- 第二项：
这里的 n 最大值是 866278171，所以计算次数为：
这里可以看到第二项的计算次数占了很大的比重
继续优化，下面分情形探讨一下 n 以内的奇数序列中 3 出现的个数
n 为 10 的整数次幂数时
- n=10
- n = 100
3, 13, 23, 33, 43, 53, 63, 73, 83, 93 总共 10 次
30, 31, 32, 33, 34, 35, 36, 37, 38, 39 出现 10 次
只保留奇数序列，且 33 重复计算一次，所以结果为：
- n = 1000
- 可以推出：
f(n) = f(10n-1)*10 + 10n-1/2
n = 10 的整数次幂的整数倍数时
- n = 300
- n = 700
- 推出：
当系数 <=3 时
f(a*10b) = a*f(10b)
当系数 >3 时
f(a*10b) = a*f(10b) + 10n-1/2
n 为一般情况时
- n = 1764
f(1764) = f(1000) + 7*f(100) + 10*f(10)/2 + 6*f(10) + 10/2 + f(4)
f(1000) = 10*f(100) + 100/2
f(100) = 10*f(10) + 10 / 2
f(10) = 1
f(4) = 1
=> f(100) = 15
=>f(1000) = 200
=>f(1764) = 200 + 7*15 + 100/2 + 6*1 + 5 + 1 = 367
优化之后的代码
优化之后，我们的 getThreeNumbers() 方法看上去就是这样的:
- Java
//获取3出现的次数 public static int getThreeNumbers(int num){ if(num < 3){ return 0; } if(num >= 3 && num <= 10){ return 1; } //得到num比10的多少次方大（或相等） int pow = (int)Math.log10(num); int afterPow = (int)Math.pow(10, pow); //得到系数 int times = num / afterPow; //得到剩余部分 int remindPart = num % (times * afterPow); if(times > 3){ return times*f(pow) + afterPow/2 + getThreeNumbers(remindPart); } return times*f(pow) + getThreeNumbers(remindPart); } //获得10的整数次幂的结果 public static int f(int pow){ if(pow == 1){ return 1; } return 10*f(pow-1) + (int)Math.pow(10, pow - 1)/2; }
- Node 代码
//得到3出现的次数 const getThreeNumbers = num => { if(num < 3){ return 0; } if(num >= 3 && num <= 10){ return 1; } let pow = Math.floor(Math.log10(num)) let afterPow = Math.pow(10, pow) let times = Math.floor(num / afterPow) let remindPart = num % (times * afterPow) if(times > 3){ return times*f(pow) + afterPow/2 + getThreeNumbers(remindPart) } return times*f(pow) + getThreeNumbers(remindPart) }; //获得10的整数次幂的结果 const f = pow => { if(pow == 1){ return 1 } return 10 * f(pow - 1) + Math.pow(10, pow-1)/2 };
- Python
# 获取3出现的次数 def getThreeNumbers(num): if num < 3: return 0 if num >=3 and num <= 10: return 1 pow = int(math.log10(num)) afterPow = int(math.pow(10, pow)) times = int(num / afterPow) remindPart = num % afterPow if times > 3: return times*f(pow) + afterPow/2 + getThreeNumbers(remindPart) return times*f(pow) + getThreeNumbers(remindPart) # 获得10的整数次幂的结果 def f(pow): if pow == 1: return 1 return 10*f(pow - 1) + math.pow(10, pow-1)/2
优化结果
Java
1ms
Node
11.6ms
Python
11.9ms
再次分析
可以看到，Java 的速度优势已经体现不出来多少了，10ms 的差距是感受不到的
反而这个时候 java 的编译速度 + 代码撰写速度比较长了
再看复杂度
现在的总复杂度其实还是：
- 第一项的计算次数还是
- 第二项的计算次数
因为用了递归，其实这里还可以优化，可以将递归改成非递归，这里就不继续写了
将 n = 866278171 代入得：
到这里，解题 + 优化的过程全部结束
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于