| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Накладные расходы стандартных контейнеров |
| Автор: W4FhLF 7.3.2012, 17:39 |
| Есть у меня в программе двумерный массив, который хранит некоторые значения (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 байт на одну запись, что совсем неприемлемо. Кто какие решения может предложить? |
| Автор: boostcoder 7.3.2012, 18:57 | ||||
так то ж деревья. узлы содержат еще и другие члены, помимо твоих данных.
а в чем вопрос? |
| Автор: W4FhLF 7.3.2012, 19:11 |
| Вопрос как хранить полупустой массив (неважно, двумерный или одномерный, т.к. любой многомерный массив может быть представлен как одномерный) оптимально с точки зрения памяти и случайного доступа к элементам. |
| Автор: boostcoder 7.3.2012, 19:17 |
| т.к. массив полупустой, сэкономить можно на размере выделяемом под элемент. решение влоб - создать массив указателей, и выделять память каждому указателю только если он не пустой. таким образом, можно сэкономить по 4 байта на элемент в случае хранения указателей на double. время доступа идеальное. |
| Автор: rumit7 7.3.2012, 19:28 | ||
Может быть так http://evgeny-lazin.blogspot.com/2011/06/blog-post.html |
| Автор: W4FhLF 7.3.2012, 19:30 | ||
Таким образом ничего не экономится, даже наоборот. Добавлено через 4 минуты и 4 секунды rumit7, это не будет работать на массивах размером больше sizeof(int)*8 Добавлено через 5 минут и 42 секунды Точнее работать будет, если использовать что-то вроде std::bitset или свой вариант, но тогда накладные расходы на доступ будут огромные, хотя по памяти этот вариант выглядит интересно. |
| Автор: rumit7 7.3.2012, 19:59 | ||
Я сомневаюсь на счет огромных расходов. Во всяком случае, если std::bitset окажется столь медленным, то можно и свою реализацию заточить под данный проект. Если так подумать, то что такое свой bitset? Это массив 32-битных масок (на 64-битных системах можно и 64-битные маски хранить сразу). Нам нужны две операции: 1) доступ к конкретному биту (т.е. смещение внутри массива масок + битовая операция + иногда обновление маски) и 2) постоянный контроль кол-ва установленных бит для всего массива масок (ну это обычный целочисленный счетчик). Я думаю, выжав максимум можно приблизиться к оригинальному времени массива.. ну во всяком случае для двумерного массива - не проиграть слишком много.. |
| Автор: feodorv 7.3.2012, 20:22 | ||||
Чешу тыкву со времён http://forum.vingrad.ru/forum/topic-347698.html. Не пойму, почему дело ограничивается обычным целочисленным счётчиком:
bit - всегда степень двойки, а (bit-1) - двоичное число из i единиц. Таким образом, нужно считать число установленных бит в позициях (0,i-1) (для i > 0), а это для битового набора произвольной длины задача не столь тривиальная. В общем, одним целочисленным счётчиком не отделаться... |
| Автор: W4FhLF 7.3.2012, 20:24 |
| rumit7, для массива размером 1000000 в котором только половина значений нелувые у тебя будет 15625 64х битных числа, которые будут хранить маску и собственно массив из 500000 ненулевых элементов. Нужно обратить к i-му элементу. Как быстро вычислить его позицию в массиве ненулевых элементов? |
| Автор: borisbn 7.3.2012, 20:30 | ||
Debug или Release ? |
| Автор: feodorv 7.3.2012, 20:36 |
| Между прочим, в http://forum.vingrad.ru/index.php?showtopic=347698&view=findpost&p=2464927 была дана ссылка не некую библиотеку sparcelib++. Я её не смотрел, но, может, она решит проблему? |
| Автор: W4FhLF 7.3.2012, 20:45 | ||
| borisbn, release конечно. Добавлено через 2 минуты и 53 секунды
Судя по названию речь идёт о разряженных массивах. То есть когда количество ненулевых элементов много меньше общего числа элементов. |
| Автор: feodorv 7.3.2012, 21:29 | ||||
О "много меньше" там ни слова. Более того, даже если все элементы матрицы ненулевые, то всё равно библиотекой можно пользоваться (будут накладные расходы по памяти и доступу). Хранение данных там чуть более своеобразно, чем http://forum.vingrad.ru/index.php?showtopic=347698&view=findpost&p=2463818. В любом случае, пользоваться самой библиотекой смысла нет (уж больно она математизирована), но ведь можно подсмотреть, как она устроена  Добавлено через 6 минут и 53 секунды Всё же, возвращаясь к постановке задачи:
Насколько важна экономия памяти по сравнению со снижением скорости доступа? По-моему, лучше простого массива здесь ничего не придумаешь... |
| Автор: W4FhLF 7.3.2012, 22:03 |
| feodorv, с форматами хранения разряженных матриц я знаком. Они эффективны когда бОльшая часть элементов == 0, к тому же время доступа там в лучшем случае логарифмическое. По поводу того, что лучше двумерного массива ничего не найти я догадывался ещё до создания этой.  |
| Автор: feodorv 7.3.2012, 22:46 | ||||
Ага, понятно Меня смущает (даже больше чем "объём vs доступ") то, что там линейные массивы, размером в число ненулевых элементов. При добавлении нового ненулевого элемента можно нарваться на перезаказ памяти нехилого размера (а непрерывного участка памяти такого размера может и не оказаться в наличии после нескольких перезаказов...) Если же заранее известен размер двумерного массива, то ничего перезаказывать не нужно.
Гм. А где оно не логарифмическое?))) |
| Автор: W4FhLF 7.3.2012, 23:14 | ||||
Необязательно. Грубо говоря эти форматы делятся на те в которые можно быстро добавлять новые элементы, но при этом они медленные в плане перебора. И другой класс относится к форматам, структура которых не должна меняться, но их удобно использовать при необходимости обхода ненулевых элементов, например в операциях умножения матрицы на вектор. Обычно большие разряженные матрицы создаются с использованием одного формата и потом конвертируются в другой.
В хеш-таблице например. Это теория, на практике по моим тестам оно лишь в несколько раз меньше времени доступа к элементам std::map, которое в теории логарифмическое. |
