Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.94/17: Рейтинг темы: голосов - 17, средняя оценка - 4.94
Stas0n
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
#1

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

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

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

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

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

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

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

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

52
thebvog
73 / 53 / 12
Регистрация: 20.02.2012
Сообщений: 239
26.02.2012, 19:22 #2
hello19, лучший вариант, по-моему, связанные списки.
C++
1
2
3
4
struct num {
        double value;
        num* prev, next;
}
Экономия памяти обеспечена.
0
Stas0n
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
27.02.2012, 01:17  [ТС] #3
Цитата Сообщение от thebvog Посмотреть сообщение
[b]
C++
1
        num* prev, next;
Экономия памяти обеспечена.
Что это строчка означает? Я так понимаю, что это что-то типа координат...
но как же потом с ними работать?
Вот допустим, что мне надо сделать какие-либо алгебраические операции с элементами одной строки... как это сделать?
0
CheshireCat
Эксперт С++
2912 / 1261 / 114
Регистрация: 27.05.2008
Сообщений: 3,463
27.02.2012, 10:33 #4
Напиши для себя раз и навсегда класс "разреженная матрица", лучше всего - шаблонный. А может, он уже кем-нибудь написан (погугли, задача-то типовая).... Там будет один-два некрупных архитектурных вопроса (типа "что делать, если запрошенный элемент не существует?"), но даже написание такого класса с нуля - ну, полдня.... с тестами - ну, еще полдня; итого день. Потом будешь многократно применять его "по месту", и все. Думать уже будет не надо. :-)
0
Stas0n
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
27.02.2012, 22:04  [ТС] #5
Цитата Сообщение от CheshireCat Посмотреть сообщение
Напиши для себя раз и навсегда класс "разреженная матрица", лучше всего - шаблонный. А может, он уже кем-нибудь написан (погугли, задача-то типовая).... Там будет один-два некрупных архитектурных вопроса (типа "что делать, если запрошенный элемент не существует?"), но даже написание такого класса с нуля - ну, полдня.... с тестами - ну, еще полдня; итого день. Потом будешь многократно применять его "по месту", и все. Думать уже будет не надо. :-)
я в проге не силен...
Можешь примерно накидать то, что должно быть?
0
AKE
11 / 11 / 3
Регистрация: 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
    };
0
Stas0n
3 / 4 / 1
Регистрация: 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;
0
thebvog
73 / 53 / 12
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 20:26 #8
hello19,
C++
1
2
         T     node; // Переменная с каким-то типом
         Item *next; // Указатель на следующий элемент типа Item
0
Stas0n
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 20:34  [ТС] #9
Цитата Сообщение от thebvog Посмотреть сообщение
hello19,
C++
1
2
         T     node; // Переменная с каким-то типом
         Item *next; // Указатель на следующий элемент типа Item
как с этим работать дальше?
Вот например, как мне считать из файла значения коэффициентов?
0
thebvog
73 / 53 / 12
Регистрация: 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;
    }
    ...
}
1
Stas0n
3 / 4 / 1
Регистрация: 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;
    }
    ...
}
0
thebvog
73 / 53 / 12
Регистрация: 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;
    }
    ...
}
Смысл таков: каждый элемент - структура указывает на следующей за ней элемент.
Вообщем лучше почитать про само понятие связанных списков.
0
Stas0n
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
28.02.2012, 20:59  [ТС] #13
а что за тип такой node в структуре?
0
thebvog
73 / 53 / 12
Регистрация: 20.02.2012
Сообщений: 239
28.02.2012, 21:02 #14
hello19, честно, не знаю, что под этой переменной имел ввиду AKE.

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

Как лучше всего реализовать настройки в программе?
Хочу грамотно сделать настройки для своей программы. Сейчас примерно так:...

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

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


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

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

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