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

@Stas0n · Регистрация: 13.07.2011

Author24 — интернет-сервис помощи студентам

Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double

ValeryS · 01.03.2012, 20:31

Сообщение от hello19

Матрица системы - сильноразреженная. По этому нет смысла хранить все элементы, т.к. большая их часть просто нули.

если тебе не важна скорость
все эти динам массивы списки работают гораздо медленнее
ну это извечный вопрос скорость/память

@thebvog · 01.03.2012, 20:32

ValeryS, да, медленнее в 4 раза где-то, но если экономия памяти превышает это число то очень полезно.

@Stas0n · 01.03.2012, 20:32 **[ТС]**

Сообщение от thebvog

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

Можете на коде показать?

@thebvog · 01.03.2012, 20:35

hello19, могу для обычного уравнения, а это эти я не помню.

@Stas0n · 01.03.2012, 20:35 **[ТС]**

да ну хоть как... просто глазами увидеть..

@thebvog · 01.03.2012, 20:43

hello19,

C++

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 · 01.03.2012, 20:52 **[ТС]**

а какие входные данные?
вот скажем, если у меня вот такая система уравнений:
1*x1 + 2x3 = 3
x2 = 5
x3 = 1
как лучше всего хранить ненулевые коэффициенты?

@thebvog · 01.03.2012, 20:56

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 · 01.03.2012, 20:59 **[ТС]**

вот, да.. это было бы замечательно.. но как это сделать?

@Xind · 01.03.2012, 21:01

Если интересно, то есть еще один способ, предложенный в книжке Мозговой М. C++ Мастер-класс. 85 нетривиальных проектов, решений и задач раздел 1.2 Разреженные матрицы там показан пример класса, в нем используются map и pair.

@thebvog · 01.03.2012, 21:01

hello19, как я показал выше. Вводим 1:1, 3:1, 4:1, 2:2, 4:2, 3:3, 4:3 и соответствующее им значение коэффициента.

@Stas0n · 01.03.2012, 21:07 **[ТС]**

Сообщение от 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++

    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 · 01.03.2012, 21:12

hello19, умножить на 2 можно так:

C++

do
{
    k[i]->value *= 2;
} while (k[i]->row == ROW);

@Stas0n · 01.03.2012, 21:17 **[ТС]**

а, скажем, если мне надо 1 и 3 умножить на 2, а последний разделить на 2..
и что означает эта строчка:

C++

1	while (k[i]->row == ROW)

@thebvog · 01.03.2012, 21:20

hello19, просто добавить условие сравнивания ещё и cow.

@Stas0n · 01.03.2012, 21:24 **[ТС]**

ммм... вообщем тут есть еще над чем подумать.. в субботу продолжу спасибо!

@thebvog · 01.03.2012, 21:27

Не по теме:

hello19, не за что :)

@~~-=ЮрА=-~~ · 03.03.2012, 01:26

hello19, ты на неверном пути. Лучше того что мы паяли с тобой летом врядли можно без спец методов решения СЛАУ высокого порядка решить.
Смотри у нас было 4000х4000 элементов - это ~ 128000000 байт (122 Мб), виртуалка уже начинала трещать. Теперь ты вводишь структуру

Сообщение от hello19

struct elements
* * * * {
* * * * * * * * int one; // строка
* * * * * * * * int two; // столбец
* * * * * * * * double three; // значение коэффициента
* * * * };
* * * * vector <elements> matrix(N)

- у тебя в 3 раза выростет объём виртуалки (т.к. в структуре 3 поля) 3х122 = 366 Мб (с таким динамическим монстром не всякое железо справится).
Я тебе предлагаю подождать недельку, я как раз расмотрю методы решения СЛАУ высокого порядка здесь https://www.cyberforum.ru/faq/... ost2431657

Сообщение от -=ЮрА=-

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

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

Не по теме:

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

@Paporotnik · 03.03.2012, 02:07

для хранения разреженных матриц методов много. одни сильно выигрывают по памяти, но уступают по скорости "распаковки", другие - наоборот.
если матрица у нас 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, 02:15

Сообщение от Paporotnik

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

- там ничего такого нет(по крайней мере заметить это нереально ввиду колоссального объёма матрицы).
Вот тот топик
Решить систему алгебраических линейных неоднородных уравнени
я даю ссылку на проект на котором по памяти остановились.

Paporotnik, если есть настоящие соображения по матрицам и СЛАУ с готовностью выслушаю!

@Stas0n 3 / 4 / 1 Регистрация: 13.07.2011 Сообщений: 313
	01.03.2012, 20:59 [ТС]	29
	вот, да.. это было бы замечательно.. но как это сделать? 0

@Xind 277 / 150 / 25 Регистрация: 05.11.2011 Сообщений: 429 Записей в блоге: 1
	01.03.2012, 21:01	30
	Если интересно, то есть еще один способ, предложенный в книжке Мозговой М. C++ Мастер-класс. 85 нетривиальных проектов, решений и задач раздел 1.2 Разреженные матрицы там показан пример класса, в нем используются map и pair. 1

@~~-=ЮрА=-~~ Заблокирован
	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 Мб (с таким динамическим монстром не всякое железо справится). Я тебе предлагаю подождать недельку, я как раз расмотрю методы решения СЛАУ высокого порядка здесь https://www.cyberforum.ru/faq/... ost2431657 Сообщение от -=ЮрА=- Содержание FAQ ... 4.5 Класс Матрица. 5 Системы линейных алгебраических уравнений(СЛАУ) 5.1 Метод Гаусса 5.2 Матричный способ решения 5.3 Метод Крамера 5.4 Решение СЛАУ высокого порядка 6 Геометрические задачи 7 Распознавание ручного ввода задания аналитических зависимостей Не по теме: hello19, просто поверь ты сейчас на неверном пути. Никакого выиграша структуры тебе не дадут. У тебя есть Гаусс(лучше его в плане производительности для не спец методов на мой взгляд нет!). Для разрежённых матриц думаю напаять метод с обобщённым правилом Саррюса для определителя n-го порядка, может откопаю где-то норм описание спец методов тога будет настоящий алгоритм... 0

@Paporotnik 385 / 229 / 12 Регистрация: 06.07.2011 Сообщений: 512
	03.03.2012, 02:07	39
	для хранения разреженных матриц методов много. одни сильно выигрывают по памяти, но уступают по скорости "распаковки", другие - наоборот. если матрица у нас NN и в ней k ненулевых элементов, то есть метод, позволяющий хранить 2k значений для сохранения данных о матрице. алгоритм таков: пусть дана матрица: 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

@Stas0n 3 / 4 / 1 Регистрация: 13.07.2011 Сообщений: 313
		1
	Как лучше всего хранить коэффициенты? 26.02.2012, 13:58. Показов 4576. Ответов 52 Метки нет (Все метки) Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти? Элементы матрицы типа double 0

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,521
	01.03.2012, 20:31	21
	Сообщение от hello19 Матрица системы - сильноразреженная. По этому нет смысла хранить все элементы, т.к. большая их часть просто нули. если тебе не важна скорость все эти динам массивы списки работают гораздо медленнее ну это извечный вопрос скорость/память 0

@thebvog 74 / 54 / 12 Регистрация: 20.02.2012 Сообщений: 239
	01.03.2012, 20:32	22
	ValeryS, да, медленнее в 4 раза где-то, но если экономия памяти превышает это число то очень полезно. 0

@Stas0n 3 / 4 / 1 Регистрация: 13.07.2011 Сообщений: 313
	01.03.2012, 20:32 [ТС]	23
	Сообщение от thebvog hello19, как мне кажется, можно сделать обычный динамический массив (можно vector), и каждый раз где надо использовать коэффициент, сравнивать, если индекс элемента динамического коэффициента равен индексу коэффициента, то подставляем и прибавляем счётчик текущего индекса динам. массива, иначе вставляем 0, и переходим к следующему. Если я правильно вас понял. Можете на коде показать? 0

@thebvog 74 / 54 / 12 Регистрация: 20.02.2012 Сообщений: 239
	01.03.2012, 20:35	24
	hello19, могу для обычного уравнения, а это эти я не помню. 0

@Stas0n 3 / 4 / 1 Регистрация: 13.07.2011 Сообщений: 313
	01.03.2012, 20:35 [ТС]	25
	да ну хоть как... просто глазами увидеть.. 0

@Stas0n 3 / 4 / 1 Регистрация: 13.07.2011 Сообщений: 313
	01.03.2012, 20:52 [ТС]	27
	а какие входные данные? вот скажем, если у меня вот такая система уравнений: 1*x1 + 2x3 = 3 x2 = 5 x3 = 1 как лучше всего хранить ненулевые коэффициенты? 0

@thebvog 74 / 54 / 12 Регистрация: 20.02.2012 Сообщений: 239
	01.03.2012, 20:56	28
	hello19, 1x1 + 2x3 = 3 x2 = 5 x3 = 1 Если правильно понял, то в полной форме примерно так: 1x1 + 0x2 + 2x3 = 3 0x1 + 1x2 + 0x3 = 5 0x1 + 0x2 + 1*x3 = 1 И вот матрица 4 на 3, а храним только элементы с позицией, 1:1, 3:1, 4:1, 2:2, 4:2, 3:3, 4:3. 0

@thebvog 74 / 54 / 12 Регистрация: 20.02.2012 Сообщений: 239
	01.03.2012, 21:20	35
	hello19, просто добавить условие сравнивания ещё и cow. 1

@Stas0n 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, 02:15	40
	Сообщение от Paporotnik Если матрица симметричная, то алгоритмы еще интереснее. А если к тому же и ленточная (все ненулевые элементы близко к диагонали), то там крайне эффективные схемы хранения есть. - там ничего такого нет(по крайней мере заметить это нереально ввиду колоссального объёма матрицы). Вот тот топик Решить систему алгебраических линейных неоднородных уравнени я даю ссылку на проект на котором по памяти остановились. Paporotnik, если есть настоящие соображения по матрицам и СЛАУ с готовностью выслушаю! 0