Тропическая свертка с numpy

Question

Справочная информация: я пишу пакет, который требует чего-то очень похожего на свертку массива. (Тропическая Свертка также называется минус плюс свертка). Статья в Википедии не велика, но она здесь: https://en.wikipedia.org/wiki/Network_calculus#Min -plus_algebra

В принципе, если d = mpConv (a, b), то d [c] = max (a [J] + Ь [* * -j тысячу двадцать-три]). Стандартная свертка будет d [c] = сумма (a [j] * b [c -j]).

У меня есть два numpy. Массива a и b, и выходной диапазон должен быть r , Итак, вот что у меня есть сейчас:

def mpConv(a,b,r):
    A = len(a) - 1
    B = len(b) - 1
    return [numpy.amax(a[max(0,c-B)  :min(c,A)+1    :+1]+
                       b[min(c-B,0)-1:max(0,c-A)-B-2:-1],0) for c in r]

Это работает так, как нужно. Раньше я не имел дело с numpy, поэтому меня интересуют эффективность, скорость и просто общие способы использования numpy лучше.

Есть ли более эффективный способ для l oop по сравнению с диапазон г? (Это всегда будет иметь вид r = numpy .arange (s, e), если это имеет значение.)

Это «numpy способ ведения дел?»

Подпрограмма numpy .convolve написана на C, поэтому исходный код не слишком полезен для этого. Я полагаю, я мог бы написать это в C, но я бы потерял силу и легкость python.

Информация о бонусе: Самый быстрый способ, которым я ожидаю, здесь: https://arxiv.org/abs/1212.4771 (Ожерелья, Свертки и X + Y от Бремнера, Чана, Демейна, Эриксона, Уртадо, Яконо, Лангермана, Патраску, Таслакяна) Я не слишком беспокоюсь об этом. Я бы, наверное, реализовал это в C первым. Я не верю, что получу значительное увеличение скорости от не наивных методов.

Answer 1

Если кому-то это понадобится когда-либо, вот что я считаю наиболее приятным после некоторого копания:

Эта функция вычисляет сложение всех необходимых пар и помещает их в массив.

import numpy
def plus_convolve(a, b, e=0):
    if len(a)<len(b):
        return plus_convolve(b,a,e)
    return numpy.concatenate((                    #This is for padding (as stated below)
        numpy.add(a,b[:,None]),                   #Do the desired outer addition. Broadcasting handles this well.
        numpy.broadcast_to(e,(len(b),)+b.shape)   #Pad the end of the result with, e, the fill value.
        ),1).ravel()[:-b.size].reshape(           #We reshape the array to have one fewer row. This makes the convolution line up exactly like we want
            (len(b),len(a)+len(b)-1)+b.shape[1:]  #This is the new size
        )

Мы можем просто вычислить макс каждой строки, чтобы получить свертку макс-плюс (в этом примере я свертываю матрицу 1000x10 с матрицей 2000x10.)

a=numpy.random.randint(0,20,(1000,10))
b=numpy.random.randint(0,20,(2000,10))
numpy.amax(plus_convolve(a,b),0)

Я считаю, что это быстрее так как он переносит всю работу на numpy, но использует больше памяти. Мой оригинал довольно хорош, если проблема с памятью.

Я полагаю, что вопрос был слишком эзотерическим c для SO, но если кому-то это понадобится, оставьте комментарий: Мне было бы любопытно, почему.