Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

Python/PHP/Perl 开发与设计
头像
xw_y_am
帖子: 3332
注册时间: 2009-05-08 14:18
系统: Arch
来自: 河南新乡
送出感谢: 10 次
接收感谢: 6 次
联系:

Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#1

帖子 xw_y_am » 2012-04-17 16:55

Python 代码

代码: 全选

# coding=utf-8
''' The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million. '''

import math
import time

'''分解因数,如果是素数返回'''
def factor(x, min = 2):
  temp = min
  while temp <= int(math.sqrt(x)) + 1: #从最小值到上界开始尝试
    if x % temp == 0: return temp # 如果 a 能分解则返回最小因子
    else: temp += 1
  return 1 # 如果 a 是素数就返回 1,此处也可以设置为返回 x 本身

total = 0 # 总和
a = time.time() # 时间测试
for i in range(3, 200000): # 从 3 到 2000000 循环检测是否为素数
  if factor(i) == 1: total += i # 若是则加入总和
b = time.time()
total += 2 # 补上 2
print total # 输出
print b - a # 输出时间
C++ 代码

代码: 全选

/** The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million. */

#include "0.hpp"
#include <sys/timeb.h>

uu factor(uu a, uu min = 1)
{
  uu temp = min;
  uu sqr = (int)(sqrt((double)a) + _eps);
  while(temp < sqr) if(a % ++temp == 0) break;
  if(a % temp == 0) return temp;
  else return 1;
}

int main()
{
  const uu _max = 200000;
  
  uu sum = 0;
  timeb start, end;
  ftime(&start);
  for(uu i = 3; i <= _max; i += 2) {
    if(factor(i) == 1) {
      //cout << i << "\t";
      sum += i;
    }
  }
  sum += 2;
  ftime(&end);
  cout << sum << endl;
  cout << (end.time - start.time) * 1000 + end.millitm - start.millitm << endl;
  return 0;
}
python 的那个程序特别慢
谁能解释一下原因啊
小生这里拜谢了 :em70 :em70
Linux 相关链接大杂烩

代码: 全选

if(read) {
    if(practise) return g☘☘d;
    else return w☘☘d;
} else {
    return t☘☘d;
}
头像
lilydjwg
论坛版主
帖子: 4163
注册时间: 2009-04-11 23:46
系统: Arch Linux
送出感谢: 11 次
接收感谢: 127 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#2

帖子 lilydjwg » 2012-04-17 17:04

数据呢?Py2 还是 3?

PS: 本版块有个非常高效的质数算法的 Haskell 版。
PPS: Python 版检查的数的数量是 C++ 版的两倍啊。
PPPS: 哦,是 Py2,那么请用 xrange。
这些用户感谢了作者 lilydjwg 于这个帖子:
xw_y_am (2012-04-17 20:02)
评价: 3.7%
头像
xw_y_am
帖子: 3332
注册时间: 2009-05-08 14:18
系统: Arch
来自: 河南新乡
送出感谢: 10 次
接收感谢: 6 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#3

帖子 xw_y_am » 2012-04-17 17:24

lilydjwg 写了:数据呢?Py2 还是 3?

PS: 本版块有个非常高效的质数算法的 Haskell 版。
PPS: Python 版检查的数的数量是 C++ 版的两倍啊。
PPPS: 哦,是 Py2,那么请用 xrange。

代码: 全选

import time
a = time.time()
i = 0
for i in xrange(123456789): pass
b = time.time()
print b - a

代码: 全选

#include <iostream>
#include <sys/timeb.h>
using namespace std;

typedef unsigned long long int uu;

int main()
{
  timeb start, end;
  ftime(&start);
  for(uu i = 0; i < 123456789; i++);
  ftime(&end);
  cout << end.time + float(end.millitm) / 1000 - start.millitm / 1000 - start.time << endl;
  return 0;
} 
这两个程序的差异也很大啊。。。
什么具体内容都木有,就是遍历 0 到 123456789 而已
c++ 耗时 0.5 s 左右
python 每次都是 6 s + 啊。。。

有木有什么好的办法呢。。。。
Linux 相关链接大杂烩

代码: 全选

if(read) {
    if(practise) return g☘☘d;
    else return w☘☘d;
} else {
    return t☘☘d;
}
头像
枫叶饭团
论坛版主
帖子: 14684
注册时间: 2010-06-16 1:05
系统: Mac OS X
来自: Tencent
送出感谢: 1 次
接收感谢: 132 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#4

帖子 枫叶饭团 » 2012-04-17 17:30

人家py速度本来就不是非常快嘛,用c写拓展haha~
头像
b33e
论坛版主
帖子: 3862
注册时间: 2011-06-07 14:20
系统: Mint18
送出感谢: 16 次
接收感谢: 62 次

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#5

帖子 b33e » 2012-04-17 17:39

我好奇x**0.5和math.sqrt(x)哪个快一点?不太清楚哦。
头像
枫叶饭团
论坛版主
帖子: 14684
注册时间: 2010-06-16 1:05
系统: Mac OS X
来自: Tencent
送出感谢: 1 次
接收感谢: 132 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#6

帖子 枫叶饭团 » 2012-04-17 17:49

我用手机运行那个123456789,运行了1分多钟没出结果,手机发热我把它关了。py for android效率无敌啊
头像
lilydjwg
论坛版主
帖子: 4163
注册时间: 2009-04-11 23:46
系统: Arch Linux
送出感谢: 11 次
接收感谢: 127 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#7

帖子 lilydjwg » 2012-04-17 18:00

xw_y_am 写了:
这两个程序的差异也很大啊。。。
什么具体内容都木有,就是遍历 0 到 123456789 而已
c++ 耗时 0.5 s 左右
python 每次都是 6 s + 啊。。。

有木有什么好的办法呢。。。。
这还好啦。如果 Python 的计算效率不够,那么用 C 扩展吧。
PS: 你那个 C++ 版本的如果开优化的话应该立马出结果吧?
头像
xw_y_am
帖子: 3332
注册时间: 2009-05-08 14:18
系统: Arch
来自: 河南新乡
送出感谢: 10 次
接收感谢: 6 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#8

帖子 xw_y_am » 2012-04-17 18:04

lilydjwg 写了:
xw_y_am 写了:
这两个程序的差异也很大啊。。。
什么具体内容都木有,就是遍历 0 到 123456789 而已
c++ 耗时 0.5 s 左右
python 每次都是 6 s + 啊。。。

有木有什么好的办法呢。。。。
这还好啦。如果 Python 的计算效率不够,那么用 C 扩展吧。
PS: 你那个 C++ 版本的如果开优化的话应该立马出结果吧?
:em06 :em06 不知道肿么开优化
Linux 相关链接大杂烩

代码: 全选

if(read) {
    if(practise) return g☘☘d;
    else return w☘☘d;
} else {
    return t☘☘d;
}
头像
b33e
论坛版主
帖子: 3862
注册时间: 2011-06-07 14:20
系统: Mint18
送出感谢: 16 次
接收感谢: 62 次

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#9

帖子 b33e » 2012-04-17 19:18

看看这个python算法吧,我是直接网上找的,加了一行,很快。你的python源代码写的是200000,这个2000000都比你的快的多。

代码: 全选

def primes(n):
  if n < 2:  return []
  if n == 2: return [2]
  s = range(3, n, 2)
  mroot = n ** 0.5
  half = len(s)
  i = 0
  m = 3
  while m <= mroot:
    if s[i]:
      j = (m * m - 3)//2
      s[j] = 0
      while j < half:
        s[j] = 0
        j += m
    i = i + 1
    m = 2 * i + 3
  return [2]+[x for x in s if x]
print sum(primes(2000000))
这些用户感谢了作者 b33e 于这个帖子:
xw_y_am (2012-04-17 20:01)
评价: 3.7%
头像
tangboyun
帖子: 701
注册时间: 2009-07-25 1:57
送出感谢: 5 次
接收感谢: 13 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#10

帖子 tangboyun » 2012-04-17 19:41

换pypy试试看。速度应该会提升很多。至于为啥和c++版本有如此大差距,取决于解释器的底层实现的,这部分除非有人非常了解、读过源码,否则很难回答你的。
至于脚本,其实每种动态语言都不适合数值计算(优化的再好,也只能和未向量化的c比比),那些可以做的,比如R和matlab,其实都是调用了c或者fortran库。

你这个要速度快的话,就用numpy的sweave去内联c,很适合你这个例子(你这个例子无法向量化的,所以内联c肯定可以接近原始c的速度)。
这些用户感谢了作者 tangboyun 于这个帖子:
xw_y_am (2012-04-17 20:02)
评价: 3.7%
https://github.com/tangboyun
http://tangboyun.is-programmer.com/
提问的智慧————Eric Steven Raymond
回答的智慧————Andrew Clarke
吾尝终日而思矣,不如须臾之所学也;吾尝跂而望矣,不如登高之博见也。
急急急标题什么的,最讨厌了!
急急复急急,急急何其多,我生待急急,万事急急急。
头像
枫叶饭团
论坛版主
帖子: 14684
注册时间: 2010-06-16 1:05
系统: Mac OS X
来自: Tencent
送出感谢: 1 次
接收感谢: 132 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#11

帖子 枫叶饭团 » 2012-04-17 20:10

b33e 写了:我好奇x**0.5和math.sqrt(x)哪个快一点?不太清楚哦。
q我用手机试了下,**比sqrt快近5倍-_-#
头像
xw_y_am
帖子: 3332
注册时间: 2009-05-08 14:18
系统: Arch
来自: 河南新乡
送出感谢: 10 次
接收感谢: 6 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#12

帖子 xw_y_am » 2012-04-17 20:13

b33e 写了:看看这个python算法吧,我是直接网上找的,加了一行,很快。你的python源代码写的是200000,这个2000000都比你的快的多。

代码: 全选

def primes(n):
  if n < 2:  return []
  if n == 2: return [2]
  s = range(3, n, 2)
  mroot = n ** 0.5
  half = len(s)
  i = 0
  m = 3
  while m <= mroot:
    if s[i]:
      j = (m * m - 3)//2
      s[j] = 0
      while j < half:
        s[j] = 0
        j += m
    i = i + 1
    m = 2 * i + 3
  return [2]+[x for x in s if x]
print sum(primes(2000000))
这个是优化过了
但是我用 C++ 的话,即便是那个慢算法也很快
我又测试了几个程序
发现 Python 大数遍历的机制木有 C++ 好
Linux 相关链接大杂烩

代码: 全选

if(read) {
    if(practise) return g☘☘d;
    else return w☘☘d;
} else {
    return t☘☘d;
}
头像
xw_y_am
帖子: 3332
注册时间: 2009-05-08 14:18
系统: Arch
来自: 河南新乡
送出感谢: 10 次
接收感谢: 6 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#13

帖子 xw_y_am » 2012-04-17 20:18

枫叶饭团 写了:
b33e 写了:我好奇x**0.5和math.sqrt(x)哪个快一点?不太清楚哦。
q我用手机试了下,**比sqrt快近5倍-_-#
你怎么测试的,为毛我的结果正好跟你相反 :em20 :em20

代码: 全选

import math
import time

_max = 12345678

a = time.time()
for i in xrange(_max):
  i ** 0.5
b = time.time()
print b - a

for i in xrange(_max):
  math.sqrt(i)
a = time.time()
print a - b

代码: 全选

3.97089219093              **
2.98011684418               math
Linux 相关链接大杂烩

代码: 全选

if(read) {
    if(practise) return g☘☘d;
    else return w☘☘d;
} else {
    return t☘☘d;
}
头像
枫叶饭团
论坛版主
帖子: 14684
注册时间: 2010-06-16 1:05
系统: Mac OS X
来自: Tencent
送出感谢: 1 次
接收感谢: 132 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#14

帖子 枫叶饭团 » 2012-04-17 20:33

py for android坑爹呢
头像
月下叹逍遥
论坛版主
帖子: 33994
注册时间: 2010-10-07 14:23
系统: Archdows10
来自: 某系某星某洲某国某省某市
送出感谢: 8 次
接收感谢: 63 次
联系:

Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大

#15

帖子 月下叹逍遥 » 2012-04-17 20:35

搞计算,fortran吧,比c都快。。。
心似浮云常自在,意如流水任东西。
此事背后一定有个天大的咪咪
广告:
1、走过路过,不要错过,dropbox网盘2.25G大放送
py大法好,退C保平安
java多妖孽,VB本异端
日诵一千遍,快活似神仙
回复

回到 “Python/Php/Perl”