Резервирование памяти.
Практически любая алгоритм решения прикладных задач (оптимизация, обращение и т. д.) включает математическую операцию суммирования. А суммирование, в свою очередь, реализуется циклом. Например, задача нахождения функции интеграла методом прямоугольников реализуется формулой:
Реализация этой функции в среде MATLAB может быть такой:
function [t, J] = intJ(fun, dt, T)
% fun – интегрируемая функция
% dt – шаг интегрирования
% T – предел интегрирования
n = T/dt;
J(1) = 0;
t(1) = 0;
for i = 2:n
t(i) = dt*(i-1);
J(i) = J(i-1) + dt*feval(fun, t(i));
end;
» tic; [t, x] = intJ('sin', 0.1, 500); toc
elapsed_time =
7.6200
Этот код не является оптимальным по скорости выполнения. Действительно, если вы знакомы с программированием на C++ или Java, то вам известно, что для инициализации массива обязательно нужно задать его размер. Это необходимо для резервирования области памяти. Так же и MATLAB, для каждой инициализируемой переменной (массива) выделяет область памяти. Поэтому, когда в программе увеличивают размер массива, MATLAB сначала инициализирует новый массив указанного размера и выделяет память для него, копирует туда значения элементов прежнего массива и новые значения, и возвращает указатель на эту область.
Таким образом, осуществляется большой объем лишних операций, которые легко избежать путём резервирования памяти. Для этого мы сразу выделяем нужный объём памяти, заполняя массив, например, нулями:
J = zeros(1, n); % или вот так: J(1:n) = 0;
t = J;
Добавьте эти две строчки кода после строки ‘n = T/dt;’, и выполните функцию:
» tic; [t, x] = intJ('sin', 0.1, 500); toc
elapsed_time =
0.6500
Таким образом, мы получили существенный прирост в скорости, причём коэффициент прироста (kt=7.62/0.65=11.72) сильно возрастает с увеличением числа элементов массива.
Матричные операции.
Часто, можно вообще отказаться от циклов. Как было отмечено, цикл реализует операцию суммирования, которая в свою очередь с успехом может быть заменена операцией перемножения матриц. Тогда данная операция может быть представлена в виде:
Таким образом перемножение вектора Aна транспонированный векторBдаст нам результатS. Аналогичные выкладки справедливы для двойной суммы. Такая замена даёт очень большой выигрыш, и может быть использована во многих случаях. Рассмотрим пример вычисления интеграла методом прямоугольников:
dt=0.1;
t=0:dt:10;
N=length(t);
f=exp(-0.1*t);
% Использование цикла для
% реализации формылы суммирования
s1=0;
for i=1:N
s1=s1+dt*f(i);
end;
s1
% Использование умножения матриц
% для реализации формылы суммирования
s2=dt*ones(1,N)*f';
s2
При вложенности циклов, большом объёме вычислений данный приём даёт значительный выигрыш (в данном примере скорость для второго варианта возрастает в 60 раз).
Пример.
Рассмотрим пример, ярко иллюстрирующий возможности по оптимизации кода. Ниже приведены две реализации одной и той же функции. Сразу отмечу, что оптимизированная реализация функции для заданного входного параметра l = 100даёт выигрыш в скорости вычислений чуть меньше5000 (пяти тысяч) раз! То есть программа, использующая эту функцию, для оптимизированного варианта решает задачу за4,5 секунды, а не оптимизированный вариант решил бы её примерно15,4 часа!