Быстро вычислить `точка (a (n: конец), b (1: конец-n))`

Question

Предположим, у нас есть два одномерных массива значений a и b, которые оба имеют длину N.Я хочу создать новый массив c так, чтобы c(n)=dot(a(n:N), b(1:N-n+1)) я, конечно, мог сделать это, используя простой цикл:

for n=1:N
    c(n)=dot(a(n:N), b(1:N-n+1));
end

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

Answer 1

Решение с использованием 1D свертки conv:

out = conv(a, flip(b));
c = out(ceil(numel(out)/2):end);

В conv первый вектор умножается на обратную версию второго вектора, поэтому нам нужно вычислить свертку a ипереверните b и обрежьте ненужную часть.

Answer 2

Это интересная проблема!

Я собираюсь предположить, что a и b - векторы столбцов одинаковой длины.Давайте рассмотрим простой пример:

a = [9;10;2;10;7];
b = [1;3;6;10;10];
% yields:
c = [221;146;74;31;7];

Теперь давайте посмотрим, что произойдет, когда мы вычислим свертку этих векторов:

>> conv(a,b)
ans =
     9
    37
    86
   166
   239
   201
   162
   170
    70

>> conv2(a, b.')
ans =
     9    27    54    90    90
    10    30    60   100   100
     2     6    12    20    20
    10    30    60   100   100
     7    21    42    70    70

Мы заметили, что c является суммой элементоввдоль нижних диагоналей результата conv2.Чтобы было понятнее, мы транспонируем, чтобы получить диагонали в том же порядке, что и значения в c:

>> triu(conv2(a.', b))
ans =
     9    10     2    10     7
     0    30     6    30    21
     0     0    12    60    42
     0     0     0   100    70
     0     0     0     0    70

Так что теперь встает вопрос суммирования диагоналей матрицы, равной более распространенная проблема с существующим решением, например, от Андрея Боброва:

C = conv2(a.', b);
p = sum( spdiags(C, 0:size(C,2)-1) ).'; % This gives the same result as the loop.