[图片] 首先声明我并不是想证明某一个语言比另外一个好,因为每一个语言都是图灵完备的 撰写该博客的起因是看到朋友转发了一条这样的微博: [图片] 为了保证公平,三种语言的代码逻辑都是一致的,并且都是在同一个电脑上运行的 话不多说,直接上代码 Python 代码(3.6.5) import time # 判断是否为质数 ..

Java,Node,Python 运行速度比较

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

撰写该博客的起因是看到朋友转发了一条这样的微博:
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);
    }
}

运行结果

注意一下,这里的单位是秒不是毫秒(ms),转化成毫秒就是 1926298ms

分析

且不谈优化,我知道我的解法肯定有待优化,至少这里三种代码的逻辑是一致的
从结果数字来看,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 代码的行数最多,至少能说明键盘敲得次数更多

语言特性

结论


算法优化

想了想还是继续优化一下算法吧,之前给出的复杂度计算有误,已经改正

循环边界判断优化

感谢(@kafuly)给出的建议
isPrime()以及getWechatID()函数中的循环边界都改成i <= num / 3,这里三种语言代码稍稍有点区别:

进一步思考

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

$$\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 的整数次幂数时

$$f(10) = 1$$

$$f(100) = 10*1+\frac{10}{2}=15$$

$$10 * 15 + \frac{100}{2} = 200$$

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

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

$$3 * f(100) = 3 * 15 = 45$$

$$ 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 为一般情况时

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()方法看上去就是这样的:

    //获取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;
    }
//得到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
};
# 获取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 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2271 引用 • 7700 回帖 • 922 关注
  • Python

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

    304 引用 • 434 回帖 • 675 关注
  • Node.js

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

    101 引用 • 205 回帖 • 714 关注
4 回帖   
请输入回帖内容...
  • szy0syz  

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

    等我拿 golang 试试 😂

    1 回复
  • nobt  

    秀儿,是你吗?

  • kafuly

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

  • someone45057        

    可能我电脑没你的好😂