Есть ли способ сэкономить время, не вычисляя ненужные суммы? - PullRequest
Новая
       3

Есть ли способ сэкономить время, не вычисляя ненужные суммы?

2 голосов
/ 01 июня 2019

Цель

Учитывая двумерный массив A, я должен продолжать добавлять +1 к значению первой строки в каждом столбце до тех пор, пока суммы столбцов не будут равны одному значению,например, 28.

Мое решение

Возможно, это не лучшее из решений, но, учитывая то, что я хотел бы высказать, оно подойдет.Это должно быть упрощенным примером.В исходной версии это основано на распределении вероятностей того, получает ли первая или вторая строка +1, и оно отличается среди столбцов.Кроме того, это должно быть сделано один за другим, поскольку распределение вероятностей изменяется в зависимости от того, получил ли первый или второй ряд столбца +1 в предыдущем цикле.Таким образом, суммирование столбцов и итерация необходимы. 

import numpy as np

A = np.arange(20).reshape(2, 10)
print(A)

MASK = A.sum(axis=0) < 28
print(A.sum(axis=0) < 28)

while np.any(MASK):
    LUCKYROW = np.repeat(0, np.count_nonzero(MASK))
    A[LUCKYROW, MASK] += 1
    MASK = A.sum(axis=0) < 28
    print(A.sum(axis=0) < 28)
print(A)

Давайте посмотрим на вывод: 

[[ 0  1  2  3  4  5  6  7  8  9]
 [10 11 12 13 14 15 16 17 18 19]]
[ True  True  True  True  True  True  True  True  True False]
[ True  True  True  True  True  True  True  True  True False]
[ True  True  True  True  True  True  True  True False False]
[ True  True  True  True  True  True  True  True False False]
[ True  True  True  True  True  True  True False False False]
[ True  True  True  True  True  True  True False False False]
[ True  True  True  True  True  True False False False False]
[ True  True  True  True  True  True False False False False]
[ True  True  True  True  True False False False False False]
[ True  True  True  True  True False False False False False]
[ True  True  True  True False False False False False False]
[ True  True  True  True False False False False False False]
[ True  True  True False False False False False False False]
[ True  True  True False False False False False False False]
[ True  True False False False False False False False False]
[ True  True False False False False False False False False]
[ True False False False False False False False False False]
[ True False False False False False False False False False]
[False False False False False False False False False False]
[[18 17 16 15 14 13 12 11 10  9]
 [10 11 12 13 14 15 16 17 18 19]]

Хорошо, это работает, но почему я вычисляю сумму каждого столбцав каждом цикле?Основываясь на предыдущих циклах, я знаю, какая сумма столбца уже достигла целевого значения.Если я воспользуюсь этой информацией, я смогу сэкономить время.

Мое второе решение 

import numpy as np

A = np.arange(20).reshape(2, 10)
print(A)

MASK = A.sum(axis=0) < 28
print(A.sum(axis=0) < 28)

while np.any(MASK):
    LUCKYROW = np.repeat(0, np.count_nonzero(MASK))
    A[LUCKYROW, MASK] += 1
    MASK[MASK] = A[:, MASK].sum(axis=0) < 28
    print(A[:, MASK].sum(axis=0) < 28)
print(A)

И вывод: 

[[ 0  1  2  3  4  5  6  7  8  9]
 [10 11 12 13 14 15 16 17 18 19]]
[ True  True  True  True  True  True  True  True  True False]
[ True  True  True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True]
[ True  True  True  True  True  True]
[ True  True  True  True  True  True]
[ True  True  True  True  True]
[ True  True  True  True  True]
[ True  True  True  True]
[ True  True  True  True]
[ True  True  True]
[ True  True  True]
[ True  True]
[ True  True]
[ True]
[ True]
[]
[[18 17 16 15 14 13 12 11 10  9]
 [10 11 12 13 14 15 16 17 18 19]]

Кажется, это работает.Хотя возникает одна проблема.Это не быстрее, чем первое решение.Я пробовал использовать 25000 столбцов и 74998 в качестве целевого значения, но они примерно равны по времени.

Мой запрос

Я думаю, что у меня может быть принципиальное недопонимание либо операций ndarray, либо индексации ndarray.Второе решение должно делать все меньше и меньше вычислений с каждым циклом, поэтому я ожидаю значительного улучшения производительности.Я не могу найти объяснение.Где мой ход мысли неисправен?

Ответы [ 2 ]

1 голос
/ 01 июня 2019

Поскольку вы изменяете только первую строку, вам не нужно пересчитывать сумму столбцов на каждой итерации. Фактически, поскольку единственным изменением является добавление 1 к некоторым элементам в первой строке, вам вообще не нужно итерировать. 

A = np.arange(20).reshape(2, 10)
s = A.sum(0)
d = max(s) - s
A[0] += d

>>> A
array([[18, 17, 16, 15, 14, 13, 12, 11, 10,  9],
       [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]])

Это может быть невозможно при более сложных вычислениях, но для сумм это простой способ.

Может быть несколько причин, по которым ваш «более быстрый» код на самом деле не работает быстрее. Во-первых, слава за фактическое профилирование кода. Первая причина в том, что A очень мало. Как правило, numpy дает преимущество в скорости только с тысячами или десятками тысяч элементов в массиве.

Во-вторых, в «более быстром» коде строка 

MASK[MASK] = A[:, MASK].sum(axis=0) < 28

создает копию всех строк в A, проиндексированных MASK. Это может быть довольно дорогой операцией, поэтому суммирование дополнительных строк в исходной версии с использованием MASK = A.sum(axis=0) < 28 может быть быстрее просто потому, что для этого не требуется дополнительная копия.

0 голосов
/ 01 июня 2019

Демонстрация того, как индексирование влияет на суммы: 

In [140]: x = np.arange(10000)                                                       
In [141]: timeit x.sum()                                                             
13.4 µs ± 183 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

суммирование половины элементов, даже с быстрым срезом view не экономит столько времени: 

In [142]: timeit x[:5000].sum()                                                      
10.8 µs ± 78.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Расширенное индексирование или маскирование медленнее: 

In [143]: %%timeit idx=np.arange(5000) 
     ...: x[idx].sum() 

21.3 µs ± 1.12 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [144]: %%timeit 
     ...: x[x<=5000].sum() 

34.4 µs ± 1.34 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

На современных компьютерах базовые математические вычисления не так уж дороги. Выбор элементов и итерация по массивам так же затратны по времени, как и само добавление.

...