1

Numpy の学習を始めたので、これを書く方法を探しています。オイラー 1 の一般化を書きました。除数のリストと数値が必要です。たとえば、[3, 5] とオイラー 1 の 1000 です。

単純に純粋な python で:

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

これは、range(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])

range(2,20)、1000000 の場合、約 0.45 秒で実行されます。

私の 3 番目の試みは、foor ループを削除して純粋な 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)])

これは、range(2,20)、100000 の場合、約 0.5 秒で実行されます。

「純粋な」numpyでそれを書くためのより速い方法はありますか、それとも恥ずかしがらないforループですか？

注：除数リストを減らすことで最適化できることはわかっているので、それについてコメントする必要はありません:)

4

2 に答える 2

0

1 つの 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 に答える