Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.92
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
#1

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

26.02.2012, 13:58. Просмотров 3048. Ответов 52
Метки нет (Все метки)

Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2012, 13:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как лучше всего хранить коэффициенты? (C++):

Задача на алгоритм Дейкстры (как лучше хранить информацию?) - C++
Доброго времени суток. Есть задача: Есть идея хранить входные данные след. образом: Выделить в памяти 2-х матрицы(Tab1 и Tab2...

Оконный менеджер. Как лучше хранить указатели на элементы менеджера? - C++
Привет! Делаю тут 3D движок :wizard: В общем есть главный класс движка mgeSystem, так же есть класс окна mgeWindow, который не...

Как лучше всего создать форму в С++ - C++
Хочу попробовать создать не консольную программу, а графическую. Как лучше всего создавать формы?

Как лучше всего учить язык C++? - C++
Хочу начать изучать язык программирования! Остановился на C++, а с чего начать не знаю!

Как лучше всего реализовать настройки в программе? - C++
Хочу грамотно сделать настройки для своей программы. Сейчас примерно так: программа создаёт объект класса Settings, там пользователь...

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

52
thebvog
73 / 53 / 3
Регистрация: 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
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 21:07  [ТС] #32
Цитата Сообщение от Xind Посмотреть сообщение
Если интересно, то есть еще один способ, предложенный в книжке Мозговой М. C++ Мастер-класс. 85 нетривиальных проектов, решений и задач раздел 1.2 Разреженные матрицы там показан пример класса, в нем используются map и pair.
Интересно-интересно... сейчас поищу литературу

Добавлено через 5 минут
Цитата Сообщение от thebvog Посмотреть сообщение
hello19, как я показал выше. Вводим 1:1, 3:1, 4:1, 2:2, 4:2, 3:3, 4:3 и соответствующее им значение коэффициента.
Да ну я просто не знаю как их хранить...
вот я раньше делал вот вот так вот:
C++
1
2
3
4
5
6
7
    struct elements
    {
        int one; // строка
        int two; // столбец
        double three; // значение коэффициента
    };
    vector <elements> matrix(N);
допустим я туда считал 1:1, 3:1, 4:1, 2:2, 4:2, 3:3, 4:3 и соответствующее им значение коэффициентов
дальше мне надо будет работать с элементами одной строки... проще всего - сделать цикл...
но проблема в том, что для этого

Вот как мне циклом умножить все коэффициенты первой строки например на 2?
я запускаю цикл по столбцам при фиксированной строке... но ведь у меня не все столбцы то заняты...вот в первой строке, например, нет коэффициента стоящего на 2-м месте...
0
thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 21:12 #33
hello19, умножить на 2 можно так:
C++
1
2
3
4
do
{
    k[i]->value *= 2;
} while (k[i]->row == ROW);
1
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 21:17  [ТС] #34
а, скажем, если мне надо 1 и 3 умножить на 2, а последний разделить на 2..
и что означает эта строчка:
C++
1
while (k[i]->row == ROW)
0
thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 21:20 #35
hello19, просто добавить условие сравнивания ещё и cow.
1
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 21:24  [ТС] #36
ммм... вообщем тут есть еще над чем подумать.. в субботу продолжу спасибо!
0
thebvog
01.03.2012, 21:27
  #37

Не по теме:

hello19, не за что

0
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 01:26 #38
hello19, ты на неверном пути. Лучше того что мы паяли с тобой летом врядли можно без спец методов решения СЛАУ высокого порядка решить.
Смотри у нас было 4000х4000 элементов - это ~ 128000000 байт (122 Мб), виртуалка уже начинала трещать. Теперь ты вводишь структуру
Цитата Сообщение от hello19 Посмотреть сообщение
struct elements
* * * * {
* * * * * * * * int one; // строка
* * * * * * * * int two; // столбец
* * * * * * * * double three; // значение коэффициента
* * * * };
* * * * vector <elements> matrix(N)
- у тебя в 3 раза выростет объём виртуалки (т.к. в структуре 3 поля) 3х122 = 366 Мб (с таким динамическим монстром не всякое железо справится).
Я тебе предлагаю подождать недельку, я как раз расмотрю методы решения СЛАУ высокого порядка здесь http://www.cyberforum.ru/faq/thread436065.html#post2431657

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Содержание FAQ
...
4.5 Класс Матрица.
5 Системы линейных алгебраических уравнений(СЛАУ)


5.1 Метод Гаусса
5.2 Матричный способ решения
5.3 Метод Крамера
5.4 Решение СЛАУ высокого порядка
6 Геометрические задачи
7 Распознавание ручного ввода задания аналитических зависимостей

Не по теме:

hello19, просто поверь ты сейчас на неверном пути. Никакого выиграша структуры тебе не дадут. У тебя есть Гаусс(лучше его в плане производительности для не спец методов на мой взгляд нет!). Для разрежённых матриц думаю напаять метод с обобщённым правилом Саррюса для определителя n-го порядка, может откопаю где-то норм описание спец методов тога будет настоящий алгоритм...

0
Paporotnik
383 / 227 / 7
Регистрация: 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
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:15 #40
Цитата Сообщение от Paporotnik Посмотреть сообщение
Если матрица симметричная, то алгоритмы еще интереснее. А если к тому же и ленточная (все ненулевые элементы близко к диагонали), то там крайне эффективные схемы хранения есть.
- там ничего такого нет(по крайней мере заметить это нереально ввиду колоссального объёма матрицы).
Вот тот топик
Решить систему алгебраических линейных неоднородных уравнени
я даю ссылку на проект на котором по памяти остановились.

Paporotnik, если есть настоящие соображения по матрицам и СЛАУ с готовностью выслушаю!
0
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
03.03.2012, 02:24 #41
упаковка разреженных матриц - это не просто баловство. это необходимость. и она очень ярко проявляется, скажем, в реализациях метода конечных элементов. правда там это прежде всего симметричные ленточные матрицы, но полезность этого приема не уменьшается.
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:30 #42
Paporotnik, упаковать не проблемма и держать в памяти можно только ненулевые элементы, а как потом такую матрицу загнать в любой из существующих методов решения СЛАУ - в этом вся и соль...
0
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
03.03.2012, 02:36 #43
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
а что этим методам нужно от матрицы? ответ - знать какой элемент находится по таким-то координатам. и методы упаковки позволяют восстановить эту информацию, пускай и в несколько шагов и разумеется не так быстро, как прямой доступ к массиву. но экономия памяти колоссальна. я показал это выше.
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.03.2012, 02:41 #44
Цитата Сообщение от Paporotnik Посмотреть сообщение
а что этим методам нужно от матрицы? ответ - знать какой элемент находится по таким-то координатам. и методы упаковки позволяют восстановить эту информацию, пускай и в несколько шагов и разумеется не так быстро, как прямой доступ к массиву. но экономия памяти колоссальна. я показал это выше.
- решить систему А*В = Х
А 4000х4000 В - 4000 элементов. Проект по ссылке в посте 38 решал систему по методу Гаусса. Рзультаты получились довольно приемлимыми, однако не совпали с результатами полученными в SCILAB. Следует отметить что в исходной матрице А некоторые строки были полностью нулевыми, поэтому был ещё разработан алгоритм эффективного вычеркивания соотв строки и столбца...
0
valeriikozlov
Эксперт С++
4674 / 2500 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.03.2012, 02:45 #45
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
а как потом такую матрицу загнать в любой из существующих методов решения СЛАУ - в этом вся и соль...
Любой метод можно подогнать под любой вид матрицы. Будет такой метод работать медленнее чем для обычной матрицы.
Как всегда: выигрываем во времени - проигрываем в памяти. Выигрываем в памяти - проигрываем во времени.
0
03.03.2012, 02:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.03.2012, 02:45
Привет! Вот еще темы с ответами:

Как лучше всего разделить строку на несколько подстрок? - C++
Есть строка вида параметр1*параметр2*параметр3*параметр4. Как разделить эту строку, чтобы получить в первой переменной параметр1, во...

Как лучше всего пробежать все элементы контейнера? - C++
Речь о следующем. Есть vector. Я хочу пробежать все его элементы, но походу я буду проверять удовлетворяют они определенному условию или...

Как же все-таки лучше всего перегружать операторы? - C++
1. Нужно ли использовать friend там, где это возможно? (или не стоит злоупотреблять где-нибудь?) 2. Стоит ли при перегрузке бинарного...

Нужен совет: как лучше всего сгенерировать документ .doc с оформлением по ГОСТу - C++
Хай. Надо написать программу которая будет оформлять текст так сказать по госту(шрифт, размер интервал), была возможность вставлять туда...


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

Или воспользуйтесь поиском по форуму:
45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.