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

Хрантите 2 массива: один для double значений, другой для их индексов.
count означает число ненулевых элементов матрицы, reserved - число элементов, под которое выделена память (count <= reserved). Плюс подпрограмма бинарного поиска элемента с данным индексом. Плюс подпрограммы вставки/удаления элементов.

Гм. Только что дошло: у Вас матрица многомерная? Это немного более сложный случай...

Нет, матрица обычная 100 000 * 100 000

Что-то не соображу как реализовать поиск элементов...

Если размер матрицы фиксирован, то её можно превратить в линейный список: [i][j] => [i*N+j], хотя 100 000 * 100 000 в int уже не влезают... Тогда можно хранить два набора индексов:



Список индексов - отсортированный, поэтому можно воспользоваться бинарным поиском:
Если элемент [x][y] не найден, значит его значение 0.0, иначе m->values[*pindex].

Добавлено @ 14:48
Аналогично пишется spmatrixAdd( m, x, y, value):

• делаем spmatrixFind( m, x, y, &index)
• если такой элемент найден, заменяете его значение на value (на этом всё)
• если не найден, то тогда имеем индекс, куда нужно производить вставку (чтобы сохранить отсортированность матричных индексов)
• 1. проверяем, есть ли свободная память в списках (m->count < m->reserved); если нет, то увеличиваем значение для reserved и перезаказываем память на все три списка (m->values, m->x, m->y) (или заказываем память, если reserved был нулевой)
• 2. сдвигаем списки с [index] до [count-1] включительно на одну позицию вправо (освобождаем место в позиции index)
• 3. помещаем значания x, y, value в освободившуюся позицию index
• 4. count увеличиваем на 1

Это сообщение отредактировал(а) feodorv - 29.2.2012, 15:15

Если нет желания возиться с отсортированным списком индексов, тогда можно в лоб сравнивать все пары m->x[i], m->y[i] с x, y. Но это потребует много времени...

Если же ненулевых значений мотрицы не так уж и мало (>10000), то можно воспользоваться (например) красно-чёрным деревом для хранения ненулевых значений матрицы, тогда каждый лист дерева будет содержать набор (x,y,value). Дерево удобнее тем, что при добавлении новых ненулевых элементов не нужно будет перезаказывать память (правда, и потребует больше памяти по сравнению со списками).

Это сообщение отредактировал(а) feodorv - 26.2.2012, 15:00

Может быть вам будет интересно решение описанное здесь http://evgeny-lazin.blogspot.com/2011/06/blog-post.html

Да, решение интересное (подобно можно организовать нечёткий поиск подстроки длинной не более 32 символов в строке произвольной длины). Но:

Что-то я не очень понимаю в чем проблема? std::bitset и разные другие готовые штучки уже не в моде?

Технически, наверное, проще всего будет организовать массив 10^5 указателей (так что доступ по одной координате будет "прямым"), на которые повесить деревья (те же красно-черные или сразу B-), обеспечивающие поиск по второй координате. Скорость доступа по сравнению с чисто древесным вариантом будет в среднем в два раза больше, а одномерный массив из 10^5 указателей - это пустяк даже при 64-битной адресации. В принципе, если памяти не очень жалко, можно сделать аналогичную вещь, "сбросив" в линейный доступ еще и часть второй координаты (когда каждое дерево будет содержать не полную строку или столбец, а лишь некоторую часть).

Я бы первом делом попробовал на std::map, (или лучше на хеш.мап), что нибудь организовать.
на записи поставить иф. если нулевой коэф, просто не записывать в мап.
на чтении, обратное, если нет в мапе, возвращать 0.


Это сообщение отредактировал(а) volatile - 26.2.2012, 20:16

Ну да, map (хэш-мап) с ключом pair <int, int>.

Тут вопрос в том, насколько она разреженная?
Если там допустим половина элементов НЕ нулевые, то в итоге с map мы только теряем.
std::map - это +3 указателя для каждого НЕ нулевого элемента да еще плюс к нему сам индекс, а это немало, в итоге может выйти так, что расход будет больше, чем при обычной матрице, да еще и поиск становиться не константным.


В данном случае опять такие теряется константность поиска, но если хранить массив индексов отсортированным, то можно будет применить бинарный поиск.

Мне кажется данных мало для однозначного ответа.

hello19
Что для тебя важнее? Скорость нахождения элемента или размер расходуемой памяти, какой процент нулевых элементов ожидается в матрице?
Что предполагается делать с матрицей? Какие действия?

Ещё зависит от того, где расположен ненулевые элементы.
Если ненулевые элементы находятся около главной диалогали - хранить по диагоналям полностью.
индекс диагонали - (x-y-minDiagonal), индекс на диагонали - max(x,y);

Если ненулевые элементы расположены блоками возле определеных координат


Добавлено через 12 минут и 50 секунд
При делении на блоки для поиска удобно, чтобы они были одного размера и выравнены по своему размеру:

http://math.nist.gov/sparselib++/