Как эффективно кешировать и применить scipy gammaln к массиву numpy?

Я ищу способ кешировать результаты функции gammaln, применить ее к массиву и затем суммировать результаты. В настоящее время я могу кэшировать результаты gammln с помощью простого словарного подхода, но, похоже, я не могу эффективно итерировать массив. Ниже приведен иллюстративный фрагмент кода проблемы.

import numpy as np
from scipy.special import gammaln

gammaln_cache_dic = {}
def gammaln_cache(x):
    if x not in gammaln_cache_dic:
        val = gammaln(x)
        gammaln_cache_dic[x] = val
    else:
        val = gammaln_cache_dic[x]
    return val

def cache_gammaln_sum(M):
    res_sum = 0.0
    for x in np.fromiter( [ x for x in M ], int ):
        res_sum += gammaln_cache(x)
    return res_sum

np_array = np.random.randint(5, size=(500))*1000+3
start = time.time()
for i in np_array:
    gammaln(i)
end = time.time()
print("NO cache gammaln %f secs" % (end - start))

start = time.time()
for i in np_array:
    gammaln_cache(i)
end = time.time()
print("cache gammaln %f secs" % (end - start))

start = time.time()
gammaln(np_array).sum()
end = time.time()
print("NO cache gammaln sum %f secs" % (end - start))

start = time.time()
cache_gammaln_sum(np_array)
end = time.time()
print("cache gammaln sum %f secs" % (end - start))
Источник

3 ответа

Решение

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

In [1]: from scipy.special import gammaln
In [2]: np_array = np.random.randint(5, size=(500))*1000+3
In [3]: np_array.shape
Out[3]: (500,)
In [4]: timeit gammaln(np_array).sum()
....
10000 loops, best of 3: 34.9 µs per loop

Оценка каждого элемента будет намного медленнее

In [5]: timeit sum([gammaln(i) for i in np_array])
1000 loops, best of 3: 1.8 ms per loop

Простая итерация по массиву медленнее.

In [6]: timeit sum([i for i in np_array])
10000 loops, best of 3: 127 µs per loop

В этом случае значения представляют собой небольшой набор целых чисел

In [10]: np.unique(np_array)
Out[10]: array([   3, 1003, 2003, 3003, 4003])

Но идентификация этих уникальных значений занимает почти столько же времени, сколько и вычисление функции для всех 500.

In [11]: timeit np.unique(np_array)
...
In [12]: timeit gammaln(np.unique(np_array))

На самом деле медленнее, если я также попрошу индексы, которые могут восстановить массив:

In [14]: timeit np.unique(np_array, return_inverse=True)    
10000 loops, best of 3: 54 µs per loop

Есть рецепты кэширования или запоминания для Python, в том числе @functools.lru_cache декоратор. Но я не видел их много с numpy массивы. Если ваша проблема подходит для кеширования, я подозреваю, что лучше всего это делать в коде более низкого уровня, например, в Cython, и с использованием существующих библиотек кеша C или C++.

Кеш с уникальным

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

In [5]: unq, idx=np.unique(np_array, return_inverse=True)
In [6]: res1= gammaln(np_array)
In [7]: res2= gammaln(unq)
In [8]: res2= res2[idx]
In [9]: np.allclose(res1, res2)
Out[9]: True

Но сравните время:

In [10]: timeit res1= gammaln(np_array)
10000 loops, best of 3: 29.1 µs per loop

In [11]: %%timeit
    ...: unq, idx=np.unique(np_array, return_inverse=True)
    ...: res2= gammaln(unq)[idx]
10000 loops, best of 3: 63.3 µs per loop

Большая часть этого дополнительного времени находится в расчете unique; когда у нас есть отображение, его применение выполняется довольно быстро:

In [12]: timeit res2=gammaln(unq)[idx]
...
100000 loops, best of 3: 6.12 µs per loop

уникальный с суммой

Возврат суммы значений, а не фактических значений, немного сдвигается относительно времени

In [13]: %timeit res1= gammaln(np_array).sum()
10000 loops, best of 3: 35.3 µs per loop
In [14]: %%timeit
    ...: unq, idx=np.unique(np_array, return_inverse=True)
    ...: res2= gammaln(unq)[idx].sum()
10000 loops, best of 3: 71.3 µs per loop

С подходом подсчета Пола Панцера

In [21]: %%timeit 
    ...: unq, cnt=np.unique(np_array, return_counts=True)
    ...: res=(gammaln(unq)*cnt).sum()
10000 loops, best of 3: 59.5 µs per loop
In [22]: %%timeit 
    ...: unq, cnt=np.unique(np_array, return_counts=True)
    ...: res=np.dot(gammaln(unq),cnt)
10000 loops, best of 3: 52.1 µs per loop
Источник

Вы могли бы использовать np.unique

uniq, counts = np.unique(data, return_counts=True)
result = np.dot(gammaln(uniq), counts)

uniq - отсортированные уникальные значения в данных, return_counts Ключевое слово указывает функции также возвращать кратности.

Вторая строка оценивает gammaln один раз для каждого отдельного элемента, умножается на количество вхождений и сумм.

Вы также можете сохранить gammaln(uniq) и использовать его в качестве таблицы look_up.

look_up = gammaln(uniq)
indices = np.searchsorted(uniq, new_samples)
hit = uniq[indices] == new_samples
result = look_up[indices[hit]]
miss = new_samples[~hit]
Источник

gammalnкак и большинство функций из scipy.special является ufunc, то есть, учитывая массив NumPy, он работает поэлементно и возвращает массив NUMPY:

In [1]: import numpy as np

In [2]: from scipy.special import gammaln

In [3]: x = np.arange(1, 8)

In [4]: gammaln(x)
Out[4]: 
array([ 0.        ,  0.        ,  0.69314718,  1.79175947,  3.17805383,
        4.78749174,  6.57925121])

In [5]: gammaln(x).sum()
Out[5]: 17.029703434928095

Фактически, если вы дадите ему список чисел, он конвертирует его в массив внутри, поэтому

In [6]: gammaln(list(range(1, 8)))
Out[6]: 
array([ 0.        ,  0.        ,  0.69314718,  1.79175947,  3.17805383,
        4.78749174,  6.57925121])

Также обратите внимание, что итерации ufunc происходят в скомпилированном коде. Таким образом, маловероятно, что вы сможете добиться гораздо большей производительности с любым типом кэширования и итераций Python и т. Д.

Источник
Другие вопросы по тегам