Форум программистов, компьютерный форум, киберфорум
Наши страницы
Зосима
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 1.

Матричная магия: часть 1 - Суммирование в мгновение ока!

Запись от Зосима размещена 01.02.2013 в 18:27

Очень часто возникают задачи посчитать сумму ряда.
В традиционных языках программирования для этого используются циклы, в матлабе же есть замечательная встроенная функция sum, которая одним махом находит сумму элементов массива или столбцов матрицы!
Но я расскажу еще об одном способе: матричном заклинании которое считает сумму быстрее первых двух способов!
Вспомним правило матричного умножения: элемент новой матрицы равен сумме произведений строки первой матрицы на столбец второй.

Теперь, если допустить, что первая матрица - вектор-строка, а второй вектор-столбец, то результат будет числом, равным сумме поэлементных произведений! В этом вся соль!

Главное, чтобы длины векторов совпадали и соблюдалась ориентация!!!

Так, для вычисления суммы элементов вектора-строки x достаточно матрично умножить его на вектор-столбец из единичек! А так как матлаб заточен и оптимизирован под матричные операции, такой способ работает очень быстро!
Для сравнения различных алгоритмов суммирования в матлаб я набросал простенькую программку:
Программа MATLAB
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
clear; clc;
 
n = 60; % кол-во точек
% длины масивов
N = fix(logspace(1,7,n));
T = zeros(n,3);
for k = 1:length(N)
    % формируем масивы
    x = 1:N(k);
    o = ones(1,N(k));
    
    tic
    s1=sum(x); % суммирование встроенной ф-цией
    t_sum = toc;
    
    tic
    s2=x*o'; % суммирование матричным умножением
    t_matr = toc;
    
    tic
    s3=0;
    for i=1:N(k)
        s3=s3+x(i); % суммирование в цикле
    end
    t_loop = toc;
    % сохраняем длительности
    T(k,:) = [t_sum, t_matr, t_loop];
end
% рисуем логарифм. график и подписываем
loglog(N,T)
ylabel('Время вычисления, t, с')
xlabel('Длинна массива, N')
legend('Ф-ция sum','Матричное умножение','Суммирование в цикле','location','northwest')

Она генерирует произвольные массивы х с длинами от 101 до 107, считает сумму тремя различными способами, засекает время расчета каждого, сохраняет результат и рисует график.
Получаем такую зависимость:

Нажмите на изображение для увеличения
Название: 0p.png
Просмотров: 866
Размер:	7.1 Кб
ID:	1694

Отсюда можно сделать такие выводы:
- суммирование в цикле сообразно использовать, если длинна массива меньше ~200. Однако, в данном случае, в цикле нет доп. вычислений и условий, которые есть в реальном задании, поэтому от циклов лучше по возможности уходить
- матричное умножение считается быстрее встроенной ф-ции, а при длине массива болше ~105 разница между ними становится значительной. Поэтому для массивов больших размерностей предпочтительней использовать матричное умножение

Ну и на закуску приведу пример вычисления рядов матричным умножением.
Рассчет экспоненты:
Matlab M
1
2
3
4
5
i = 0:19; % 20 членов ряда
x = 2;% значение аргумента
s = x.^(i) * (1./factorial(i))' % сумма произведений
y = exp(x) % точный результат для сравнения
d = abs(s-y) % разница
Получаем:
Matlab M
1
2
3
4
5
6
7
8
s =
    7.3891
 
y =
    7.3891
 
d =
  4.7606e-013
Замечу, что конструкция вида a:h:b возвращает вектор-строку чисел от а до b с шагом h, поэтому второй вектор (1./factorial(i)) тоже будет строкой, поэтому мы его транспонируем (...)'

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

Список тем, где был применен данный метод:
http://www.cyberforum.ru/post3697347.html и http://www.cyberforum.ru/post3699099.html
http://www.cyberforum.ru/post3811787.html (см. под кат)

В следующей части расскажу, как из двух векторов любой длины, при помощи матричной магии , создать матрицу и как это можно применить на практике.
Размещено в Без категории
Просмотров 2786 Комментарии 18
Всего комментариев 18
Комментарии
  1. Старый комментарий
    Аватар для R2D2
    Спасибо за курс магии)) Решал задачку здесь предложным тобою методом, но все ровно находятся умельцы по оптимизации кода (смотри карту решений ).
    Запись от R2D2 размещена 03.04.2013 в 11:20 R2D2 вне форума
  2. Старый комментарий
    И как же эта sum реализована, если не теми же циклами?
    Запись от размещена 03.04.2013 в 12:24
  3. Старый комментарий
    Аватар для Зосима
    Тарас, как именно она реализована - это коммерческая тайна компании MathWorks Спинным мозгом чувствую, что через тоже матричное умножение и явно не через циклы, т.к. разница в скорости весьма существенна.
    Запись от Зосима размещена 03.04.2013 в 18:16 Зосима вне форума
  4. Старый комментарий
    Не через цикл как раз будет во-первых медленнее, а во-вторых количество слагаемых будет фиксировано, а сложение через матричное умножение вообще не возможно математически, скорость здесь вообще не причём. Просто можно оптимизировать сам цикл. Например, при массиврованном параллелизме суммирование 1024-х чисел выполняется за 10 шагов цикла: на первом шаге одновременно за один проход тела цикла складывается 512 пар чисел, в каждой получается одна частичная сумма, на втором шаге одновременно за один проход тела цикла складывается складывается 256 пар частичных сумм - результатов первого шага и получается 256 частичных сумм, на третьем шаге одновременно за один проход тела цикла складывается складывается 128 пар частичных сумм - результатов второго шага и получается 128 частичных сумм, на четвёртом шаге одновременно за один проход тела цикла складывается складывается 64 пар частичных сумм - результатов третьего шага и получается 64 частичных сумм, на пятом шаге одновременно за один проход тела цикла складывается складывается 32 пары частичных сумм - результатов четвёртого шага и получается 32 частичных сумм, на шестом шаге одновременно за один проход тела цикла складывается складывается 16 пар частичных сумм - результатов пятого шага и получается 16 частичных сумм, на седьмом шаге одновременно за один проход тела цикла складывается складывается 8 пар частичных сумм - результатов шестого шага и получается 8 частичных сумм, на восьмом шаге одновременно за один проход тела цикла складывается складывается 4 пары частичных сумм - результатов седьмого шага и получается 4 частичных сумм, на девятом шаге одновременно за один проход тела цикла складывается складывается 2 пары частичных сумм - результатов восьмого шага и получается 2 частичных сумм, на десятом шаге складываются последние две частичные суммы и того 10 шагов цикла вместо 1024-х, выигрыш более, чем стакрантый. При 1048576-ти слагаемых достаточно 20-ти шагов, выигрыш в примерно в 52 тысячи раз, при 1073741824-х слагаемых достаточно 30-ти шагов, выигрыш более, чем 35 миллионов раз. И это я ещё не рассматриваю переполнение кеша, интерпретацию и тому подобную фигню, способную уронить скорость цикла во многие квадриллионы раз. Я сам автор быстрого решения матричного уравнения свыше двухстот миллионов элементов. Теоретическая оценка времени исполнения неоптимизированной версии 6 393 года, оптимизированная реально уложилась в 40 минут, деля время с дополнительной "работой".
    Запись от размещена 03.04.2013 в 19:18
  5. Старый комментарий
    Да, кстати, нециклическое сложение матриц вообще перестанет влезать в машину задолго до достижения размера в 16900 элементов, для которого оптимизация ещё не имеет смысла, так как и решение системы "в лоб" выполняется в долю секунды.
    Запись от размещена 03.04.2013 в 19:20
    Обновил(-а) taras atavin 03.04.2013 в 19:22
  6. Старый комментарий
    Умножение же матриц вообще не реализуемо ни как, кроме цикла.
    Запись от размещена 03.04.2013 в 19:23
  7. Старый комментарий
    Аватар для Зосима
    Еще раз подчеркну, что мне достоверно не известно как именно разработчики реалиовали функцию sum и матричное умножение
    Существуют быстрые алгоритмы перемножения матриц, которые вероятно и были использованы.
    Смысл статьи не в "порицании" циклов, а в ознакомлении с несправедливо пренебрегаемыми матричными действиями в MATLAB
    Политика создателей программы направлена на уход от обычных циклов без премудростей (хотя не всегда можно обойтись без них), т.к. они увеличивают время вычислений что мы и видим на простом примере суммирования элементов вектора.

    Кстать, интересный алгоритм! я вот только не совсем "догнал" программную реализацию: подумал, что частичные суммы на каждом шагу так же считаются в цикле и получаем двойной цикл: так для 1024 элементов внешний будет иметь 10 шагов, а внутренний 512, 256, 128... Или я не правильно понял?
    Запись от Зосима размещена 04.04.2013 в 07:06 Зосима вне форума
  8. Старый комментарий
    Явные циклы стабильно хуже тех, на которых реализованы оптимизированные функции, но не всегда есть возможность обращаться к матлабу, часто матричные операции приходится выполнять глубоко внутри другой программы и тогда надо идти следом за авторами самого матлаба, а юзать его.
    Запись от размещена 04.04.2013 в 07:33
  9. Старый комментарий
    [QUOTE=Зосима;bt6692]Кстать, интересный алгоритм! я вот только не совсем "догнал" программную реализацию: подумал, что частичные суммы на каждом шагу так же считаются в цикле и получаем двойной цикл: так для 1024 элементов внешний будет иметь 10 шагов, а внутренний 512, 256, 128... Или я не правильно понял? :scratch:[/QUOTE]Нет. Распараллеливание выполняется иными средствами, так что ни какого внутреннего цикла.
    Запись от размещена 04.04.2013 в 07:36
  10. Старый комментарий
    На интерпретируемых языках явные циклы гарантированно хуже невных циклов внути оптимизированных встроенных функций, на компилируемых не оптимизированные циклы стабильно хуже тех, на которых построены оптимизированные функции. Но часто нет возможности обращаться к матлабу, так как матричные операции должны выполняться глубоко внутри другой программы и остаётся идти следом за авторами матлаба, а не юзать его.
    Запись от размещена 04.04.2013 в 07:39
  11. Старый комментарий
    Аватар для Зосима
    Цитата:
    Сообщение от taras atavin Просмотреть комментарий
    Нет. Распараллеливание выполняется иными средствами.
    А как, если не секрет?
    Хочу запрограммировать и сравнить.
    Запись от Зосима размещена 04.04.2013 в 10:56 Зосима вне форума
  12. Старый комментарий
    Одной программной реализации здесь мало, нужен параллельный процессор. Такой процессор поддерживает нечто подобное циклу, но внутри элементарной операции и развёрнутое не по времени последовательными шагами, а по сумматорам параллельными ветвями.
    Запись от размещена 04.04.2013 в 11:38
  13. Старый комментарий
    И массированный параллелизм пока вообще не реализован, реализован только простой. Разница между ними количественная: MMX, например, может аналогично выполнить не более 3-х шагов, а потом ему не хватит ветвей, 3 шага - это до 8-ми слагаемых:
    s[0][0]=a[0]+a[1], s[0][1]=a[2]+a[3], s[0][2]=a[4]+a[5], s[0][3]=a[6]+a[7];
    s[1][0]=s[0][0]+s[0][1], s[1][1]=s[0][2]+s[0][3];
    s[2][0]=s[1][0]+s[1][1].
    Запись от размещена 04.04.2013 в 11:40
    Обновил(-а) taras atavin 04.04.2013 в 11:44
  14. Старый комментарий
    Выигрыш всего в 2,667 раза.
    Запись от размещена 04.04.2013 в 11:45
  15. Старый комментарий
    Ну можно ещё несколько ядер/процессоров попробовать использовать.
    Запись от размещена 04.04.2013 в 11:47
  16. Старый комментарий
    Но в моём посте массированный параллелизм - только пример, я выбрал его просто потому, что именно эта оптимизация может быть максимально просто описана и при этом максимально универсальна.
    Запись от размещена 04.04.2013 в 11:50
  17. Старый комментарий
    Аватар для Зосима
    Ясненько, тут скорее паяльник нужен для домохозяйки считающей минимум расстояний между пылинками на разных кадрах, например, этот метод не подходит
    Запись от Зосима размещена 04.04.2013 в 11:52 Зосима вне форума
  18. Старый комментарий
    Массированный параллелизм ожидается к пятому поколению.
    Запись от размещена 04.04.2013 в 13:14
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru