当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 34 篇帖子 ]  前往页数 1, 2, 3  下一页
作者 内容
1 楼 
 文章标题 : Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 16:55 
头像

注册: 2009-05-08 14:18
帖子: 3332
地址: 河南新乡
系统: Arch
送出感谢: 19
接收感谢: 10
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;
}


页首
 用户资料  
 
2 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 17:04 
头像

注册: 2009-04-11 23:46
帖子: 4141
系统: Arch Linux
送出感谢: 11
接收感谢: 125
数据呢?Py2 还是 3?

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


_________________
我的博客 https://blog.lilydjwg.me/
提问的智慧
Arch Linux 中文论坛

我的vimrc: https://git.io/vimrc



_________________
评价: 3.7% xw_y_am
 
页首
 用户资料  
 
3 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 17:24 
头像

注册: 2009-05-08 14:18
帖子: 3332
地址: 河南新乡
系统: Arch
送出感谢: 19
接收感谢: 10
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;
}


页首
 用户资料  
 
4 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 17:30 
头像

注册: 2010-06-16 1:05
帖子: 14676
地址: Tencent
系统: Mac OS X
送出感谢: 1
接收感谢: 153
人家py速度本来就不是非常快嘛,用c写拓展haha~


_________________
twitter求fo:http://twitter.com/maplebeats
博客求踩:http://maplebeats.com


页首
 用户资料  
 
5 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 17:39 
头像

注册: 2011-06-07 14:20
帖子: 3866
系统: Mint18
送出感谢: 17
接收感谢: 65
我好奇x**0.5和math.sqrt(x)哪个快一点?不太清楚哦。


_________________
wiki: ubuntu 技巧


页首
 用户资料  
 
6 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 17:49 
头像

注册: 2010-06-16 1:05
帖子: 14676
地址: Tencent
系统: Mac OS X
送出感谢: 1
接收感谢: 153
我用手机运行那个123456789,运行了1分多钟没出结果,手机发热我把它关了。py for android效率无敌啊


_________________
twitter求fo:http://twitter.com/maplebeats
博客求踩:http://maplebeats.com


页首
 用户资料  
 
7 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 18:00 
头像

注册: 2009-04-11 23:46
帖子: 4141
系统: Arch Linux
送出感谢: 11
接收感谢: 125
xw_y_am 写道:

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

有木有什么好的办法呢。。。。

这还好啦。如果 Python 的计算效率不够,那么用 C 扩展吧。
PS: 你那个 C++ 版本的如果开优化的话应该立马出结果吧?


_________________
我的博客 https://blog.lilydjwg.me/
提问的智慧
Arch Linux 中文论坛

我的vimrc: https://git.io/vimrc


页首
 用户资料  
 
8 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 18:04 
头像

注册: 2009-05-08 14:18
帖子: 3332
地址: 河南新乡
系统: Arch
送出感谢: 19
接收感谢: 10
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;
}


页首
 用户资料  
 
9 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 19:18 
头像

注册: 2011-06-07 14:20
帖子: 3866
系统: Mint18
送出感谢: 17
接收感谢: 65
看看这个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))


_________________
wiki: ubuntu 技巧



_________________
评价: 3.7% xw_y_am
 
页首
 用户资料  
 
10 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 19:41 
头像

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

你这个要速度快的话,就用numpy的sweave去内联c,很适合你这个例子(你这个例子无法向量化的,所以内联c肯定可以接近原始c的速度)。


_________________
https://github.com/tangboyun
http://tangboyun.is-programmer.com/
提问的智慧————Eric Steven Raymond
回答的智慧————Andrew Clarke
吾尝终日而思矣,不如须臾之所学也;吾尝跂而望矣,不如登高之博见也。
急急急标题什么的,最讨厌了!
急急复急急,急急何其多,我生待急急,万事急急急。



_________________
评价: 3.7% xw_y_am
 
页首
 用户资料  
 
11 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 20:10 
头像

注册: 2010-06-16 1:05
帖子: 14676
地址: Tencent
系统: Mac OS X
送出感谢: 1
接收感谢: 153
b33e 写道:
我好奇x**0.5和math.sqrt(x)哪个快一点?不太清楚哦。

q我用手机试了下,**比sqrt快近5倍-_-#


_________________
twitter求fo:http://twitter.com/maplebeats
博客求踩:http://maplebeats.com


页首
 用户资料  
 
12 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 20:13 
头像

注册: 2009-05-08 14:18
帖子: 3332
地址: 河南新乡
系统: Arch
送出感谢: 19
接收感谢: 10
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;
}


页首
 用户资料  
 
13 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 20:18 
头像

注册: 2009-05-08 14:18
帖子: 3332
地址: 河南新乡
系统: Arch
送出感谢: 19
接收感谢: 10
枫叶饭团 写道:
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;
}


页首
 用户资料  
 
14 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 20:33 
头像

注册: 2010-06-16 1:05
帖子: 14676
地址: Tencent
系统: Mac OS X
送出感谢: 1
接收感谢: 153
py for android坑爹呢


_________________
twitter求fo:http://twitter.com/maplebeats
博客求踩:http://maplebeats.com


页首
 用户资料  
 
15 楼 
 文章标题 : Re: Project Euler No.10 题,相同的算法用 C++ 和 Python 耗时差异巨大
帖子发表于 : 2012-04-17 20:35 
头像

注册: 2010-10-07 14:23
帖子: 33999
地址: 某系某星某洲某国某省某市
系统: Archdows10
送出感谢: 29
接收感谢: 151
搞计算,fortran吧,比c都快。。。


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


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 34 篇帖子 ]  前往页数 1, 2, 3  下一页

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 4 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译