登录 注册

Java，Node，Python 运行速度比较

本贴最后更新于 2019 天前，其中的信息可能已经时移俗易

首先声明我并不是想证明某一个语言比另外一个好，因为每一个语言都是图灵完备的

撰写该博客的起因是看到朋友转发了一条这样的微博：
reason.png
为了保证公平，三种语言的代码逻辑都是一致的，并且都是在同一个电脑上运行的
话不多说，直接上代码

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
    image.png

注意一下，这里的单位是秒不是毫秒（ms），转化成毫秒就是 1926298ms

  • Node
    image.png

  • Java
    image.png

分析

且不谈优化，我知道我的解法肯定有待优化，至少这里三种代码的逻辑是一致的
从结果数字来看，python 的确是慢了很多，Java 的确是快很多
Java：15277ms
Node：70327ms
Python：1926298ms
下面分析原因：

算法复杂度

由于用到了双层循环，所以算法的时间复杂度是

O(n^2)$$ 其实准确的说，这里的时间复杂度是 $$O(\frac{1}{2} * \frac{1}{2} * n^2 + \frac{1}{2} * n * log_{10}n)$$ 只保留最高次项，同时忽略最高项的系数得到 $$O(n^2)

代码编写时间

在这里具体的编写代码时间不好测量，因为我对每个语言的熟练程度不一样
但是 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)
    优化完毕后，复杂度是：
O(\frac{1}{3} * \frac{1}{3} * n^2 + n*log_{10}n)

进一步思考

这里我们先计算一下复杂度里第一项与第二项的大小：

  • 第一项:
\frac{1}{3} * \frac{1}{3} * n^2

这里 n 的最大值是 8171
所以计算次数是

8171 * 8171 * 1/9 \approx 7418360
  • 第二项：
n * log_{10}n

这里的 n 最大值是 866278171，所以计算次数为：

866278171 * log_{10}866278171 \approx 7742497480

这里可以看到第二项的计算次数占了很大的比重

继续优化，下面分情形探讨一下 n 以内的奇数序列中 3 出现的个数

n 为 10 的整数次幂数时

  • n=10
f(10) = 1
  • 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 重复计算一次，所以结果为：
f(100) = 10*1+\frac{10}{2}=15
  • n = 1000
10 * 15 + \frac{100}{2} = 200
  • 可以推出：

f(n) = f(10n-1)*10 + 10n-1/2

n = 10 的整数次幂的整数倍数时

  • n = 300
3 * f(100) = 3 * 15 = 45
  • n = 700
7 * f(100) + 100 / 2 = 7 * 15 + 50 = 155
  • 推出：

当系数 <=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

image.png
1ms

Node

image.png
11.6ms

Python

image.png
11.9ms

再次分析

可以看到，Java 的速度优势已经体现不出来多少了，10ms 的差距是感受不到的
反而这个时候 java 的编译速度 + 代码撰写速度比较长了

再看复杂度

现在的总复杂度其实还是：

O(n^2)
  • 第一项的计算次数还是
8171 * 8171 * 1/9 \approx 7418360
  • 第二项的计算次数
    因为用了递归，其实这里还可以优化，可以将递归改成非递归，这里就不继续写了
f(n)=log_{10}n + log_{10}(n-1) + ... + log_{10}1

将 n = 866278171 代入得：

f(n)\approx36

到这里，解题 + 优化的过程全部结束

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • Python

    Python 是一种面向对象、直译式电脑编程语言，具有近二十年的发展历史，成熟且稳定。它包含了一组完善而且容易理解的标准库，能够轻松完成很多常见的任务。它的语法简捷和清晰，尽量使用无异义的英语单词，与其它大多数程序设计语言使用大括号不一样，它使用缩进来定义语句块。

    543 引用 • 672 回帖
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台， 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动， 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 43 关注
2 关注
1 收藏
4 回帖
5.5k 82 1.0k 457 923 149 16 157 2.7k

相关帖子

4 回帖
Java，Node，Python 运行速度比较

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
  • szy0syz •

    image.png
    我跑你的 node 代码执行时间

    等我拿 golang 试试 😂

    1 回复
  • nobt •

    秀儿，是你吗？

  • visus •

    其实可以优化一下，因为最小质数为 2，但是又不是 2 从而导致，num/3，所以判断范围是 i<=num/3

  • someone45057 •
    作者

    可能我电脑没你的好 😂

someone45057
回帖
23
 帖子
9
 积分
1765