Есть у меня в программе двумерный массив, который хранит некоторые значения (POD типы), допустим double. Известно, что размер массива по одному из измерений не превышает максимальное значение unsigned short.
Строятся эти массивы один раз и новые элементы в них добавляются нечасто. А вот обращение к ij-ому элементу осуществляется десятки и сотни миллионов раз.

Проблема в том, что в большинстве случаев заполнены они только на 30-70%
Т.е. массивы могут занимать приличный объём (например 10000*10000*sizeof(double) = 800 мб) и экономия получается весьма ощутима если отбросить пустые элементы.

Ну думаю дай засуну их в какой-нибудь стандартный контейнер типа std::map<unsigned, double> или std::unordered_map<unsigned, double>. В конце-концов у последнего сложность О(1), что выглядит совсем как массив, хотя на практике конечно же медленнее. В качестве ключа всегда можно сделать: key = j + i*cols_num, где i,j - строка и столбец массива, соответственно.

Каково же было моё удивление, когда я обнаружил, что контейнеры эти занимают в ~10 раз больше памяти, чем массив. Т.е. даже массив, который заполнен только на 30%, будет занимать в 3 раза меньше памяти, чем map или unordered_map. Это в Visual C++ 2010.

Размер элемента в контейнерах можно выразить как:
(sizeof(key) + sizeof(value) + factor)
Этот фактор зависит от реализации библиотеки, в моём случае составляет порядка 60 байт на одну запись, что совсем неприемлемо.

Кто какие решения может предложить? 

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

так то ж деревья. узлы содержат еще и другие члены, помимо твоих данных.


а в чем вопрос?

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

Это сообщение отредактировал(а) W4FhLF - 7.3.2012, 20:26

т.к. массив полупустой, сэкономить можно на размере выделяемом под элемент.
решение влоб - создать массив указателей, и выделять память каждому указателю только если он не пустой.
таким образом, можно сэкономить по 4 байта на элемент в случае хранения указателей на double.
время доступа идеальное.

Может быть так http://evgeny-lazin.blogspot.com/2011/06/blog-post.html

Таким образом ничего не экономится, даже наоборот.

Добавлено через 4 минуты и 4 секунды
rumit7, это не будет работать на массивах размером больше sizeof(int)*8

Добавлено через 5 минут и 42 секунды
Точнее работать будет, если использовать что-то вроде std::bitset или свой вариант, но тогда накладные расходы на доступ будут огромные, хотя по памяти этот вариант выглядит интересно. 

Это сообщение отредактировал(а) W4FhLF - 7.3.2012, 19:31

Я сомневаюсь на счет огромных расходов. Во всяком случае, если std::bitset окажется столь медленным, то можно и свою реализацию заточить под данный проект. Если так подумать, то что такое свой bitset? Это массив 32-битных масок (на 64-битных системах можно и 64-битные маски хранить сразу). Нам нужны две операции: 1) доступ к конкретному биту (т.е. смещение внутри массива масок + битовая операция + иногда обновление маски) и 2) постоянный контроль кол-ва установленных бит для всего массива масок (ну это обычный целочисленный счетчик).

Я думаю, выжав максимум можно приблизиться к оригинальному времени массива.. ну во всяком случае для двумерного массива - не проиграть слишком много..

Чешу тыкву со времён этой ветки. Не пойму, почему дело ограничивается обычным целочисленным счётчиком:
bit - всегда степень двойки, а (bit-1) - двоичное число из i единиц. Таким образом, нужно считать число установленных бит в позициях (0,i-1) (для i > 0), а это для битового набора произвольной длины задача не столь тривиальная. В общем, одним целочисленным счётчиком не отделаться...

rumit7, для массива размером 1000000 в котором только половина значений нелувые у тебя будет 15625 64х битных числа, которые будут хранить маску и собственно массив из 500000 ненулевых элементов. Нужно обратить к i-му элементу. Как быстро вычислить его позицию в массиве ненулевых элементов?

Debug или Release ?

Между прочим, в той ветке была дана ссылка не некую библиотеку sparcelib++. Я её не смотрел, но, может, она решит проблему?

borisbn, release конечно.

Добавлено через 2 минуты и 53 секунды

Судя по названию речь идёт о разряженных массивах. То есть когда количество ненулевых элементов много меньше общего числа элементов.

О "много меньше" там ни слова. Более того, даже если все элементы матрицы ненулевые, то всё равно библиотекой можно пользоваться (будут накладные расходы по памяти и доступу). 
Хранение данных там чуть более своеобразно, чем прямой путь решения. В любом случае, пользоваться самой библиотекой смысла нет (уж больно она математизирована), но ведь можно подсмотреть, как она устроена 

Добавлено через 6 минут и 53 секунды
Всё же, возвращаясь к постановке задачи:



Насколько важна экономия памяти по сравнению со снижением скорости доступа? По-моему, лучше простого массива здесь ничего не придумаешь...

feodorv, с форматами хранения разряженных матриц я знаком. Они эффективны когда бОльшая часть элементов == 0, к тому же время доступа там в лучшем случае логарифмическое. 

По поводу того, что лучше двумерного массива ничего не найти я догадывался ещё до создания этой. 

Ага, понятно   

Меня смущает (даже больше чем "объём vs доступ") то, что там линейные массивы, размером в число ненулевых элементов. При добавлении нового ненулевого элемента можно нарваться на перезаказ памяти нехилого размера (а непрерывного участка памяти такого размера может и не оказаться в наличии после нескольких перезаказов...)

Если же заранее известен размер двумерного массива, то ничего перезаказывать не нужно.


Гм. А где оно не логарифмическое?)))