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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.92
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
26.02.2012, 13:58     Как лучше всего хранить коэффициенты? #1
Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
26.02.2012, 19:22     Как лучше всего хранить коэффициенты? #2
hello19, лучший вариант, по-моему, связанные списки.
C++
1
2
3
4
struct num {
        double value;
        num* prev, next;
}
Экономия памяти обеспечена.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
27.02.2012, 01:17  [ТС]     Как лучше всего хранить коэффициенты? #3
Цитата Сообщение от thebvog Посмотреть сообщение
[b]
C++
1
        num* prev, next;
Экономия памяти обеспечена.
Что это строчка означает? Я так понимаю, что это что-то типа координат...
но как же потом с ними работать?
Вот допустим, что мне надо сделать какие-либо алгебраические операции с элементами одной строки... как это сделать?
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
27.02.2012, 10:33     Как лучше всего хранить коэффициенты? #4
Напиши для себя раз и навсегда класс "разреженная матрица", лучше всего - шаблонный. А может, он уже кем-нибудь написан (погугли, задача-то типовая).... Там будет один-два некрупных архитектурных вопроса (типа "что делать, если запрошенный элемент не существует?"), но даже написание такого класса с нуля - ну, полдня.... с тестами - ну, еще полдня; итого день. Потом будешь многократно применять его "по месту", и все. Думать уже будет не надо. :-)
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
27.02.2012, 22:04  [ТС]     Как лучше всего хранить коэффициенты? #5
Цитата Сообщение от CheshireCat Посмотреть сообщение
Напиши для себя раз и навсегда класс "разреженная матрица", лучше всего - шаблонный. А может, он уже кем-нибудь написан (погугли, задача-то типовая).... Там будет один-два некрупных архитектурных вопроса (типа "что делать, если запрошенный элемент не существует?"), но даже написание такого класса с нуля - ну, полдня.... с тестами - ну, еще полдня; итого день. Потом будешь многократно применять его "по месту", и все. Думать уже будет не надо. :-)
я в проге не силен...
Можешь примерно накидать то, что должно быть?
AKE
11 / 11 / 0
Регистрация: 09.05.2010
Сообщений: 384
27.02.2012, 22:25     Как лучше всего хранить коэффициенты? #6
C++
1
2
3
4
5
6
    struct Item{
     T     node;
         Item *next;
     int i; //string
     int j; //column
    };
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 20:22  [ТС]     Как лучше всего хранить коэффициенты? #7
Цитата Сообщение от AKE Посмотреть сообщение
C++
1
2
3
4
5
6
    struct Item{
     T     node;
         Item *next;
     int i; //string
     int j; //column
    };
не могли бы вы пояснить код...
Что за строчки:
C++
1
2
     T     node;
         Item *next;
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 20:26     Как лучше всего хранить коэффициенты? #8
hello19,
C++
1
2
         T     node; // Переменная с каким-то типом
         Item *next; // Указатель на следующий элемент типа Item
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 20:34  [ТС]     Как лучше всего хранить коэффициенты? #9
Цитата Сообщение от thebvog Посмотреть сообщение
hello19,
C++
1
2
         T     node; // Переменная с каким-то типом
         Item *next; // Указатель на следующий элемент типа Item
как с этим работать дальше?
Вот например, как мне считать из файла значения коэффициентов?
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 20:42     Как лучше всего хранить коэффициенты? #10
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
        struct Item{
         T     node;
         Item *next;
         int value;
         int i; //string
         int j; //column
        };
 
int main()
{
    ...
    Item *p;
    Item *begin;
    p = new Item;
    p->next = NULL;
    begin  = p;
    while (cin>>a)
    {
        p->value = a;
        p->next = new Item;
        p = p->next;
        p->next = NULL;
    }
    ...
}
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 20:48  [ТС]     Как лучше всего хранить коэффициенты? #11
Все-таки хочется узнать, что это за типы:
C++
1
2
3
  
         T     node;
         Item *next;
А так же интересно, вот что тут происходит. Я так понимаю, что тут обычное считывание.. Но уж непонятны строчки... если сможете, сделайте комментарии к ним..
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
int main()
{
    ...
    Item *p;
    Item *begin;
    p = new Item;
    p->next = NULL;
    begin  = p;
    while (cin>>a)
    {
        p->value = a;
        p->next = new Item;
        p = p->next;
        p->next = NULL;
    }
    ...
}
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 20:55     Как лучше всего хранить коэффициенты? #12
hello19, мы создали структуру Item.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    ...
    Item *p; // Создаем указатель на неё, а не на саму структуру
    Item *begin; // начало массива, тоже указатель
    p = new Item; // Создаем первый элемент в памяти, а переменная p указывает на неё
    p->next = NULL;
    begin  = p;
    while (cin>>a)
    {
        p->value = a; // Текущей структуру, на которую указывает p присваеваем value значение a
        p->next = new Item; // Создаем следующую структуру
        p = p->next; // И делаем указатель и с первой структуры на вторую
        p->next = NULL;
    }
    ...
}
Смысл таков: каждый элемент - структура указывает на следующей за ней элемент.
Вообщем лучше почитать про само понятие связанных списков.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 20:59  [ТС]     Как лучше всего хранить коэффициенты? #13
а что за тип такой node в структуре?
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 21:02     Как лучше всего хранить коэффициенты? #14
hello19, честно, не знаю, что под этой переменной имел ввиду AKE.

Думаю можно и без неё, главное принцип понять.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 21:13  [ТС]     Как лучше всего хранить коэффициенты? #15
Да принцип то давно понял.. вот реализация хромает дико...
Вот у меня вопрос, можно ли сделать вот такую вот структурку:
C++
1
2
3
4
5
6
7
    struct elements
    {
        int one; // строка
        int two; // столбец
        double three; // значение коэффициента
    };
        vector <elements> matrix;
Вот только не соображу как тут хранить элементы так, чтобы нулевые элементы не хранить...
допустим мне нужно записать элементы первой строки, первого и 4-го столбцов...
Ну, допустим, что как нить их я считаю. Дальше мне с ними нужно будет делать преобразования... как минимум - запускать цикл..
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 21:24     Как лучше всего хранить коэффициенты? #16
hello19, да, это будет работать. Всё зависит от того, как вы к ним собираетесь обращаться.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 12:24  [ТС]     Как лучше всего хранить коэффициенты? #17
да там вроде бы ничего сложного...
C++
1
2
3
matrix[i].one // обращение к строке
matrix[i].two // обращение с столбцу
matrix[i].three // обращение к значению коэффициенту матрицы
единственное, что меня напрягает, так это то, что... вот мне придется делать кое какие преобразования с коэффициентам, стоящими в каждой отдельной строке...
Там нужно будет сделать что-то типа цикла.. не соображу, как можно это реализовать....

Добавлено через 1 час 23 минуты
Не соображу, как сделать функцию доступа к нужным элементам...
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 20:19     Как лучше всего хранить коэффициенты? #18
hello19, нет, я не это имею ввиду (программную реализацию я знаю). Вы можете сказать задачу, в которой вам нужно использовать динамический массив, я хочу понять что вам лучше использовать.
Stas0n
3 / 4 / 0
Регистрация: 13.07.2011
Сообщений: 313
01.03.2012, 20:21  [ТС]     Как лучше всего хранить коэффициенты? #19
задача следующая - решить систему уравнений итерационным методом. Матрица системы - сильноразреженная. По этому нет смысла хранить все элементы, т.к. большая их часть просто нули.
Я хочу хранить лишь ненулевые элементы и уже с ними работать...
Вот только не знаю, как лучше их хранить...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.03.2012, 20:27     Как лучше всего хранить коэффициенты?
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
thebvog
 Аватар для thebvog
73 / 53 / 3
Регистрация: 20.02.2012
Сообщений: 239
01.03.2012, 20:27     Как лучше всего хранить коэффициенты? #20
hello19, как мне кажется, можно сделать обычный динамический массив (можно vector), и каждый раз где надо использовать коэффициент, сравнивать, если индекс элемента динамического коэффициента равен индексу коэффициента, то подставляем и прибавляем счётчик текущего индекса динам. массива, иначе вставляем 0, и переходим к следующему. Если я правильно вас понял.
Yandex
Объявления
01.03.2012, 20:27     Как лучше всего хранить коэффициенты?
Ответ Создать тему
Опции темы

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