Numpy Project Euler 1 Обобщенная оптимизация

Question

Я начал изучать Numpy и ищу способы написать это. Я написал обобщение Эйлера 1. Он принимает список делителей и число, например [3, 5] и 1000 в Эйлере 1.

Наивно в чистом питоне

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

Это работает примерно за 2,5 секунды для диапазона (2,20), 1000000.

Моя первая и лучшая на данный момент попытка ошеломить выглядит так:

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]) 

И работает около 0,45 секунд для диапазона (2,20), 1000000.

Моя третья попытка состояла в том, чтобы удалить петлю 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)])

Это работает примерно за 0,5 секунды для диапазона (2,20), 100000.

Есть ли более быстрый способ записать это в "чистом" виде или нет, чтобы не уклоняться от циклов?

Примечание: я знаю, что вы можете оптимизировать его, уменьшив список делителей, поэтому нет необходимости комментировать это:)

Answer 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 версии.

Answer 2

Вы можете использовать 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