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

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

Показов 10130 Комментарии 18

Метки math, matlab, вектор, математика, матрица

Очень часто возникают задачи посчитать сумму ряда.
В традиционных языках программирования для этого используются циклы, в матлабе же есть замечательная встроенная функция 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')

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

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

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

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

Ну и на закуску приведу пример вычисления рядов матричным умножением.
Рассчет экспоненты:

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)) тоже будет строкой, поэтому мы его транспонируем (...)'

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

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

В следующей части расскажу, как из двух векторов любой длины, при помощи матричной магии

, создать матрицу и как это можно применить на практике.

Метки math, matlab, вектор, математика, матрица

Размещено в Без категории

« Матричная магия: вступление Главная страница Электрон быстрее дырки, почему? »

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 18

Комментарии

	Спасибо за курс магии)) Решал задачку здесь предложным тобою методом, но все ровно находятся умельцы по оптимизации кода (смотри карту решений ).
	Запись от R2D2 размещена 03.04.2013 в 11:20

	И как же эта sum реализована, если не теми же циклами?
	Запись от размещена 03.04.2013 в 12:24

	Тарас, как именно она реализована - это коммерческая тайна компании MathWorks Спинным мозгом чувствую, что через тоже матричное умножение и явно не через циклы, т.к. разница в скорости весьма существенна.
	Запись от Зосима размещена 03.04.2013 в 18:16

Не через цикл как раз будет во-первых медленнее, а во-вторых количество слагаемых будет фиксировано, а сложение через матричное умножение вообще не возможно математически, скорость здесь вообще не причём. Просто можно оптимизировать сам цикл. Например, при массиврованном параллелизме суммирование 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

Да, кстати, нециклическое сложение матриц вообще перестанет влезать в машину задолго до достижения размера в 16900 элементов, для которого оптимизация ещё не имеет смысла, так как и решение системы "в лоб" выполняется в долю секунды.

Запись от размещена 03.04.2013 в 19:20

	Умножение же матриц вообще не реализуемо ни как, кроме цикла.
	Запись от размещена 03.04.2013 в 19:23

Еще раз подчеркну, что мне достоверно не известно как именно разработчики реалиовали функцию sum и матричное умножение

Существуют быстрые алгоритмы перемножения матриц, которые вероятно и были использованы.
Смысл статьи не в "порицании" циклов, а в ознакомлении с несправедливо пренебрегаемыми матричными действиями в MATLAB

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

что мы и видим на простом примере суммирования элементов вектора.

Кстать, интересный алгоритм! я вот только не совсем "догнал" программную реализацию: подумал, что частичные суммы на каждом шагу так же считаются в цикле и получаем двойной цикл: так для 1024 элементов внешний будет иметь 10 шагов, а внутренний 512, 256, 128... Или я не правильно понял?

Запись от Зосима размещена 04.04.2013 в 07:06 Зосима вне форума

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

Запись от размещена 04.04.2013 в 07:33

[QUOTE=Зосима;bt6692]Кстать, интересный алгоритм! я вот только не совсем "догнал" программную реализацию: подумал, что частичные суммы на каждом шагу так же считаются в цикле и получаем двойной цикл: так для 1024 элементов внешний будет иметь 10 шагов, а внутренний 512, 256, 128... Или я не правильно понял? :scratch:[/QUOTE]Нет. Распараллеливание выполняется иными средствами, так что ни какого внутреннего цикла.

Запись от размещена 04.04.2013 в 07:36

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

Запись от размещена 04.04.2013 в 07:39

Сообщение от taras atavin

Нет. Распараллеливание выполняется иными средствами.

А как, если не секрет?

Хочу запрограммировать и сравнить.

Запись от Зосима размещена 04.04.2013 в 10:56 Зосима вне форума

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

Запись от размещена 04.04.2013 в 11:38

И массированный параллелизм пока вообще не реализован, реализован только простой. Разница между ними количественная: 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

	Выигрыш всего в 2,667 раза.
	Запись от размещена 04.04.2013 в 11:45

	Ну можно ещё несколько ядер/процессоров попробовать использовать.
	Запись от размещена 04.04.2013 в 11:47

	Но в моём посте массированный параллелизм - только пример, я выбрал его просто потому, что именно эта оптимизация может быть максимально просто описана и при этом максимально универсальна.
	Запись от размещена 04.04.2013 в 11:50

	Ясненько, тут скорее паяльник нужен для домохозяйки считающей минимум расстояний между пылинками на разных кадрах, например, этот метод не подходит
	Запись от Зосима размещена 04.04.2013 в 11:52

	Массированный параллелизм ожидается к пятому поколению.
	Запись от размещена 04.04.2013 в 13:14

Новые блоги и статьи Все статьи Все блоги /
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .

Сообщение форума

Отменить изменения