ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Насчет производительности
83 сообщений из 83, показаны все 4 страниц
  все  
Насчет производительности
    #39212574
Dimmf28
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimmf28
Участник
Есть такая задача, умножить одну матрицу на другую , делаю я эту в БД занимает оно 24 часа, думаю если вот перемножать матрицы на С++,а не SQL даст ли оно выигрыш в производительности, в каждой матрице где то 500 тысяч записей ну и 5 столбиков?
...
Рейтинг: 0 / 0
11.04.2016, 14:36
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212588
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
А разве неквадратные матрицы способны перемножаться?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
11.04.2016, 14:42
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212591
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dimmf28,

ты точно матрицы умножаешь? Или другую операцию над ними делаешь?
...
Рейтинг: 0 / 0
11.04.2016, 14:43
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212593
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dimitry SibiryakovА разве неквадратные матрицы способны перемножаться?..
да.
одна NxM, другая MxN
...
Рейтинг: 0 / 0
11.04.2016, 14:44
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212599
Dimmf28
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimmf28
Участник
Изопропил,

ну да матрицы просто они в виде табличек у меня
...
Рейтинг: 0 / 0
11.04.2016, 14:48
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212600
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Тогда уж NxM на MxK
...
Рейтинг: 0 / 0
11.04.2016, 14:48
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212608
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
А по теме - вытянуть матрицы да перемножить самому всяко быстрее выйдет чем чисто через sql. Возможное исключение - какое-нибудь нативное расширение на сервере для таких задач, но в общем случае о таком лучше даже не думать.
...
Рейтинг: 0 / 0
11.04.2016, 14:52
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212611
Dimmf28
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimmf28
Участник
wst,

то есть в с++ это быстрей будет получаться?
...
Рейтинг: 0 / 0
11.04.2016, 14:53
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212621
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dimmf28wst,

то есть в с++ это быстрей будет получаться?
да.
...
Рейтинг: 0 / 0
11.04.2016, 14:58
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212651
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Изопропилда.
Сильно зависит от кривизны рук перемножающего. Если он их в БД 24 часа перемножает...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
11.04.2016, 15:08
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212690
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dimitry SibiryakovИзопропилда.
Сильно зависит от кривизны рук перемножающего. Если он их в БД 24 часа перемножает...
теперь не уверен....
...
Рейтинг: 0 / 0
11.04.2016, 15:20
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212777
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
По-любому в БД такое делать точно нельзя. Даже не по соображениям производительности.
...
Рейтинг: 0 / 0
11.04.2016, 16:07
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212808
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
MasterZivПо-любому в БД такое делать точно нельзя.
почему?
...
Рейтинг: 0 / 0
11.04.2016, 16:22
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212826
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Изопропилпочему?
Наверное, Зив считает, что СУБД плохо справляются с перемножением и сложением множеств...

[src=SQL]select a.x,b.y,sum(a.value*b.value) from a join b on a.y=b.x group by 1,2[/src]
Как-то так по-моему...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
11.04.2016, 16:41
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212853
Dimmf28
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimmf28
Участник
Dimitry Sibiryakov,

ага вот так вот почти я и делал
...
Рейтинг: 0 / 0
11.04.2016, 17:01
| Ответить | Цитировать | Написать  
Насчет производительности
    #39212930
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimmf28ага вот так вот почти я и делал
так как Сибиряков написал должно работать секунду, а не сутки. Покажи свое "почти так", т.е. текст запроса.
...
Рейтинг: 0 / 0
11.04.2016, 18:12
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213052
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Dima Tтак как Сибиряков написал должно работать секунду, а не сутки.

а может он всё-таки каждую из 500к умножает на 500к
...
Рейтинг: 0 / 0
11.04.2016, 21:21
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213055
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
кстати, вот
самый лучший алгоритм на данный момент: O(n2.3727)
точно секунда?
...
Рейтинг: 0 / 0
11.04.2016, 21:25
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213091
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Изопропил,
потому что мир перевернется и наши потомки будут смеяться нам нами, а предки будут плакать в могилах и спрашивать : "за что же мы боролись?"
...
Рейтинг: 0 / 0
11.04.2016, 22:41
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213112
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dimmf28Есть такая задача, умножить одну матрицу на другую , делаю я эту в БД занимает оно 24 часа, думаю если вот перемножать матрицы на С++,а не SQL даст ли оно выигрыш в производительности, в каждой матрице где то 500 тысяч записей ну и 5 столбиков?
Скорее всего ты - большой выдумщик и фантазер.

Написать код который быстро считает на С++ это означает что нужно предварительно
ПОДГОТОВИТЬ данные для процессинга. Тоесть расположить в памяти строки 1-й
матрицы и столбцы второй в таком порядке чтобы они считывались последовательно,
были компактны были friendly для кешей L1/L2.

А теперь самое интересное. Тебя интересует КАКОЕ время. Время умножения?
Или время ПОДГОТОВКИ + время умножения?

Не спеши с ответом. Подумай. Это бесконечной длины боян который я всегда
спрашиваю у любителей сортировать массивы целых чисел длиной 4Гб.
...
Рейтинг: 0 / 0
12.04.2016, 00:04
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213114
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
mayton,

2x500000x5 float - это 20 мегабайт - слёзы.

преждевременная оптимизация, как обычно, не нужна
...
Рейтинг: 0 / 0
12.04.2016, 00:09
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213121
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Изопропил, точно-точно не нужна?

А может быть 5xfloat расширить до 8x ?
...
Рейтинг: 0 / 0
12.04.2016, 00:56
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213125
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
mayton,

точно не нужна.
достаточно хранить в памяти вторую матрицу транспонированной
...
Рейтинг: 0 / 0
12.04.2016, 01:04
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213129
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Изопропилmayton,

точно не нужна.
достаточно хранить в памяти вторую матрицу транспонированной
Загадками говоришь.
...
Рейтинг: 0 / 0
12.04.2016, 01:08
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213141
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
tip78кстати, вот
самый лучший алгоритм на данный момент: O(n2.3727)
точно секунда?

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

Пусть у нас есть две прямоугольных матрицы xy и yz. Тогда, асимптотика поиска матрицы r=xy mpl yz составит O(xyz). Алгоритм будет примерно такой:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
//предварительная инициализации элементов  матрицы r нулями
for(int i=0;i<x;++i){
   for(int j=0;j<y;++j){
      for(int k=0;k<z;++k){
         r[i][j]+=a[i][k]*b[k][j];
}
}
}



может что-то с индексами напутал, Dimmf28 проверьте самостоятельно. У меня нет времени(код набирал тут)

Таким образом в вашем случае необходимо либо 0,125*10^13, либо 0,125*10^8 операций (поскольку операция умножения в пространстве матриц некоммутативна). Думаю что за 30 минут, в крайнем случае за 60 минут, максимальное из этих двух значений число операций должно быть выполнено на не самой мощной вычислительной машине
...
Рейтинг: 0 / 0
12.04.2016, 02:21
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213214
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
дожили - матрицы умножать разучились
...
Рейтинг: 0 / 0
12.04.2016, 09:23
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213234
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Изопропил, тыб не вбрасывал - а код написал. Тут - каждый философ.

P.S. Show me your ....en code!
...
Рейтинг: 0 / 0
12.04.2016, 09:45
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213244
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
SashaMercurytip78кстати, вот
самый лучший алгоритм на данный момент: O(n2.3727)
точно секунда?

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

Пусть у нас есть две прямоугольных матрицы xy и yz . Тогда, асимптотика поиска матрицы r=xy mpl yz составит O(xyz).

там такие и обсуждаются
...
Рейтинг: 0 / 0
12.04.2016, 09:54
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213257
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
tip78SSпропущено...


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

Пусть у нас есть две прямоугольных матрицы xy и yz . Тогда, асимптотика поиска матрицы r=xy mpl yz составит O(xyz).

там такие и обсуждаются
Что в таком случае значит n ?
...
Рейтинг: 0 / 0
12.04.2016, 10:02
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213269
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
maytonИзопропилmayton,

точно не нужна.
достаточно хранить в памяти вторую матрицу транспонированной
Загадками говоришь.

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

если матрицы хранятся по строкам - строки располагаются в непрерывных участках памяти со всеми профитами
...
Рейтинг: 0 / 0
12.04.2016, 10:09
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213927
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У меня как-то изначально не возникало сомнений по поводу транспонирования.

Сложно знаешь ли представить себе табличку в БД в 500 тыс колонок
...
Рейтинг: 0 / 0
12.04.2016, 17:24
| Ответить | Цитировать | Написать  
Насчет производительности
    #39213993
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
maytonСложно знаешь ли представить себе табличку в БД в 500 тыс колонок
я о представлении в памяти и последующих вычислениях


ЗЫ жаль, топикстартер SQL код не предоставил до сих пор
...
Рейтинг: 0 / 0
12.04.2016, 18:34
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214000
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да тут возможности SQL все просадят нахер.
По хорошему надо бить 500 тыщ строк на 2х250 или 4х125
и пускать в двух или четырех процессах но кто
посоветует как для generic-dbms обеспечить
хотя-бы константное время подготовки этих
данных.
...
Рейтинг: 0 / 0
12.04.2016, 18:40
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214014
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изопропиля о представлении в памяти и последующих вычислениях
Тут как-раз нет проблем: обе матрицы 500000х5, т.е. всего 5000000 элементов. А результат 500000х500000 - его сразу на диск писать.
Параллелить тоже не сложно. Можно даже кластером считать.
...
Рейтинг: 0 / 0
12.04.2016, 18:54
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214020
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Дима, дорогой мой чел. SQL курсор в общем случае неумеет найти с 250000 по 500000 элемент.
Нету у него Seek. Для этого нужно делать партишионинг что в общем случае усложняет
задачу и вообще ставит под вопрос смыслы. Для чего? Только для умножения?
...
Рейтинг: 0 / 0
12.04.2016, 18:59
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214037
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Я бы не стал сходу утверждать, что люди, делающие разбор и оптимизацию SQL-запросов в движках SQL-серверов зря едят свой хлеб.
И рассуждения о секционировании и прочих продвинутых техниках - та самая преждевременная оптимизация.

P.S. Тупой запрос поиска "счастливых билетов" отработал "практически мгновенно". Apache Derby без всякого "тьюнингования".
Для семизначных чисел, да - заметно медленнее, но в "предел терпиливого ожидания" всё равно уложился.
...
Рейтинг: 0 / 0
12.04.2016, 19:09
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214043
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима, дорогой мой чел. SQL курсор в общем случае неумеет найти с 250000 по 500000 элемент.
Нету у него Seek. Для этого нужно делать партишионинг что в общем случае усложняет
задачу и вообще ставит под вопрос смыслы. Для чего? Только для умножения?
Я про алгоритмическое решение. SQL тут мало уместен, он на реляционные модели заточен, а тут чистое декартово произведение с сохранением полного результата.

Я выше не совсем понял о чем речь, матрицы давно изучены ... и забыты за ненадобностью.
...
Рейтинг: 0 / 0
12.04.2016, 19:14
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214069
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Basil A. SidorovЯ бы не стал сходу утверждать, что люди, делающие разбор и оптимизацию SQL-запросов в движках SQL-серверов зря едят свой хлеб.
Буквально на днях, написал запрос (MS SQL), разовый, писал лишь бы правильно ситаксис написать, молотило 18 минут. Вторых 18 минут не было, глянул план, чуть поправил - отработало за несколько секунд. Может не зря хлеб едят, но масло я бы им на хлеб не ложил.
...
Рейтинг: 0 / 0
12.04.2016, 20:17
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214070
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Люди знающие хлеб и масло это DBA. Это узкие люди. Они свою технологию
шарят а шаг влево шаг вправо - уже плывут и руки вверх. Я говорю так потому
что я - такой-же. Бывший ДБА. Вобщем надо знать что такое HashTables и B+Tree
и основы дисковой оптимизации а все остальное - приложится.
...
Рейтинг: 0 / 0
12.04.2016, 20:22
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214073
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЛюди знающие хлеб и масло это DBA. Это узкие люди. Они свою технологию
шарят а шаг влево шаг вправо - уже плывут и руки вверх.
Это говорит о том что нынешние технологии далеко не идеальны. Нужны знающие люди чтобы эффективно использовать технологии, а знающих всё досконально людей не бывает. Нельзя быть опытным во всем.
Это хорошо - иначе профи будут просто не нужны, любой бред студента исправит компилятор или оптимизатор.
...
Рейтинг: 0 / 0
12.04.2016, 20:30
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214076
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonЛюди знающие хлеб и масло это DBA. Это узкие люди. Они свою технологию
шарят а шаг влево шаг вправо - уже плывут и руки вверх.
Это говорит о том что нынешние технологии далеко не идеальны. Нужны знающие люди чтобы эффективно использовать технологии, а знающих всё досконально людей не бывает. Нельзя быть опытным во всем.
Это хорошо - иначе профи будут просто не нужны, любой бред студента исправит компилятор или оптимизатор.
Это сложный и глубокий вопрос. Сложный и глубокий. Вот я раньше считал
что дев обязан знать весь стек... а сегодня я уже устал. Я не знаю как устроено
облако Amazon S3. Но я его юзаю. Я - пользователь облака. Хотя и разработчик.
Когда я звоню по мобиле я внутренне представляю себе роутинг сот и ретрансляторов
хотя... нахер оно надо если ты просто звонишь. Нафиг знать вообще весь стек технологий
если тебе достаточно тех знаний что есть чтобы заработать котлету в несколько К зелени.

Как то так.
...
Рейтинг: 0 / 0
12.04.2016, 20:37
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214082
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНафиг знать вообще весь стек технологий если тебе достаточно тех знаний что есть чтобы заработать котлету в несколько К зелени.

Как то так.
все верно, почти, например я давно забыл про умножение матриц, Саша разъяснил 19045164 , но вообще все знать невозможно, слишком много придумано.

PS котлеты из мяса вкуснее :)
...
Рейтинг: 0 / 0
12.04.2016, 20:50
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214089
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЭто сложный и глубокий вопрос. Сложный и глубокий.
У меня напарник любитель все подряд изучать. Поверхностно знает все. Дай ему любую модную хрень, он на следующий день скажет что тут можно то и это. А спроси можно ли "это вот так" ?, не ответит, т.к. вопрос в глубь. Так и живем - он в ширь, я в глубь.
...
Рейтинг: 0 / 0
12.04.2016, 21:01
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214108
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima TИзопропиля о представлении в памяти и последующих вычислениях
Тут как-раз нет проблем: обе матрицы 500000х5, т.е. всего 5000000 элементов. А результат 500000х500000 - его сразу на диск писать.
Параллелить тоже не сложно. Можно даже кластером считать.

я предположил другой порядок умножения и матрица на выходе 5x5
...
Рейтинг: 0 / 0
12.04.2016, 21:34
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214110
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima T... и забыты за ненадобностью.
как это?
...
Рейтинг: 0 / 0
12.04.2016, 21:37
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214199
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Изопропилmaytonпропущено...

Загадками говоришь.

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

если матрицы хранятся по строкам - строки располагаются в непрерывных участках памяти со всеми профитами

Асимптотика останется прежней. Как я понимаю выигрыш в том, что данные на АЛУ будут поступать быстрее. Какая примерно оценка выигрыша по времени будет за счёт этого ?
...
Рейтинг: 0 / 0
13.04.2016, 04:59
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214203
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Лучше конечно оценка снизу. Например время выполнения без транспонирования второй матрицы t, а если будем транспонировать то (1-a)*t, где а in [0, 1). Ещё нужно учесть время которое мы потратим на транспонирование матрицы
...
Рейтинг: 0 / 0
13.04.2016, 06:05
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214213
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryЛучше конечно оценка снизу. Например время выполнения без транспонирования второй матрицы t, а если будем транспонировать то (1-a)*t, где а in [0, 1). Ещё нужно учесть время которое мы потратим на транспонирование матрицы
матрица у него и так транспонированная как уже сказали
а вот то, что для получения одного числа результирующей матрицы нужно 5 млн. пар чисел перемножить и сложить с учётом возможных переполнений и пр. - забыли
...
Рейтинг: 0 / 0
13.04.2016, 07:18
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214215
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
И ещё забыли спросить зачем это нужно. Неужели систему линейных алгебраических уравнений решает
...
Рейтинг: 0 / 0
13.04.2016, 07:23
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214219
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Вообще-то главная изюминка алгоритма умножения матриц - это что он хорошо распараллеливается.
На языках типа С++, Java это делается легко.
На SQL добиться этого будет достаточно сложно.
...
Рейтинг: 0 / 0
13.04.2016, 07:39
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214221
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЕщё нужно учесть время которое мы потратим на транспонирование матрицы
Нисколько не потратим. Просто поменять в коде
Код: plaintext
1.
m[i][j] на m[j][i]
...
Рейтинг: 0 / 0
13.04.2016, 07:59
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214233
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryЕщё нужно учесть время которое мы потратим на транспонирование матрицы
Нисколько не потратим. Просто поменять в коде
Код: plaintext
1.
m[i][j] на m[j][i]



а это поможет? ведь элементы не будут находить рядом с другом
...
Рейтинг: 0 / 0
13.04.2016, 08:25
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214235
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
SashaMercuryа это поможет? ведь элементы не будут находить рядом с другом
как раз будут
...
Рейтинг: 0 / 0
13.04.2016, 08:30
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214241
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИзопропилSashaMercuryа это поможет? ведь элементы не будут находить рядом с другом
как раз будут
Не будут. Элемент результата это произведение строки одной на столбец второй. Саша прав, для оптимизации подкачки в кэш проца вторую лучше транспонировать, чтобы столбец стал строкой.
...
Рейтинг: 0 / 0
13.04.2016, 08:45
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214252
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima TСаша прав, для оптимизации подкачки в кэш проца вторую лучше транспонировать, чтобы столбец стал строкой.
19045116

87 миллисекунд без оптимизации SSE/AVX перемножаются эти матрицы на несчастном ноутбуке.
Что я делаю не так?
...
Рейтинг: 0 / 0
13.04.2016, 09:04
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214254
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Изопропил,
а какая на выходе матрица ? Размерность
...
Рейтинг: 0 / 0
13.04.2016, 09:06
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214258
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
SashaMercury,

5x5 .

500000x500000 - полагаю менее вероятной, топикстартер молчит как партизан
...
Рейтинг: 0 / 0
13.04.2016, 09:11
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214264
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ИзопропилSashaMercury,

5x5 .

500000x500000 - полагаю менее вероятной, топикстартер молчит как партизан

значит у вас выполняется около 10^6 операций, это и должно быть быстро, если не ошибаюсь
...
Рейтинг: 0 / 0
13.04.2016, 09:16
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214265
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Около 10^7
...
Рейтинг: 0 / 0
13.04.2016, 09:19
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214278
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
SashaMercuryэто и должно быть быстро
вот я и говорю о бесполезности преждевременной оптимизации
...
Рейтинг: 0 / 0
13.04.2016, 09:32
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214286
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изопропил87 миллисекунд без оптимизации SSE/AVX перемножаются эти матрицы на несчастном ноутбуке.
Что я делаю не так?
если результат 5*5, то 25 * (500000 умножений + 500000 сложений) т.е. 25 млн. простейших операций.
Добавим служебный код, пусть еще 25 млн. операций. Условно дадим твоему ноуту 2 ГГц проц.
Итого: 50 млн. / 2ГГц = 25 мс
тормозной у тебя код, есть куда оптимизировать :)
...
Рейтинг: 0 / 0
13.04.2016, 09:36
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214288
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ИзопропилSashaMercuryэто и должно быть быстро
вот я и говорю о бесполезности преждевременной оптимизации

Скорее у него в другом порядке матрицы умножаются, потому так долго. Но в любом случае исполнение алгоритма должно уложиться в 60 минут, как мне кажется
...
Рейтинг: 0 / 0
13.04.2016, 09:36
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИтого: 50 млн. / 2ГГц = 25 мс
тормозной у тебя код, есть куда оптимизировать :)
Дима что-то твоя формула у меня вызывает искреннее изумление.
...
Рейтинг: 0 / 0
13.04.2016, 09:44
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214304
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изопропил500000x500000 - полагаю менее вероятной, топикстартер молчит как партизан
Что-то я затупил в начале, про 5*5 не подумал, 500000x500000 даже по четыре байта на значение займет 1 Тб. Нереальная какая-то табличка.
...
Рейтинг: 0 / 0
13.04.2016, 09:47
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214365
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima T1 Тб. Нереальная какая-то табличка.
предположим - реальная. Затык в диске будет. Что опять же свидетельствует о бессмысленности преждевременной оптимизации вычислений
...
Рейтинг: 0 / 0
13.04.2016, 10:37
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214389
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Затестил SQL и правда задачка не для него. Представил матрицы в виде таблиц (x, y, value)
Соответственно расчет
Код: sql
1.
2.
3.
select m2.x, m1.y, sum(m1.value * m2.value) 
	from m1, m2
	group by m2.x, m1.y


умирает уже при матрице 5000*5
 
Скрипт на MS SQL
Код: sql
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.
IF object_id('tempdb..#m1') IS NULL begin
	-- заполнение матриц
	create table #m1 (x int, y int, a float(53))
	declare @i int
	set @i = 1

	while @i <= 500 begin
		insert into #m1 values (@i, 1, @i)
		insert into #m1 values (@i, 2, @i + 0.1)
		insert into #m1 values (@i, 3, @i + 0.2)
		insert into #m1 values (@i, 4, @i + 0.3)
		insert into #m1 values (@i, 5, @i + 0.4)
		set @i = @i + 1
	end

	select x as y, y as x, a + 0.5 as b into #m2 from #m1
end
go
--расчет
select #m2.x, #m1.y, sum(#m1.a * #m2.b) 
	from #m1, #m2
	group by #m2.x, #m1.y

--drop table #m1
--drop table #m2


надо хранить в виде (x, value1, value2 ...) и (y, value1, value2 ...)
и выборка как-то так
Код: sql
1.
2.
select sum(m1.v1 * m2.v1) as r11, sum(m1.v1 * m2.v2) as r12, ...
	from m1 join m2 on m1.x = m2.y


вроде правильно, но коряво и не универсально.
...
Рейтинг: 0 / 0
13.04.2016, 10:54
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214406
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima Tвроде правильно, но коряво и не универсально.
зато быстро, а насчёт универсальности и корявости - код сгенерить можно
...
Рейтинг: 0 / 0
13.04.2016, 11:04
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214479
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TСоответственно расчет
Код: sql
1.
2.
3.
select m2.x, m1.y, sum(m1.value * m2.value)
	from m1, m2
	group by m2.x, m1.y



Условие связи таблиц ты куда-то пропил. Вместе с индексами.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
13.04.2016, 11:42
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214505
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TСоответственно расчет
Код: sql
1.
2.
3.
select m2.x, m1.y, sum(m1.value * m2.value)
	from m1, m2
	group by m2.x, m1.y



Условие связи таблиц ты куда-то пропил. Вместе с индексами.

Нет условия, это декартово произведение, все со всеми.
Индексы тут не помогут.
...
Рейтинг: 0 / 0
13.04.2016, 11:58
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214512
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TНет условия, это декартово произведение, все со всеми.
Тогда на выходе у тебя совсем не произведение матриц, а матрица скалярного произведения.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
13.04.2016, 12:02
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214584
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TНет условия, это декартово произведение, все со всеми.
Тогда на выходе у тебя совсем не произведение матриц, а матрица скалярного произведения.

Точно. При такой структуре похоже вообще селектом не посчитать. Сломал мозг в попытках придумать условие объединения.
...
Рейтинг: 0 / 0
13.04.2016, 12:53
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214593
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Dima TЗатестил SQL и правда задачка не для него. Представил матрицы в виде таблиц (x, y, value)
Соответственно расчет
Код: sql
1.
2.
3.
select m2.x, m1.y, sum(m1.value * m2.value) 
	from m1, m2
	group by m2.x, m1.y


умирает уже при матрице 5000*5


наверное всё-таки SQL это хранение и поиск данных, а расчёты это C, GO, Fortran может...
что если в памяти хранить по столбам например? перемножил столб на значение из другой матрицы, на его место взял другой
а результаты складировать
...
Рейтинг: 0 / 0
13.04.2016, 13:01
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214597
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TПри такой структуре похоже вообще селектом не посчитать. Сломал мозг в
попытках придумать условие объединения.
Мой запрос с первой страницы пробовал?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
13.04.2016, 13:03
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214619
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
tip78что если в памяти хранить по столбам например?

первую матрицу хранить по строкам, вторую по столбцам(транспонированую)
полезно что для SQL рассчётов, что C

вуаля
...
Рейтинг: 0 / 0
13.04.2016, 13:22
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214623
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В этой задаче SQL нужно вообще вынести за скобки. Иначе мы никуда не уедем.
...
Рейтинг: 0 / 0
13.04.2016, 13:25
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214628
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Изопропилпервую матрицу хранить по строкам, вторую по столбцам(транспонированую)
полезно что для SQL рассчётов, что C
Пофиг. Просто создать правильные индексы. Нормальная БД вообще в таблицу не полезет, будет брать данные из упорядоченного индекса.
...
Рейтинг: 0 / 0
13.04.2016, 13:29
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214647
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Изопропилtip78что если в памяти хранить по столбам например?

первую матрицу хранить по строкам, вторую по столбцам(транспонированую)
полезно что для SQL рассчётов, что C

а чем полезны эти пляски?
(спрашиваю для просвещения, как НЕ математик)
...
Рейтинг: 0 / 0
13.04.2016, 13:39
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214652
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TПри такой структуре похоже вообще селектом не посчитать. Сломал мозг в
попытках придумать условие объединения.
Мой запрос с первой страницы пробовал?

Сейчас попробовал. Подходит. Оказалось я в тестовых данных накосячил. В итоге совсем запутался.
Матрицы 500000*5 с индексами 4 сек. работает. Без индексов - 5 сек.

 
скрипт
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
IF object_id('tempdb..#a') IS NULL begin
	-- заполнение матриц
	create table #a (x int, y int, v float(53))
	declare @i int
	set @i = 1

	while @i <= 500000 begin
		insert into #a values (@i, 1, @i)
		insert into #a values (@i, 2, @i + 0.1)
		insert into #a values (@i, 3, @i + 0.2)
		insert into #a values (@i, 4, @i + 0.3)
		insert into #a values (@i, 5, @i + 0.4)
		set @i = @i + 1
	end
	CREATE CLUSTERED INDEX #IX_ax ON #a (x, y)

	select x as y, y as x, v + 0.5 as v into #b from #a 
	CREATE CLUSTERED INDEX #by ON #b (y, x)
end
go

select #b.x, #a.y, sum(#a.v * #b.v) 
	from #a join #b on #b.y = #a.x
	group by #b.x, #a.y

...
Рейтинг: 0 / 0
13.04.2016, 13:44
| Ответить | Цитировать | Написать  
Насчет производительности
    #39214656
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
tip78а чем полезны эти пляски?
(спрашиваю для просвещения, как НЕ математик)

вычисляем скалярное произведение строки первой на столбец второй
если вторая матрица хранится по строкам как и первая - придётся обращаться к несмежным ячейкам памяти -
выборка и работа кэша процесссора станут неэффективными и лишимся возможности на полную катушку задействовать SSE/AVX
...
Рейтинг: 0 / 0
13.04.2016, 13:45
| Ответить | Цитировать | Написать  
Насчет производительности
    #39217002
log_here
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
log_here
Участник
Dimmf28Есть такая задача, умножить одну матрицу на другую , делаю я эту в БД занимает оно 24 часа, думаю если вот перемножать матрицы на С++,а не SQL даст ли оно выигрыш в производительности, в каждой матрице где то 500 тысяч записей ну и 5 столбиков?

не читал всю тему, отвечу, что есть формулы для квадратных матриц, которые делают перемножение не за N * N * N, а за N ^ 2.7 (примерно), выигрыш ощущается. Твои матрицы можно свести к квадратным, дописав нули. А можно, наверное, и для неквадратных ускоряющие формулы вывести.
...
Рейтинг: 0 / 0
16.04.2016, 00:07
| Ответить | Цитировать | Написать  
Насчет производительности
    #39217199
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
log_hereDimmf28Есть такая задача, умножить одну матрицу на другую , делаю я эту в БД занимает оно 24 часа, думаю если вот перемножать матрицы на С++,а не SQL даст ли оно выигрыш в производительности, в каждой матрице где то 500 тысяч записей ну и 5 столбиков?

не читал всю тему, отвечу, что есть формулы для квадратных матриц, которые делают перемножение не за N * N * N, а за N ^ 2.7 (примерно), выигрыш ощущается. Твои матрицы можно свести к квадратным, дописав нули. А можно, наверное, и для неквадратных ускоряющие формулы вывести.
и что получится, если умножить на 0?
...
Рейтинг: 0 / 0
16.04.2016, 17:24
| Ответить | Цитировать | Написать  
Насчет производительности
    #39217306
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
log_hereDimmf28Есть такая задача, умножить одну матрицу на другую , делаю я эту в БД занимает оно 24 часа, думаю если вот перемножать матрицы на С++,а не SQL даст ли оно выигрыш в производительности, в каждой матрице где то 500 тысяч записей ну и 5 столбиков?

не читал всю тему, отвечу, что есть формулы для квадратных матриц, которые делают перемножение не за N * N * N, а за N ^ 2.7 (примерно), выигрыш ощущается. Твои матрицы можно свести к квадратным, дописав нули. А можно, наверное, и для неквадратных ускоряющие формулы вывести.
Предлагаешь матрицу 5*500000 привести к 500000*500000, т.е. сделать ее в 100000 раз больше и думаешь ускорить потом это какими-то алгоритмами? Похоже ты даже то что процитировал не почитал.
...
Рейтинг: 0 / 0
16.04.2016, 19:54
| Ответить | Цитировать | Написать  
Насчет производительности
    #39217318
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В науке и технике для представления толстых матриц (больше тыщи строк или столбцов) используется
механизм Sparse matrix (разреженные).

Представить себе матрицу порядка 50 на 50 тыщ которая-бы несла ценную и полезную инфу весьма
сложно.
...
Рейтинг: 0 / 0
16.04.2016, 20:16
| Ответить | Цитировать | Написать  
83 сообщений из 83, показаны все 4 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Насчет производительности
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]