Ответ 1

Интуиция

Как упоминал Даниил в своем ответе , линейный индекс занимает больше места в ОЗУ, а индексы намного меньше.

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

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

Претензии

• Линейное индексирование выполняется быстрее
• ... пока общее число индексов одинаково

Задержки

Из таймингов мы видим прямое подтверждение первой заявки, и мы можем сделать второе с некоторым дополнительным тестированием (ниже).

LOOPED
      subs assignment: 0.2878s
    linear assignment: 0.0812s

VECTORIZED
      subs assignment: 0.0302s
    linear assignment: 0.0862s

Первое требование

Мы можем проверить его с помощью циклов. Число операций subref - это тот же, но линейный индекс указывает непосредственно на интересующий элемент, а индексы внутри должны быть преобразованы.

Интересующие функции:

function B = subscriptedIndexing(A,row,col)
n = numel(row);
B = zeros(n);
for r = 1:n
    for c = 1:n
        B(r,c) = A(row(r),col(c));
    end
end
end

function B = linearIndexing(A,index)
B = zeros(size(index));
for ii = 1:numel(index)
    B(ii) = A(index(ii));
end
end

Второе требование

Это утверждение является выводом из наблюдаемой разницы в скорости при использовании векторизованного подхода.

Во-первых, векторный подход (в отличие от зацикленного) ускоряет индексированное присвоение, тогда как линейная индексация немного медленнее (вероятно, не статистически значима).

Во-вторых, единственная разница в двух методах индексации исходит из размера индексов/индексов. Мы хотим выделить это как единственную возможную причину разницы в таймингах. Другим крупным игроком может быть оптимизация JIT.

Функции тестирования:

function B = subscriptedIndexingVect(A,row,col)
n = numel(row);
B = zeros(n);
B = A(row,col);
end

function B = linearIndexingVect(A,index)
B = zeros(size(index));
B = A(index);
end

ПРИМЕЧАНИЕ. Я сохраняю избыточное предварительное распределение B, чтобы совпадающие векторизованные и циклические подходы. Другими словами, различия в таймингах должны исходить только от индексации и внутренней реализации циклов.

Все тесты выполняются с помощью:

function testFun(N)
A             = magic(N);
row           = 1:2:N;
col           = 1:2:N;
[ind_x,ind_y] = ndgrid(row,col);
index         = sub2ind(size(A),ind_x,ind_y);

% isequal(linearIndexing(A,index), subscriptedIndexing(A,row,col))
% isequal(linearIndexingVect(A,index), subscriptedIndexingVect(A,row,col))

fprintf('<strong>LOOPED</strong>\n')
fprintf('      subs assignment: %.4fs\n',  timeit(@()subscriptedIndexing(A,row,col)))
fprintf('    linear assignment: %.4fs\n\n',timeit(@()linearIndexing(A,index)))
fprintf('<strong>VECTORIZED</strong>\n')
fprintf('      subs assignment: %.4fs\n',  timeit(@()subscriptedIndexingVect(A,row,col)))
fprintf('    linear assignment: %.4fs\n',  timeit(@()linearIndexingVect(A,index)))
end

Включение/выключение включения/выключения JIT имеет эффект НЕТ:

feature accel off
testFun(5e3)
...

VECTORIZED
      subs assignment: 0.0303s
    linear assignment: 0.0873s

feature accel on
testFun(5e3)
...

VECTORIZED
      subs assignment: 0.0303s
    linear assignment: 0.0871s

Этот исключает, что индексированное присваивание превосходит скорость, исходя из оптимизации JIT, которая оставляет нам единственную правдоподобную причину, количество обращений к RAM. Верно, что конечная матрица имеет одинаковое количество элементов. Тем не менее, линейное задание должно извлекать все элементы индекса для извлечения чисел.

Настройка

Протестировано на Win7 64 с MATLAB R2015b. Предыдущие версии Matlab предоставят разные результаты из-за недавних изменений в механизм выполнения Matlab

Фактически, включение JIT в Matlab R2014a влияет на тайминги, но только для циклов (ожидаемый результат):

feature accel off
testFun(5e3)

LOOPED
      subs assignment: 7.8915s
    linear assignment: 6.4418s

VECTORIZED
      subs assignment: 0.0295s
    linear assignment: 0.0878s

Это еще раз подтверждает, что разница в таймингах между линейным и сибсриптовым назначением должна исходить из количества обращений к ОЗУ, поскольку JIT не играет роли в векторизованном подходе.

Ответ 2

Меня не удивляет, что индексирование индексов намного быстрее. Если вы посмотрите на свои входные данные, в этом случае индекс намного меньше. Для индекса индексирования индекса у вас есть 512 элементов, тогда как для случая линейного индексирования у вас есть 65536 элементов.

Когда вы применяете свой пример к вектору вместо этого, вы заметите, что между обоими методами нет разницы.

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

it = 400; im = zeros(512*512,1);
x = 1:2:size(im,1);
y = 1:2:size(im,2);
%// linear indexing
[ind_x,ind_y] = ndgrid(x,y);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc 

%// subscript indexing


tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc 

Ответ 3

Очень хороший вопрос. Прямо сейчас, я не знаю правильного ответа, однако, вы можете анализировать поведение. Сохраните первый toc в t1, а второй - в t2. В конце вычислите t1/t2. Вы узнаете, что изменение количества итераций или размер вашей матрицы (почти) не изменят коэффициент. Я предлагаю:

• Количество итераций только улучшает качество tictoc. (Очевидно?)
• Размер матрицы не имеет прироста, т.е. в синтаксисе должна быть временная задержка.

Я полагаю, что существует просто внутренняя проверка или преобразование из линейного индекса в индексирование индексов, т.е. внутреннее добавление (операция), которое вы выполняете, точно такое же. Кажется более естественным использовать индексирование индексов вместо линейной индексации, поэтому, возможно, mathworks просто оптимизировал первый.

UPDATE: Вы также можете просто получить доступ к элементу в своей матрице, вы увидите, что использование индекса индекса быстрее, чем использование линейного индекса. Это поддерживает теорию, что происходит медленное преобразование, сделанное внутренне от линейного до нижнего индекса.

Ответ 4

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: На данный момент у меня нет лицензии MATLAB, поэтому код, который я предоставляю ниже, по общему признанию не проверен. Однако, если кто-то решит протестировать, пожалуйста, прокомментируйте этот ответ соответственно.

В зависимости от вашего выпуска MATLAB (используете ли вы R2015b?), возможно, вы не заплатили полную первоначальную стоимость предварительного распределения при вызове "нулей". Существует вероятность того, что вы платите за выделение при первом получении/наборе im, что вызывает дополнительные, но скрытые служебные данные при первом доступе к значениям внутри im.

Смотрите: http://undocumentedmatlab.com/blog/preallocation-performance

В качестве начального теста я предлагаю переключить порядок, в котором вы профилируете код:

N = 512; it = 400; im = zeros(N);

%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc %// What the cost now?

%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc %// What the cost now?

Для более точного определения профиля индекса и линейного индексирования я предлагаю один из двух возможных способов:

• Удостоверьтесь, что вы несете затраты на распределение по обоим методам, создав две отдельные im-матрицы: im1 и im2, изначально заданные нулями (N) и использующие каждую матрицу для отдельного метода индексирования.
• Запустите полный get/set для каждого элемента im до фактического профилирования между индексом и линейным индексированием.

Способ 1:

N = 512; it = 400; im1 = zeros(N); im2 = zeros(N);

%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im1(x,y) = im1(x,y) + 1;
end
toc %// What the cost now?

%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im2),ind_x,ind_y);

tic
for i=1:it
    im2(index) = im2(index) + 1;
end
toc %// What the cost now?

Способ 2:

N = 512; it = 400; im = zeros(N);

%// Run a full get/set on each element to force allocation
tic
for i=1:N^2
    im(i) = im(i) +1;
end
toc 


%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc %// What the cost now?

%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc %// What the cost now?

У меня есть вторая гипотеза, которая заключается в том, что вы несете дополнительные дополнительные накладные расходы, когда явным образом объявляю каждый доступный элемент, и если у вас есть MATLAB, выведите эти элементы для себя. excasa ссылка "дублировать пост" (не совсем дубликат по моему скромному мнению) имеет такое же общее понимание, но использует разные данные, чтобы прийти к такому выводу, Я не буду писать примеры этого здесь, но в основном, создавая линейный гигантский массив index по сравнению с меньшими индексами индексов x и y дает MATLAB меньше возможностей для внутренних оптимизаций. Я не знаю, что внутри MATLAB выполнит эти конкретные оптимизации, но, возможно, они происходят из черной магии, которую вы можете знать как MATLAB JIT/LXE, Если вы действительно хотите проверить, является ли JIT виновником (и работает в 2014b или ранее), вы можете попробовать отключить его, а затем запустить код выше.

Существует несколько способов отключения JIT:

• Используйте методы недокументированных функций.
• Скопируйте/вставьте команды в командную строку, а не запускайте их прямо из редактора script.

К сожалению, я не знаю, как включить LXE в R2015a и позже, и попытаться диагностировать, является ли LXE виновником, может быть, бит битвы. Если это то место, где вы застряли, возможно, вы сможете еще подробнее изучить техническую поддержку MathWorks или MathWorks Central. Вы можете быть удивлены, если найдете некоторых поразительных экспертов из любого источника.