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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.92
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
26.02.2012, 13:58     Как лучше всего хранить коэффициенты? #1
Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
01.03.2012, 20:31     Как лучше всего хранить коэффициенты? #21
Цитата Сообщение от hello19 Посмотреть сообщение
Матрица системы - сильноразреженная. По этому нет смысла хранить все элементы, т.к. большая их часть просто нули.
если тебе не важна скорость
все эти динам массивы списки работают гораздо медленнее
ну это извечный вопрос скорость/память
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 20:32     Как лучше всего хранить коэффициенты? #22
ValeryS, да, медленнее в 4 раза где-то, но если экономия памяти превышает это число то очень полезно.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 20:32  [ТС]     Как лучше всего хранить коэффициенты? #23
Цитата Сообщение от thebvog Посмотреть сообщение
hello19, как мне кажется, можно сделать обычный динамический массив (можно vector), и каждый раз где надо использовать коэффициент, сравнивать, если индекс элемента динамического коэффициента равен индексу коэффициента, то подставляем и прибавляем счётчик текущего индекса динам. массива, иначе вставляем 0, и переходим к следующему. Если я правильно вас понял.
Можете на коде показать?
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 20:35     Как лучше всего хранить коэффициенты? #24
hello19, могу для обычного уравнения, а это эти я не помню.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 20:35  [ТС]     Как лучше всего хранить коэффициенты? #25
да ну хоть как... просто глазами увидеть..
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 20:43     Как лучше всего хранить коэффициенты? #26
hello19,
C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct k {
    double value;
    int cow, row;
}
 
...
 
int main()
{
   // Ввели коэффициенты
   int n, i;
   cin>>n;
   table = new k[n];
   for (i=0;i<n;i++)
   {
       cin>>k[n]->value;
       cin>>k[n]->row;
       cin>>k[n]->cow;
   }
   ...
   int x, y;
   int cow, row; // текущие строка и столбец
   int kp = 0; // текущий коэффициент
   cow=k[kp]->cow;
   row=k[kp]->row;
   for (y=0;y<TABLE_Y;y++)
       for (x=0;i<TABLE_X;x++)
       {
           if ((x==row) && (y==cow))
           {
               // Вставляем коэффициент
               print("%d",k[kp]->value);
               kp++;
               cow=k[kp]->cow;
               row=k[kp]->row;
           }
       }
 
    return 0;
}
Как-то так, не тестировал.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 20:52  [ТС]     Как лучше всего хранить коэффициенты? #27
а какие входные данные?
вот скажем, если у меня вот такая система уравнений:
1*x1 + 2x3 = 3
x2 = 5
x3 = 1
как лучше всего хранить ненулевые коэффициенты?
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 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.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 20:59  [ТС]     Как лучше всего хранить коэффициенты? #29
вот, да.. это было бы замечательно.. но как это сделать?
Xind
275 / 148 / 7
Регистрация: 05.11.2011
Сообщений: 425
Записей в блоге: 1
01.03.2012, 21:01     Как лучше всего хранить коэффициенты? #30
Если интересно, то есть еще один способ, предложенный в книжке Мозговой М. C++ Мастер-класс. 85 нетривиальных проектов, решений и задач раздел 1.2 Разреженные матрицы там показан пример класса, в нем используются map и pair.
thebvog
 Аватар для 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 и соответствующее им значение коэффициента.
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-м месте...
thebvog
 Аватар для 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);
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)
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 21:20     Как лучше всего хранить коэффициенты? #35
hello19, просто добавить условие сравнивания ещё и cow.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 21:24  [ТС]     Как лучше всего хранить коэффициенты? #36
ммм... вообщем тут есть еще над чем подумать.. в субботу продолжу спасибо!
thebvog
01.03.2012, 21:27
  #37

Не по теме:

hello19, не за что

-=ЮрА=-
Заблокирован
Автор 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/thread4...ml#post2431657

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


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

Не по теме:

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

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 будет храниться значение.

Если матрица симметричная, то алгоритмы еще интереснее. А если к тому же и ленточная (все ненулевые элементы близко к диагонали), то там крайне эффективные схемы хранения есть.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.03.2012, 02:15     Как лучше всего хранить коэффициенты?
Еще ссылки по теме:

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

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

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

Paporotnik, если есть настоящие соображения по матрицам и СЛАУ с готовностью выслушаю!
Yandex
Объявления
03.03.2012, 02:15     Как лучше всего хранить коэффициенты?
Ответ Создать тему
Опции темы

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