Форум программистов, компьютерный форум CyberForum.ru

Как лучше всего хранить коэффициенты? - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.92
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
26.02.2012, 13:58     Как лучше всего хранить коэффициенты? #1
Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
03.03.2012, 02:24     Как лучше всего хранить коэффициенты? #41
упаковка разреженных матриц - это не просто баловство. это необходимость. и она очень ярко проявляется, скажем, в реализациях метода конечных элементов. правда там это прежде всего симметричные ленточные матрицы, но полезность этого приема не уменьшается.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:30     Как лучше всего хранить коэффициенты? #42
Paporotnik, упаковать не проблемма и держать в памяти можно только ненулевые элементы, а как потом такую матрицу загнать в любой из существующих методов решения СЛАУ - в этом вся и соль...
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
03.03.2012, 02:36     Как лучше всего хранить коэффициенты? #43
Сообщение было отмечено автором темы, экспертом или модератором как ответ
а что этим методам нужно от матрицы? ответ - знать какой элемент находится по таким-то координатам. и методы упаковки позволяют восстановить эту информацию, пускай и в несколько шагов и разумеется не так быстро, как прямой доступ к массиву. но экономия памяти колоссальна. я показал это выше.
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:41     Как лучше всего хранить коэффициенты? #44
Цитата Сообщение от Paporotnik Посмотреть сообщение
а что этим методам нужно от матрицы? ответ - знать какой элемент находится по таким-то координатам. и методы упаковки позволяют восстановить эту информацию, пускай и в несколько шагов и разумеется не так быстро, как прямой доступ к массиву. но экономия памяти колоссальна. я показал это выше.
- решить систему А*В = Х
А 4000х4000 В - 4000 элементов. Проект по ссылке в посте 38 решал систему по методу Гаусса. Рзультаты получились довольно приемлимыми, однако не совпали с результатами полученными в SCILAB. Следует отметить что в исходной матрице А некоторые строки были полностью нулевыми, поэтому был ещё разработан алгоритм эффективного вычеркивания соотв строки и столбца...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.03.2012, 02:45     Как лучше всего хранить коэффициенты? #45
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
а как потом такую матрицу загнать в любой из существующих методов решения СЛАУ - в этом вся и соль...
Любой метод можно подогнать под любой вид матрицы. Будет такой метод работать медленнее чем для обычной матрицы.
Как всегда: выигрываем во времени - проигрываем в памяти. Выигрываем в памяти - проигрываем во времени.
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:49     Как лучше всего хранить коэффициенты? #46
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Любой метод можно подогнать под любой вид матрицы. Будет такой метод работать медленнее чем для обычной матрицы.
Как всегда: выигрываем во времени - проигрываем в памяти. Выигрываем в памяти - проигрываем во времени.
valeriikozlov, проект с полным объёмом памяти позволил получить решение за 10 секунд. Аналогичный алгоритм с поэлементной работой отрабатывал где-то по памяти за мин 25(как раз успевал кофейка выпить). (Правда ЭВМ для теста была паршивая ОЗУ 384 Мб и Celeron 1.1)
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
03.03.2012, 02:50     Как лучше всего хранить коэффициенты? #47
и? вы пытаетесь опровергнуть пользу упаковки матриц тем, что вы решили общую задачу общим методом? при том, что 4000 на 4000 это совсем не масштаб реальных вычислений в реальных ситуациях?
я вам привожу факты из конкретных инженерных областей. не понимаю, о чем тут можно спорить.

да, и в конце концов. ТС задал вопрос - я дал ответ.
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:55     Как лучше всего хранить коэффициенты? #48
Лично моё мнение - существуют спец методы решение СЛАУ высокого порядка(алгоритмы работают лишь с частями матрицы по своим особым правилам) - решение получается крайне точным однако нормального описания в литратуре я так и не встретил, так упоминания о производительности и быстроте и всё. Так что ответчикам лучше бросить на усилия по поиску спец метода чем обсуждать нужны ли структуры или нет. Мой ответ не нужны, так как никакого выиграша в производительности не дадут, а лишь дополнительно усложнят алгоритм. Как вариант надо рассмтреть алгоритм перезаписи файла, возможно файла отображённого в память. Вот моё видение проблеммы...

Добавлено через 2 минуты

Не по теме:

Цитата Сообщение от Paporotnik Посмотреть сообщение
задачу общим методом
- коррективы были причём несколько(это позволило ускорить нашего Гаусса в пару раз).
Есть желание открываем проект и смотрим код...
Я тут спорить ни с кем не хочу:cofee:
hello19, сам меня попросил написать своё мнение - я написал, а его дело прислушиваться ко мне или нет...
PS В своё время истратил на алгоритм где-то с недельку и знаю подводные камни решения этой системы как отче наш. Предлагаю не вступать в палемику а написать код решения, думаю это будет максимально полезно для ТС

Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
03.03.2012, 02:59     Как лучше всего хранить коэффициенты? #49
на правах пищи для размышлений занимательную статью: http://vestnik.vgasu.ru/?source=4&articleno=253
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.03.2012, 03:02     Как лучше всего хранить коэффициенты? #50
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
valeriikozlov, проект с полным объёмом памяти позволил получить решение за 10 секунд. Аналогичный алгоритм с поэлементной работой отрабатывал где-то по памяти за мин 25(как раз успевал кофейка выпить). (Правда ЭВМ для теста была паршивая ОЗУ 384 Мб и Celeron 1.1)
Давно таких ЭВМ не встречал. Суть не в этом, сейчас обращаюсь к hello19:
Хотелось бы услышать полное условие задачи именно от Вас. Заинтересовало
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
03.03.2012, 19:17  [ТС]     Как лучше всего хранить коэффициенты? #51
Цитата Сообщение от Paporotnik Посмотреть сообщение
для хранения разреженных матриц методов много. одни сильно выигрывают по памяти, но уступают по скорости "распаковки", другие - наоборот.
если матрица у нас N*N и в ней k ненулевых элементов, то есть метод, позволяющий хранить 2*k значений для сохранения данных о матрице. алгоритм таков:

пусть дана матрица:
0 0 3 0 0
1 0 2 0 0
0 0 0 0 4
0 5 0 1 0
0 0 0 0 1
Заведем массив Values, в котором перечислим все значения, выбрав определенный способ обхода (по столбцам, к примеру).
Values={1,5,3,2,1,4,1}
Теперь заведем массив Coords, элементами которого будет значение i+(j-1)*n, где i-номер строки, j-номер столбца элемента из массива Values, а n-порядок матрицы. Проще говоря порядковый номер при выбранном виде обхода. Получим:
Coords={2,9,11,12,19,23,25}

Соответственно, для проверки возьмем произвольные координаты элементов: (3;4) и (4;2). Подставляем в формулу выше и получаем значения 18 и 9. Ищем эти значения в массиве coords. 18 не найдено, значит элемент нулевой. 9 найдено, значит элемент не нулевой. Берем индекс этого значения в Coords - под этим же номером в Values будет храниться значение.

Если матрица симметричная, то алгоритмы еще интереснее. А если к тому же и ленточная (все ненулевые элементы близко к диагонали), то там крайне эффективные схемы хранения есть.
Идейка очень интересная... пожалуй стоит задуматься над ее реализацией...
да и памяти тут съедается немного...

-=ЮрА=- мне же не надо хранить всю матрицу - только ее не отрицательные элементы... по этому памяти не будет так много съедаться...
что качается метода решения - вообщем то передо мной стоит задача как раз решить систему итерационным методом
-=ЮрА=-
03.03.2012, 22:47
  #52

Не по теме:

Цитата Сообщение от hello19 Посмотреть сообщение
-=ЮрА=- мне же не надо хранить всю матрицу - только ее не отрицательные элементы... по этому памяти не будет так много съедаться...
- ну ок, раз так считаешь пусть так и будетВ принципе тебе видней что и к чему должно быть в решении(я даже не представляю для каких целей понадобилось решение такой огромной системы)...

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2012, 19:04     Как лучше всего хранить коэффициенты?
Еще ссылки по теме:

Оконный менеджер. Как лучше хранить указатели на элементы менеджера? C++
C++ Подскажите, как лучше всего изучать язык, ежели в академии не дают достаточный объем знаний
Как лучше всего разделить строку на несколько подстрок? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
07.03.2012, 19:04  [ТС]     Как лучше всего хранить коэффициенты? #53
а как считать элементы в эти 2 массива?
Вот у меня например вот такая системка:
x1 + 3x2 = 4
x2 = 1

Матрица ненулевых коэффициентов у меня выглядит вот так:
(1;1)(2;3)
(2;1)

Как мне просто считать в вектор values значения 1,3,1
Ну и, соответственно в вектор coords значения 1, 3, 4
Yandex
Объявления
07.03.2012, 19:04     Как лучше всего хранить коэффициенты?
Ответ Создать тему
Опции темы

Текущее время: 07:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru