3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
|
1 | |
Как лучше всего хранить коэффициенты?26.02.2012, 13:58. Показов 4575. Ответов 52
Метки нет (Все метки)
Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double
0
|
26.02.2012, 13:58 | |
Ответы с готовыми решениями:
52
Задача на алгоритм Дейкстры (как лучше хранить информацию?) Оконный менеджер. Как лучше хранить указатели на элементы менеджера? Как лучше всего хранить контент сайта? Как лучше всего хранить данные для приложения? |
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
|
01.03.2012, 20:32 | 22 |
ValeryS, да, медленнее в 4 раза где-то, но если экономия памяти превышает это число то очень полезно.
0
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
|
01.03.2012, 20:32 [ТС] | 23 |
0
|
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
|
01.03.2012, 20:35 | 24 |
hello19, могу для обычного уравнения, а это эти я не помню.
0
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
|
01.03.2012, 20:35 [ТС] | 25 |
да ну хоть как... просто глазами увидеть..
0
|
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
||||||
01.03.2012, 20:43 | 26 | |||||
hello19,
0
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
|
01.03.2012, 20:52 [ТС] | 27 |
а какие входные данные?
вот скажем, если у меня вот такая система уравнений: 1*x1 + 2x3 = 3 x2 = 5 x3 = 1 как лучше всего хранить ненулевые коэффициенты?
0
|
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
|
01.03.2012, 20:56 | 28 |
hello19,
1*x1 + 2x3 = 3 x2 = 5 x3 = 1 Если правильно понял, то в полной форме примерно так: 1*x1 + 0*x2 + 2x3 = 3 0*x1 + 1*x2 + 0*x3 = 5 0*x1 + 0*x2 + 1*x3 = 1 И вот матрица 4 на 3, а храним только элементы с позицией, 1:1, 3:1, 4:1, 2:2, 4:2, 3:3, 4:3.
0
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
|
01.03.2012, 20:59 [ТС] | 29 |
вот, да.. это было бы замечательно.. но как это сделать?
0
|
01.03.2012, 21:01 | 30 |
Если интересно, то есть еще один способ, предложенный в книжке Мозговой М. C++ Мастер-класс. 85 нетривиальных проектов, решений и задач раздел 1.2 Разреженные матрицы там показан пример класса, в нем используются map и pair.
1
|
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
|
01.03.2012, 21:01 | 31 |
hello19, как я показал выше. Вводим 1:1, 3:1, 4:1, 2:2, 4:2, 3:3, 4:3 и соответствующее им значение коэффициента.
0
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
||||||
01.03.2012, 21:07 [ТС] | 32 | |||||
Интересно-интересно... сейчас поищу литературу
Добавлено через 5 минут Да ну я просто не знаю как их хранить... вот я раньше делал вот вот так вот:
дальше мне надо будет работать с элементами одной строки... проще всего - сделать цикл... но проблема в том, что для этого Вот как мне циклом умножить все коэффициенты первой строки например на 2? я запускаю цикл по столбцам при фиксированной строке... но ведь у меня не все столбцы то заняты...вот в первой строке, например, нет коэффициента стоящего на 2-м месте...
0
|
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
||||||
01.03.2012, 21:12 | 33 | |||||
hello19, умножить на 2 можно так:
1
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
||||||
01.03.2012, 21:17 [ТС] | 34 | |||||
а, скажем, если мне надо 1 и 3 умножить на 2, а последний разделить на 2..
и что означает эта строчка:
0
|
74 / 54 / 12
Регистрация: 20.02.2012
Сообщений: 239
|
|
01.03.2012, 21:20 | 35 |
hello19, просто добавить условие сравнивания ещё и cow.
1
|
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
|
|
01.03.2012, 21:24 [ТС] | 36 |
ммм... вообщем тут есть еще над чем подумать.. в субботу продолжу спасибо!
0
|
thebvog
|
01.03.2012, 21:27
#37
|
Не по теме: hello19, не за что :)
0
|
Заблокирован
|
|
03.03.2012, 01:26 | 38 |
hello19, ты на неверном пути. Лучше того что мы паяли с тобой летом врядли можно без спец методов решения СЛАУ высокого порядка решить.
Смотри у нас было 4000х4000 элементов - это ~ 128000000 байт (122 Мб), виртуалка уже начинала трещать. Теперь ты вводишь структуру - у тебя в 3 раза выростет объём виртуалки (т.к. в структуре 3 поля) 3х122 = 366 Мб (с таким динамическим монстром не всякое железо справится). Я тебе предлагаю подождать недельку, я как раз расмотрю методы решения СЛАУ высокого порядка здесь https://www.cyberforum.ru/faq/... ost2431657 Не по теме: hello19, просто поверь ты сейчас на неверном пути. Никакого выиграша структуры тебе не дадут. У тебя есть Гаусс(лучше его в плане производительности для не спец методов на мой взгляд нет!). Для разрежённых матриц думаю напаять метод с обобщённым правилом Саррюса для определителя n-го порядка, может откопаю где-то норм описание спец методов тога будет настоящий алгоритм...
0
|
385 / 229 / 12
Регистрация: 06.07.2011
Сообщений: 512
|
|
03.03.2012, 02:07 | 39 |
для хранения разреженных матриц методов много. одни сильно выигрывают по памяти, но уступают по скорости "распаковки", другие - наоборот.
если матрица у нас 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 будет храниться значение. Если матрица симметричная, то алгоритмы еще интереснее. А если к тому же и ленточная (все ненулевые элементы близко к диагонали), то там крайне эффективные схемы хранения есть.
0
|
Заблокирован
|
|
03.03.2012, 02:15 | 40 |
- там ничего такого нет(по крайней мере заметить это нереально ввиду колоссального объёма матрицы).
Вот тот топик Решить систему алгебраических линейных неоднородных уравнени я даю ссылку на проект на котором по памяти остановились. Paporotnik, если есть настоящие соображения по матрицам и СЛАУ с готовностью выслушаю!
0
|
03.03.2012, 02:15 | |
03.03.2012, 02:15 | |
Помогаю со студенческими работами здесь
40
Где и как лучше всего хранить структурированную информацию Как лучше всего хранить двумерный массив переменного размера Как лучше всего хранить текстовые данные (более 1000 слов) Где и как лучше всего хранить строку, которая будет подвергаться значительным изменениям Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |