Изменяет ли векторизация сложность?

#matlab #matrix #vectorization #complexity-theory

#matlab #матрица #векторизация #сложность -теория

Вопрос:

Я написал код в MATLAB со сложностью O (n ^ 3). Я удалил один из циклов и вместо этого использовал векторизованную форму. В результате время выполнения сократилось. Я понимаю, что в целом векторизация повышает производительность. В чем я не уверен, так это в том, что я предположил, что векторизация не изменяет сложность.

Я провел несколько экспериментов следующим образом:

Когда я увеличил размер ввода в 2 раза, время выполнения увеличилось примерно в 2,5 раза (я ожидал примерно в 8 раз).

Теперь я не уверен, действительно ли мое первоначальное предположение (то есть векторизация не изменяет сложность.). У кого-нибудь есть понимание?

Спасибо.

1. Это зависит от используемой вами функции. Например, использование такой функции, как bsxfun увеличивает скорость, в то время как она просто for-loop записывается как c / mex file . В таких случаях я не думаю, что векторизация кода изменяет сложность.

2. Спасибо за ваше понимание. Знаете ли вы, почему время выполнения не увеличивается пропорционально (при увеличении размера ввода)? Когда я использовал цикл for, он был близок к ожидаемому увеличению, но когда я векторизовал, он не был близок. Я использовал MATLAB. Я просто дал диапазон для индекса (а не для столбца) и удалил для loop.mathworks.com/help/matlab/matlab_prog/vectorization.html

3. @Crimson Что ж, при векторизованных подходах вы обрабатываете больше данных за определенный период времени, поэтому передача данных намного больше, На что может повлиять пропускная способность памяти и т. Д. Итак, я не думаю, что это будет линейный масштаб. Векторизация против производительности против памяти — уникальная игра. Однако я не слишком хорошо знаком с определениями сложности.

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

5. Я в основном предполагаю, поэтому только комментарий, но здесь идет. Я не думаю, что векторизация должна изменять сложность. Т.Е. Я бы подумал, что векторизованная версия O(n^3) кода также должна быть O(n^3) , но с гораздо меньшим префактором. Но вот в чем загвоздка: это всего лишь асимптотическое поведение (поэтому вам нужно очень большое n , чтобы четко видеть это), и в вашем коде обычно много пуха (накладные расходы с точки зрения вашей векторизации), который масштабируется по-разному. Итак, вам действительно нужны огромные n и масштабируемые на несколько порядков величины, чтобы сказать что-нибудь эмпирическое о сложности.

Ответ №1:

В самом общем виде я думаю, что разница на самом деле заключается в пропускной способности (латентности) и количестве операций (сложности). Если бы вы создали очень специализированный алгоритм ASIC для вас, вам пришлось бы выполнять n ^ 3 операции. Векторизируя, вы говорите, что некоторые из этих операций могут выполняться независимо друг от друга параллельно. Matlab и текущие процессоры более умны и могут выполнять определенные операции «параллельно», например, 64-битный процессор может выполнять 2-32-битные суммирования, 4-16-битные и т.д.

Подумайте о двух алгоритмах, как в O (n ^ 3), a, где каждая операция должна выполняться полностью независимой (вы можете векторизовать этот алгоритм), так и в другом, где они должны быть последовательными (вы не можете векторизовать его). Специальное оборудование для каждого из них потребует n ^ 3 операций. Однако, используя больше оборудования / элементов для a, вы можете завершить задачу всего за 1 такт, в то время как для b больше оборудования / элементов вам не поможет, и задача займет n ^ 3 такта.

Редактировать:

Некоторый код для иллюстрации скорости векторизации, хотя сложность (#operation) не увеличится

 clear variable;

Iterations = 100;
n = 2^20;
a = randi(100,[1,n]);
b = randi(100,[1,n]);

profile on;
for loop=1:Iterations
    % Full vector approach
    vector = a*b.';

    % Partial vector approach
    vector2 = sum(a.*b);

    % Direct mathematical approach
    serial = 0;
    for id=1:n
        serial = serial   a(id)*b(id);
    end
end
profile viewer;

теперь технически matlab имеет некоторые дополнительные накладные расходы на операцию, такие как проверка, имеет ли смысл операция и т.д., Что значительно замедляет цикл for. Но в целом это всего лишь пример, иллюстрирующий тенденцию.

1. с этим объяснением, если я правильно понял, сложность уменьшится, поскольку большая часть параллельной версии алгоритма имеет меньшую сложность.

2. Спасибо за ваш ответ. С вашим объяснением, если я правильно понял, сложность уменьшится (поскольку параллельная версия алгоритма обычно имеет меньшую сложность). В руководстве по векторизации я не видел объяснения о том, как сделать его параллельным.

3. Сложность в основном останется прежней, по-прежнему в O (n ^ 3), но, возможно, некоторые другие префакторы, как предложил @Andras. Что изменится, так это то, что некоторые операции будут выполняться параллельно, что сократит время получения ответа. Когда дело доходит до сложности, векторизация подразумевает параллельные операции. В общем случае «время» не обязательно указывает на сложность, а скорее на ввод. Особенно с MATLAB.

4. Спасибо за ответ. Я должен подробнее прочитать об этом. Я немного смущен, так как раньше я изучал параллельную версию для нескольких алгоритмов сортировки. В основном целью является повышение эффективности (а не времени), но конечная сложность (вычисление связь) в конце уменьшится (из того, что я запомнил).

5. Я понимаю, вы можете подумать о быстрой сортировке или сортировке слиянием . Которые естественным образом разделяют проблему и могут быть легко векторизованы / распараллелены, но они также разделяют проблему на меньшую проблему и избавляют от нее сложность. Это не относится к векторизации / распараллеливанию в целом, я добавляю некоторый код, чтобы проиллюстрировать это в ответе выше.