Что лучше, выделить много памяти или много указателей на память?

#графы #память #указатели #cpp

Есть задача, нужно создать взвешенный граф в виде матрицы смежности. Нужен int-массив,
который будет одновременно означать и связь и ее "цену". Ну так вот, весь прикол в
том, что (в реале) не все элементы будут связаны друг с другом, а значит некоторый
объем памяти лежать без дела => умнее будет создать массив указателей, и те элементы
которые не используются будут = NULL, т.е. память занимать не будет...Но опять же я
занимаю много памяти под адреса. Что же лучше? Вообще, указатели же имеет "вес"?    

Ответы

Ответ 1

У Кнута в первом томе есть пример, как можно хранить такие матрицы, достаточно экономно
и с возможностью быстро индексировать.
Для хранения одного элемента используется структура
struct Node {
  int row; // это и следующее поле можно и исключить
  int col; // ниже будет описана замена.
  Node * next;
  Node * bottom;
  Data data; // а это одно (или несколько  полей), где собственно хранятся данные.
}

Поэтому получается, что на каждый элемент нужно два дополнительных указателя (8-16
байт) и, возможно, ещё 4-8-16 байт для ускорения работы (и возможно отладки).
Индексы также не обязательно хранить в int. Вполне может оказаться, что short может
оказаться достаточным.
Данные хранятся следующем виде. Каждая нода хранит ссылку на следующую ноду в строке
и следующую ноду в столбце. Если в данной строке/столбце больше правее/ниже нет нод,
то хранится ссылка на самую верхнюю/левую, то есть, зацикливаем.
Если данных 4 байта, и система 32 битная, то уже при заполнении менее, чем на треть,
уже будет выигрыш.
Как работать с такой матрицей
Заводим один вектор, который будет хранить указатели на списки строк. Что бы найти
какой-то элемент по индексу, нужно просто в векторе взять нужную строку, а потом просто
пройтись по элементам до нахождения нужного. Если нужно посчитать сумму по строке -
также не сложно - просто нужно получить строку и суммировать элементы. Нулевых нет,
но они не меняют картины.
Но если размерности матрицы большие ( к примеру 100000 на 100000), то есть смысл
просто сделать список всех существующий строк и столбцов.
Подсуммировав все, получаем такое
struct Node {
  int row; 
  int col; 
  Node * next;
  Node * bottom;
  Data data; // а это одно (или несколько  полей), где собственно хранятся данные.
}
std::list rows;
std::list cols;

// дальше алгоритмы словесные.
Node * get(int i, int j) {
   // Пройтись циклом по rows до нужной строки.
   // Если такой строки  нет, значит элемент нулевой
   // иначе проходим по строке (используя указатель next), ищем нужный элемент.
}

// Добавление элемента.
void add(Node * n) {

   // Находим нужную строку. Если строки в списке rows нет, нужно вставить.
   // добавляем этот элемент в эту строку.
   // если строка есть, то проходим циклом, что бы найти место вставки, 
   // поправляем два указателя
   // аналогичное проделываем с столбцами.
}
// удаление аналогично.

Возможно я немного модифицировал идею Кнута, поэтому настойчиво  рекомендую взять
его книгу и поискать (думаю легко по заголовкам найдется, первый том).
Также в книге рекомендуется создать свой пул объектов, если предполагается, что данные
будут часто модифицироваться.
Ещё раз напомню, данный алгоритм будет очень эффективным, если кол-во элементов значительно
( в сотни раз) меньше общей вместимости матрицы.


Ответ 2

Два стандартных представления связей в графе это 1) матрица, где элемент (i,j) указывает
есть ли связь между i-ой и j-ой вершинами и 2) массив списков, где i-ый элемент массива
содержит список связный с ним вершин. Если связи (i,j) в графе нет, то в i-ом списке
не будет элемента j.
Оба подхода имеют плюсы и минусы. Плюс второго подхода в экономии памяти.


Ответ 3

Это называется сильно разреженными матрицами, рассматривалось, к примеру, Кнутом.
Есть давнишняя книжка Писанецки строго на эту тему


Ответ 4

Просто создайте указатель на указатель ;) **