powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Насчет производительности
25 сообщений из 83, страница 3 из 4
Насчет производительности
    #39214221
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЕщё нужно учесть время которое мы потратим на транспонирование матрицы
Нисколько не потратим. Просто поменять в коде
Код: plaintext
1.
m[i][j] на m[j][i] 
...
Рейтинг: 0 / 0
Насчет производительности
    #39214233
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TSashaMercuryЕщё нужно учесть время которое мы потратим на транспонирование матрицы
Нисколько не потратим. Просто поменять в коде
Код: plaintext
1.
m[i][j] на m[j][i] 



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

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

5x5 .

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

5x5 .

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

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

Скорее у него в другом порядке матрицы умножаются, потому так долго. Но в любом случае исполнение алгоритма должно уложиться в 60 минут, как мне кажется
...
Рейтинг: 0 / 0
Насчет производительности
    #39214299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TИтого: 50 млн. / 2ГГц = 25 мс
тормозной у тебя код, есть куда оптимизировать :)
Дима что-то твоя формула у меня вызывает искреннее изумление.
...
Рейтинг: 0 / 0
Насчет производительности
    #39214304
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Изопропил500000x500000 - полагаю менее вероятной, топикстартер молчит как партизан
Что-то я затупил в начале, про 5*5 не подумал, 500000x500000 даже по четыре байта на значение займет 1 Тб. Нереальная какая-то табличка.
...
Рейтинг: 0 / 0
Насчет производительности
    #39214365
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T1 Тб. Нереальная какая-то табличка.
предположим - реальная. Затык в диске будет. Что опять же свидетельствует о бессмысленности преждевременной оптимизации вычислений
...
Рейтинг: 0 / 0
Насчет производительности
    #39214389
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
Насчет производительности
    #39214406
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tвроде правильно, но коряво и не универсально.
зато быстро, а насчёт универсальности и корявости - код сгенерить можно
...
Рейтинг: 0 / 0
Насчет производительности
    #39214479
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
Насчет производительности
    #39214505
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
Насчет производительности
    #39214512
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TНет условия, это декартово произведение, все со всеми.
Тогда на выходе у тебя совсем не произведение матриц, а матрица скалярного произведения.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Насчет производительности
    #39214584
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovDima TНет условия, это декартово произведение, все со всеми.
Тогда на выходе у тебя совсем не произведение матриц, а матрица скалярного произведения.

Точно. При такой структуре похоже вообще селектом не посчитать. Сломал мозг в попытках придумать условие объединения.
...
Рейтинг: 0 / 0
Насчет производительности
    #39214593
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
Насчет производительности
    #39214597
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TПри такой структуре похоже вообще селектом не посчитать. Сломал мозг в
попытках придумать условие объединения.
Мой запрос с первой страницы пробовал?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Насчет производительности
    #39214619
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78что если в памяти хранить по столбам например?

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

вуаля
...
Рейтинг: 0 / 0
Насчет производительности
    #39214623
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В этой задаче SQL нужно вообще вынести за скобки. Иначе мы никуда не уедем.
...
Рейтинг: 0 / 0
25 сообщений из 83, страница 3 из 4
Форумы / C++ [игнор отключен] [закрыт для гостей] / Насчет производительности
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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