19.2 Трансляция

Трансляция определяет поведение бинарных операторов и функций Octave, когда матричные или массивные операнды и аргументы имеют разные размеры. Начиная с версии 3.6.0, Octave автоматически транслирует векторы, матрицы и массивы при использовании поэлементных бинарных операторов и функций. В общем случае массивы меньшего размера «транслируются» вдоль большего массива, пока их формы не станут совместимыми. Правило состоит в том, что соответствующие измерения массивов должны либо

1. быть равны, либо
2. одно из них должно быть равно 1.

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

x = [1 2 3;
     4 5 6;
     7 8 9];

y = [10 20 30];

x + y

Без трансляции x + y вызвало бы ошибку, поскольку размеры не совпадают. Однако при трансляции операция эквивалентна следующей:

x = [1 2 3
     4 5 6
     7 8 9];

y = [10 20 30
     10 20 30
     10 20 30];

x + y
⇒    11   22   33
      14   25   36
      17   28   39

То есть массив меньшего размера [1 3] копируется вдоль единичного измерения (числа строк), пока его размер не станет [3 3]. Однако фактического копирования не происходит. Внутренняя реализация повторно использует элементы вдоль необходимого измерения, чтобы получить требуемый результат без копирования в памяти.

Оба массива можно транслировать относительно друг друга. Например, можно вычислить все попарные разности элементов вектора с самим собой:

y - y'
⇒    0   10   20
    -10    0   10
    -20  -10    0

Здесь векторы размера [1 3] и [3 1] транслируются в матрицы размера [3 3], после чего выполняется обычное вычитание матриц.

Частный случай трансляции, который может быть вам знаком, — когда все измерения транслируемого массива равны 1, то есть массив является скаляром. Поэтому, например, операции x - 42 и max (x, 2) — простые примеры трансляции.

Рассмотрим пример с массивом большей размерности: пусть img — изображение RGB размером [m n 3], и мы хотим умножить каждый цвет на отдельный скаляр. Следующий код выполняет это с помощью трансляции:

img .*= permute ([0.8, 0.9, 1.2], [1, 3, 2]);

Обратите внимание на использование permute для согласования измерений вектора [0.8, 0.9, 1.2] с img.

Для функций, не написанных с учётом семантики трансляции, может быть полезна функция bsxfun, позволяющая обеспечить их трансляцию.

: C = bsxfun (f, A, B)

Применяет бинарную функцию f поэлементно к двум аргументам-массивам A и B, расширяя при необходимости единичные измерения любого из входных аргументов.

f — это дескриптор функции, встроенная функция или строка с именем вычисляемой функции. Функция f должна принимать два аргумента — вектора-столбца одинаковой длины либо вектор-столбец и скаляр.

Измерения A и B должны быть равны или равны единице. Единичные измерения массивов будут расширены до размерности другого массива.

См. также: arrayfun, cellfun.

Трансляция применяется только при выполнении одного из двух условий трансляции. Однако, как и обычно, трансляция не выполняется, если два измерения различаются и ни одно из них не равно 1:

x = [1 2 3
     4 5 6];
y = [10 20
     30 40];
x + y

Это приведёт к ошибке о несовместимых аргументах.

Помимо распространённых арифметических операций, трансляцию поддерживают несколько функций с двумя аргументами. Полный список функций и операторов, поддерживающих трансляцию:

plus      +
      minus     -
      times     .*
      rdivide   ./
      ldivide   .\
      power     .^
      lt        <
      le        <=
      eq        ==
      gt        >
      ge        >=
      ne        !=  ~=
      and       &
      or        |
      atan2
      hypot
      max
      min
      mod
      rem
      xor

      +=  -=  .*=  ./=  .\=  .^=  &=  |=

Вот наглядный пример возможностей трансляции. Алгоритм Флойда — Уоршелла используется для вычисления длин кратчайших путей между каждой парой вершин графа. Наивная реализация для матрицы смежности графа порядка n может выглядеть так:

for k = 1:n
  for i = 1:n
    for j = 1:n
      dist(i,j) = min (dist(i,j), dist(i,k) + dist(k,j));
    endfor
  endfor
endfor

Если векторизовать внутренний цикл, код может выглядеть так:

for k = 1:n
  for i = 1:n
    dist(i,:) = min (dist(i,:), dist(i,k) + dist(k,:));
  endfor
endfor

При использовании трансляции в обоих направлениях код выглядит так:

for k = 1:n
  dist = min (dist, dist(:,k) + dist(k,:));
endfor

Относительное время выполнения трёх вариантов для графа со 100 вершинами составляет 7,3 секунды для наивного кода, 87 миллисекунд для частично векторизованного кода и 1,3 миллисекунды для кода с полной трансляцией. Для графа с 1000 вершинами векторизация занимает 11,7 секунды, а трансляция — всего 1,15 секунды. Поэтому для повышения производительности обычно стоит писать код с учётом семантики трансляции.

Однако не следует прибегать к трансляции, если достаточно более простой операции. Рассмотрим следующие действия с матрицами a и b:

c = sum (permute (a, [1, 3, 2]) .* permute (b, [3, 2, 1]), 3);

При поэлементном умножении эта операция транслирует две матрицы с переставленными измерениями относительно друг друга, чтобы получить массив большей размерности — трёхмерный массив, который затем суммируется вдоль третьего измерения. Если немного подумать, станет ясно, что эта операция эквивалентна обычному умножению матриц, c = a*b;, которое работает гораздо быстрее.

Примечание о терминологии: термин «трансляция» получил распространение благодаря численной среде Numpy для языка программирования Python. В других языках программирования и средах трансляция также может называться бинарным расширением единичных измерений (BSX в MATLAB; от этого термина происходит имя функции bsxfun), повторным использованием (язык программирования R), одной командой над множеством данных (SIMD) или репликацией.

• Трансляция и устаревший код

try
  c = a.*b;
catch
  c = a.*a;
end_try_catch

if (isequal (size (a), size (b)))
  c = a .* b;
else
  c = a .* a;
endif