我有用Python/NumPy编写的代码
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,那么他们会自动获胜,而我会输。
最快的解决办法现在太快了,时间太快了。因此,我将n增加到10,并设置iters = 100000来比较最好的。在这个标准下,最快的是。
我的机器计时将在我的机器上运行。这是一个标准的ubuntu安装在一个AMD FX-8350八核处理器上.这也意味着我需要能够运行您的代码。
后续张贴,因为这次比赛太容易得到一个x100加速,我已经张贴了一个后续谁想要锻炼他们的速度大师的专业知识。请参阅到底有多慢(第二部分)?
发布于 2014-04-27 05:40:45
原始Python的直接翻译。
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))发布于 2014-04-27 10:30:46
在我的机器上使用0.015s,OP的原始代码为~ 7.7s。试图通过生成随机数组并在相同的循环中进行卷积来进行优化,但这似乎没有多大的区别。
第一个数组是通过接受一个整数生成的,用二进制将其写出来,并将所有的1到-1和所有的0更改为1,其余的都应该非常简单。
编辑:现在我们没有将n作为int,而是将n作为宏定义的常量,因此我们可以使用int arr[n];而不是malloc。
Edit2:而不是内置的rand()函数,它现在实现了一个xorshift。此外,在生成随机数组时,会删除许多条件语句。
汇编说明:
gcc -O3 -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize -Wall ./test.c -o ./test代码:
#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;
}发布于 2014-04-27 00:17:59
我不希望击败任何编译语言,而且有东西告诉我,这需要一台奇迹般的机器才能得到小于0.09的S,但我还是想提交这个J,因为它相当精巧。
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,特别是两个数字,从对角线和到卷积的最长元素--这大约是时间的一半。
https://codegolf.stackexchange.com/questions/26323
复制相似问题