Использование монотонности в Numpy Array - PullRequest
Новая
       8

Использование монотонности в Numpy Array

0 голосов
/ 29 сентября 2019

У меня большой массив Numpy, и я хочу применить некоторую функцию поэлементно, если элемент положительный, и заменить на -inf в противном случае. Массив представляет собой внешнюю разницу двух векторов (см. Пример, если не ясно), и поэтому он имеет определенную структуру: каждая строка начинается с положительных чисел и в какой-то момент становится отрицательной, например, когда я вычитаю [1 ,. .., 10] из [3,4,5] я получаю матрицу 

2  1  0 -1 -2 -3 ...
3  2  1  0 -1 -2 ...
4  3  2  1  0 -1 ...

(конечно, в реальном приложении векторы не являются равномерно пробелами)

и яхочу получить 

f(2)  f(1)  f(0)  -inf -inf -inf ...
f(3)  f(2)  f(1)  f(0) -inf -inf ...
f(4)  f(3)  f(2)  f(1) f(0) -inf ...

Существует простое решение: 

import numpy as np

x = np.arange(2000,dtype=np.float64)
y = np.arange(4000,dtype=np.float64)

M = x[:,None] - y[None,:]

i_pos = M>=0

M[i_pos] = np.sqrt(M[i_pos])
M[~i_pos] = -np.inf

Это работает, но кажется довольно неэффективным, поскольку поиск положительных элементов не учитывает монотонность (если путешествовать по рядумы столкнулись с отрицательным числом, мы не должны идти дальше).

Более общий пример 

x = np.arange(10000,dtype=np.float64).reshape(100,100)
y = np.arange(4000,dtype=np.float64)

M = x[:,:,None] - y[None,None,:]

i_pos = M>0

M[i_pos] = np.sqrt(M[i_pos])
M[~i_pos] = -np.inf

занимает больше одной секунды.

Есть ли способ разумно использовать эту структуру для улучшения скорости? Я пытался отработать функцию Numba с помощью цикла, но, похоже, он не был намного быстрее (1,38 с против 1,18 с + время компиляции).

1 Ответ

1 голос
/ 30 сентября 2019

Распределение памяти является ограничивающей частью

Если вы используете такие функции, как sqrt, exp, sin, потому что убедитесь, что вы установили Intel SVML . Также добавьте все, что вы пробовали до сих пор и как вы получили время.

Ваше решение Numpy использует временные массивы, поэтому должно быть достаточно места для улучшения.

Пример 

import numpy as np
import numba as nb

def calc_M(x,y):
    M = x[:,:,None] - y[None,None,:]

    i_pos = M>0

    M[i_pos] = np.sqrt(M[i_pos])
    M[~i_pos] = -np.inf
    return M

@nb.njit(parallel=True)
def calc_M_nb_1(x,y):
    res=np.empty((x.shape[0],x.shape[1],y.shape[0]))
    for i in nb.prange(x.shape[0]):
        for j in range(x.shape[1]):
            for k in range(y.shape[0]):
                val= x[i,j]-y[k]
                if val>0:
                    res[i,j,k]=np.sqrt(val)
                else:
                    res[i,j,k]=-np.inf
    return res

@nb.njit(parallel=True)
def calc_M_nb_2(x,y,res):
    for i in nb.prange(x.shape[0]):
        for j in range(x.shape[1]):
            for k in range(y.shape[0]):
                val= x[i,j]-y[k]
                if val>0:
                    res[i,j,k]=np.sqrt(val)
                else:
                    res[i,j,k]=-np.inf
    return res

Время 

x = np.arange(10000,dtype=np.float64).reshape(100,100)
y = np.arange(4000,dtype=np.float64)
res=np.empty((x.shape[0],x.shape[1],y.shape[0]))

%timeit res_1=calc_M(x,y)
469 ms ± 3.42 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit res_2=calc_M_nb_1(x,y)
79.5 ms ± 671 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
res=np.empty((x.shape[0],x.shape[1],y.shape[0]))
%timeit res_3=calc_M_nb_2(x,y,out)
25.5 ms ± 204 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Если сравнить время calc_M_nb_2 и calc_M_nb_1 видно, что выделение памяти занимает больше времени, чем все вычисления, что не является редким случаем в простых функциях. Конечно, не всегда возможно избежать выделения памяти, но если вы хотите применить эту функцию ко многим аналогичным входам (размер массива), вы можете получить некоторое ускорение.

...