1

我已经开始学习 Numpy，我正在寻找一些方法来编写这个。我写了欧拉 1 的概括。它需要一个除数列表和一个数字，例如欧拉 1 中的 [3, 5] 和 1000。

在纯python中天真地：

def subn1(divisors, n):
    return sum(i for i in range(1,n) if not all(i % d for d in divisors))

对于范围（2,20），1000000，这将在大约 2.5 秒内运行。

到目前为止，我的第一个也是最好的 numpy 尝试如下所示：

def subn2(divisors, n):
    a = np.arange(1,n) 
    b = np.zeros(a.shape[0], dtype=bool) 
    for d in divisors:
        b += a % d == 0
    return np.sum(a[b])

对于范围（2,20），1000000，运行时间约为 0.45 秒。

我的第三次尝试是删除 foo 循环并使用纯 numpy，但是它在速度部门中丢失了一小部分并且使用了更多内存。

def subn3(divisors, n):
    nums = np.arange(1,n)     
    divs = np.array([divisors]).T
    return np.sum(nums[np.logical_or.reduce(np.mod(nums, divs) == 0, axis=0)])

对于范围（2,20），100000，这将在大约 0.5 秒内运行。

有没有一种更快的方法可以在“纯”numpy 中编写它，或者是 foo 循环不要回避？

注意：我知道您可以通过减少除数列表来优化它，因此无需对此发表评论:)

4

2 回答 2

0

一种 NumPythonic 矢量化方法broadcasting-

def subn_broadcasting(divisors,n):
    a = np.arange(1,n)
    return (a[(a % np.array(divisors)[:,None] == 0).any(0)]).sum()

运行时测试和验证 -

In [14]: # Inputs
    ...: n = 1000
    ...: divisors = range(2,20)
    ...: 

In [15]: print subn1(divisors, n)
    ...: print subn2(divisors, n)
    ...: print subn3(divisors, n)
    ...: print subn_broadcasting(divisors, n)
    ...: 
416056
416056
416056
416056

In [16]: %timeit subn1(divisors, n)
    ...: %timeit subn2(divisors, n)
    ...: %timeit subn3(divisors, n)
    ...: %timeit subn_broadcasting(divisors, n)
    ...: 
1000 loops, best of 3: 1.39 ms per loop
1000 loops, best of 3: 480 µs per loop
1000 loops, best of 3: 434 µs per loop
1000 loops, best of 3: 428 µs per loop

嗯，看起来与n2和n3版本相比没有太大的改进。

于 2015-12-06T11:12:40.573 回答
0

您可以使用np.where，如下所示：

def subn4(divisors, n):
    a = np.arange(np.min(divisors),n) 
    b = np.zeros(a.shape[0], dtype=bool) 
    for d in divisors:
        b += a % d == 0
    return np.sum(a[np.where(b)])

def subn4_(divisors, n):
    a = np.arange(1,n) 
    b = np.zeros(a.shape[0], dtype=bool) 
    for d in divisors:
        b += a % d == 0
    return np.sum(a[np.where(b)])

测试，如前所述：

%timeit subn1(divisors, n)
%timeit subn2(divisors, n)
%timeit subn3(divisors, n)
%timeit subn_broadcasting(divisors, n)
%timeit subn4(divisors, n)
%timeit subn4_(divisors, n)


1 loops, best of 3: 596 ms per loop
10 loops, best of 3: 30.1 ms per loop
10 loops, best of 3: 32 ms per loop
10 loops, best of 3: 31.9 ms per loop
10 loops, best of 3: 28.2 ms per loop
10 loops, best of 3: 27.4 ms per loop
于 2015-12-06T12:42:47.420 回答