首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Python到底有多慢?(或者你的语言有多快?)

问Python到底有多慢?(或者你的语言有多快?)
EN

Code Golf用户
提问于 2014-04-26 18:26:17
回答 10查看 111.6K关注 0票数 153

我有用Python/NumPy编写的代码

代码语言:javascript
复制
from __future__ import division
import numpy as np
import itertools

n = 6
iters = 1000
firstzero = 0
bothzero = 0
""" The next line iterates over arrays of length n+1 which contain only -1s and 1s """
for S in itertools.product([-1, 1], repeat=n+1):
    """For i from 0 to iters -1 """
    for i in xrange(iters):
        """ Choose a random array of length n.
            Prob 1/4 of being -1, prob 1/4 of being 1 and prob 1/2 of being 0. """
        F = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n)
        """The next loop just makes sure that F is not all zeros."""
        while np.all(F == 0):
            F = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n)
        """np.convolve(F, S, 'valid') computes two inner products between
        F and the two successive windows of S of length n."""
        FS = np.convolve(F, S, 'valid')
        if FS[0] == 0:
            firstzero += 1
        if np.all(FS == 0):
            bothzero += 1

print("firstzero: %i" % firstzero)
print("bothzero: %i" % bothzero)

它是计算两个随机阵列卷积的次数,其中一个比另一个长,具有特定的概率分布,在第一个位置有一个0,在两个位置上都是0。

我和一位朋友打赌,他说Python是一种非常糟糕的语言,用它来编写需要快速的代码。在我的电脑上需要9s。他说,如果用“适当的语言”写,它的速度可以快100倍。

我们面临的挑战是,在您选择的任何语言中,看看这段代码是否能够使速度提高100倍。我将测试你的代码和最快的一周后,将获胜。如果有人低于0.09,那么他们会自动获胜,而我会输。

状态

  • 巨蟒。被Alistair Buxon加速了30倍!虽然不是最快的解决方案,但事实上它是我最喜欢的。
  • 八度。通过“Thethos”提速100倍。
  • 生锈。由@dbaupp加速500倍。
  • C++。由盖伊·西尔顿提速570次。
  • 用@ace加速727倍。
  • C++。惊人的快“斯特凡。

最快的解决办法现在太快了,时间太快了。因此,我将n增加到10,并设置iters = 100000来比较最好的。在这个标准下,最快的是。

  • C.7.5s @ace。
  • C++。1由@斯特凡。

我的机器计时将在我的机器上运行。这是一个标准的ubuntu安装在一个AMD FX-8350八核处理器上.这也意味着我需要能够运行您的代码。

后续张贴,因为这次比赛太容易得到一个x100加速,我已经张贴了一个后续谁想要锻炼他们的速度大师的专业知识。请参阅到底有多慢(第二部分)?

EN

回答 10

Code Golf用户

发布于 2014-04-27 05:40:45

锈蚀: 0.011s

原始Python: 8.3

原始Python的直接翻译。

代码语言:javascript
复制
extern crate rand;

use rand::Rng;

static N: uint = 6;
static ITERS: uint = 1000;

fn convolve<T: Num>(into: &mut [T], a: &[T], b: &[T]) {
    // we want `a` to be the longest array
    if a.len() < b.len() {
        convolve(into, b, a);
        return
    }

    assert_eq!(into.len(), a.len() - b.len() + 1);

    for (n,place) in into.mut_iter().enumerate() {
        for (x, y) in a.slice_from(n).iter().zip(b.iter()) {
            *place = *place + *x * *y
        }
    }
}

fn main() {
    let mut first_zero = 0;
    let mut both_zero = 0;
    let mut rng = rand::XorShiftRng::new().unwrap();

    for s in PlusMinus::new() {
        for _ in range(0, ITERS) {
            let mut f = [0, .. N];
            while f.iter().all(|x| *x == 0) {
                for p in f.mut_iter() {
                    match rng.gen::<u32>() % 4 {
                        0 => *p = -1,
                        1 | 2 => *p = 0,
                        _ => *p = 1
                    }
                }
            }

            let mut fs = [0, .. 2];
            convolve(fs, s, f);

            if fs[0] == 0 { first_zero += 1 }
            if fs.iter().all(|&x| x == 0) { both_zero += 1 }
        }
    }

    println!("{}\n{}", first_zero, both_zero);
}



/// An iterator over [+-]1 arrays of the appropriate length
struct PlusMinus {
    done: bool,
    current: [i32, .. N + 1]
}
impl PlusMinus {
    fn new() -> PlusMinus {
        PlusMinus { done: false, current: [-1, .. N + 1] }
    }
}

impl Iterator<[i32, .. N + 1]> for PlusMinus {
    fn next(&mut self) -> Option<[i32, .. N+1]> {
        if self.done {
            return None
        }

        let ret = self.current;

        // a binary "adder", that just adds one to a bit vector (where
        // -1 is the zero, and 1 is the one).
        for (i, place) in self.current.mut_iter().enumerate() {
            *place = -*place;
            if *place == 1 {
                break
            } else if i == N {
                // we've wrapped, so we want to stop after this one
                self.done = true
            }
        }

        Some(ret)
    }
}
  • 用--opt-level=3编译
  • 我的生锈编译器是最近的夜间:(准确地说是rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700))
票数 44
EN

Code Golf用户

发布于 2014-04-27 10:30:46

C

在我的机器上使用0.015s,OP的原始代码为~ 7.7s。试图通过生成随机数组并在相同的循环中进行卷积来进行优化,但这似乎没有多大的区别。

第一个数组是通过接受一个整数生成的,用二进制将其写出来,并将所有的1到-1和所有的0更改为1,其余的都应该非常简单。

编辑:现在我们没有将n作为int,而是将n作为宏定义的常量,因此我们可以使用int arr[n];而不是malloc。

Edit2:而不是内置的rand()函数,它现在实现了一个xorshift。此外,在生成随机数组时,会删除许多条件语句。

汇编说明:

代码语言:javascript
复制
gcc -O3 -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize -Wall ./test.c -o ./test

代码:

代码语言:javascript
复制
#include <stdio.h>
#include <time.h>

#define n (6)
#define iters (1000)
unsigned int x,y=34353,z=57768,w=1564; //PRNG seeds

/* xorshift PRNG
 * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
 * Used under CC-By-SA */
int myRand() {
    unsigned int t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

int main() {
    int firstzero=0, bothzero=0;
    int arr[n+1];
    unsigned int i, j;
    x=(int)time(NULL);

    for(i=0; i< 1<<(n+1) ; i++) {
        unsigned int tmp=i;
        for(j=0; j<n+1; j++) {
            arr[j]=(tmp&1)*(-2)+1;
            tmp>>=1;
        }
        for(j=0; j<iters; j++) {
            int randArr[n];
            unsigned int k, flag=0;
            int first=0, second=0;
            do {
                for(k=0; k<n; k++) {
                    randArr[k]=(1-(myRand()&3))%2;
                    flag+=(randArr[k]&1);
                    first+=arr[k]*randArr[k];
                    second+=arr[k+1]*randArr[k];
                }
            } while(!flag);
            firstzero+=(!first);
            bothzero+=(!first&&!second);
        }
    }
    printf("firstzero %d\nbothzero %d\n", firstzero, bothzero);
    return 0;
}
票数 21
EN

Code Golf用户

发布于 2014-04-27 00:17:59

J

我不希望击败任何编译语言,而且有东西告诉我,这需要一台奇迹般的机器才能得到小于0.09的S,但我还是想提交这个J,因为它相当精巧。

代码语言:javascript
复制
NB. constants
num =: 6
iters =: 1000

NB. convolve
NB. take the multiplication table                */
NB. then sum along the NE-SW diagonals           +//.
NB. and keep the longest ones                    #~ [: (= >./) #/.
NB. operate on rows of higher dimensional lists  " 1
conv =: (+//. #~ [: (= >./) #/.) @: (*/) " 1

NB. main program
S  =: > , { (num+1) # < _1 1                NB. all {-1,1}^(num+1)
F  =: (3&= - 0&=) (iters , num) ?@$ 4       NB. iters random arrays of length num
FS =: ,/ S conv/ F                          NB. make a convolution table
FB =: +/ ({. , *./)"1 ] 0 = FS              NB. first and both zero
('first zero ',:'both zero ') ,. ":"0 FB    NB. output results

这需要大约0.5 S在笔记本电脑上的前十年,只有大约20倍的速度比Python的答案。大部分时间都花在conv上,因为我们写它很懒散(我们计算整个卷积),而且是完全通用的。

因为我们了解S和F,所以我们可以通过对这个程序进行特定的优化来加快速度。我想出的最好的是conv =: ((num, num+1) { +//.)@:(*/)"1,-select,特别是两个数字,从对角线和到卷积的最长元素--这大约是时间的一半。

票数 18
EN
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codegolf.stackexchange.com/questions/26323

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档