Контейнер с произвольным доступом, который не помещается в памяти?

У меня есть массив объектов (скажем, изображений), который слишком велик, чтобы поместиться в память (например, 40 ГБ). Но мой код должен иметь возможность случайного доступа к этим объектам во время выполнения.

Как лучше всего это сделать?

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

container.getObject(1242)->process();
container.getObject(479431)->process();

Но как мне реализовать этот контейнер? Должен ли он просто отправлять запросы в базу данных? Если да, то какой вариант будет лучшим? (Если база данных, то она должна быть бесплатной и не доставлять особых хлопот с администрированием, может быть, Berkeley DB или sqlite?)

Должен ли я просто реализовать это сам, запоминая объекты после доступа и очищая память, когда она заполнена? Или есть хорошие библиотеки (С++) для этого?

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

ОБНОВЛЕНИЕ: оказалось, что STXXL не работает для моей проблемы, потому что объекты, которые я храню в контейнере, имеют динамический размер, т.е. мой код может обновлять их (увеличивая или уменьшая размер некоторых объектов) во время выполнения . Но STXXL с этим не справится:

Контейнеры STXXL предполагают, что типы данных, которые они хранят, являются простыми старыми типами данных (POD). http://algo2.iti.kit.edu/dementiev/stxxl/report/node8.html

Не могли бы вы прокомментировать другие решения? А как насчет использования базы данных? И какой?


c++ database memory data-structures random-access
person Frank    schedule 25.01.2010    source источник
comment
Не зная больше о вашей проблеме, я бы сказал, что оба (чтение с диска и кэширование некоторых результатов или использование базы данных с кэшированием) являются хорошими решениями.   -  person BlueRaja - Danny Pflughoeft    schedule 25.01.2010
comment
Если вы изменяете объект, разве вы не создаете новый объект? Затем у вас либо есть старый и новый объект, либо вы удаляете старый и заменяете его новым объектом.   -  person codeDr    schedule 15.07.2011

Ответы (5)


arrow_upward
8
arrow_downward

Рассмотрите возможность использования STXXL:

Ядром STXXL является реализация стандартной библиотеки шаблонов C++ STL для вычислений во внешней памяти (вне ядра), т. е. STXXL реализует контейнеры и алгоритмы, которые могут обрабатывать огромные объемы данных, которые помещаются только на диски. В то время как совместимость с STL обеспечивает простоту использования и совместимость с существующими приложениями, другим приоритетом разработки является высокая производительность.

person James McNellis    schedule 25.01.2010
comment
Это выглядит красиво, но я не знаю, можно ли сказать ему кэшировать или предварительно загружать определенные результаты? Например, когда я получаю доступ к элементу n, вполне вероятно, что вскоре я получу доступ к некоторым элементам от n-100 до n+100, поэтому он должен загрузить и сохранить их в памяти. Может быть, мне нужно свое собственное решение в таком случае? - person Frank; 25.01.2010
comment
STXXL у меня не работает, смотрите обновление в моем вопросе. Любые другие идеи? - person Frank; 26.01.2010

arrow_upward
1
arrow_downward

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

person Liz Albin    schedule 25.01.2010

arrow_upward
1
arrow_downward

Я бы реализовал базовый кеш. С этим размером рабочего набора вы получите наилучшие результаты с set-associative-cache с x байтовыми строками кэша ( x == что лучше всего соответствует вашему шаблону доступа ). Просто реализуйте программно то, что каждый современный процессор уже имеет аппаратно. Это должно дать вам лучшие результаты. Вы могли бы оптимизировать его, если бы вы могли оптимизировать шаблон доступа, чтобы он был как-то линейным.

person DarthCoder    schedule 25.01.2010

arrow_upward
0
arrow_downward

Одним из решений является использование структуры, похожей на B-дерево, индексы и «страницы» массивов или векторов. Идея заключается в том, что индекс используется для определения того, какую страницу загрузить в память для доступа к вашей переменной.

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

person Thomas Matthews    schedule 25.01.2010

arrow_upward
0
arrow_downward

Я видел очень умный код, который перегружает operator[]() для выполнения доступа к диску на лету и прозрачной загрузки необходимых данных с диска/базы данных.

person SF.    schedule 26.01.2010
comment
Конечно, я спрашивал, стоит ли писать этот код самому (и если да, то каков наилучший подход: доступ к базе данных и т. д.?) или этот код доступен. - person Frank; 26.01.2010