Структура данных для хранения огромного количества данных?

Ответ 1

Простейшим решением вашей проблемы будет использование 64-битных адресных пространств - современные Mac, поддерживающие это из коробки, в Windows и Linux вам потребуется установить 64-разрядную версию ОС. Я считаю, что Qt можно использовать для создания 64-битных приложений довольно хорошо. 32-битные системы не смогут поддерживать единичные распределения размера, о котором вы говорите, - даже Mac с 4 ГБ адресного пространства, доступным для приложений, не сможет сделать ни одного 3,7 ГБ распределения, поскольку не будет быть смежным пространством такого размера.

Для отмены я бы посмотрел на файлы с отображением памяти и копирование на запись для копирования блока:

http://en.wikipedia.org/wiki/Copy-on-write

Это означает, что на самом деле вам не нужно копировать все исходные данные, система будет делать копии страниц по мере их написания. Это значительно улучшит производительность, если ваши изображения значительно больше реальной памяти, и вы не меняете каждую часть изображения. Похоже, что boost:: map_file с "private" мог бы быть полезен для этого.

Если вам действительно нужно поддерживать 32-битные системы, единственная альтернатива - как-то разбить эти большие блоки, как правило, на самолеты или подтомы. Оба ужасно работают, когда дело доходит до применения 3D-фильтров и т.д., Хотя я действительно избегал этого, если можно.

Если вы переходите на маршрут субтома, один трюк состоит в том, чтобы сохранить все подтомы в файлах с отображением памяти и отобразить их в адресное пространство только тогда, когда они вам понадобятся. При отключении от адресного пространства они должны оставаться в кеше унифицированного буфера до тех пор, пока не будут очищены, это означает, что вы можете использовать больше ОЗУ, чем у вас есть адресное пространство (особенно в Windows, где 32-разрядные приложения получают по умолчанию только 2 ГБ адресного пространства).

Наконец, на 32-битной Windows вы также можете посмотреть переключатель /3GB в boot.ini. Это позволяет вам выделять 3 ГБ адресного пространства для приложений, а не нормальный 2 ГБ. Из описанной проблемы я не думаю, что это даст вам достаточно адресного пространства, однако это может помочь вам с меньшими объемами. Обратите внимание, что переключатель /3GB может вызвать проблемы с некоторыми драйверами, поскольку он уменьшает количество адресного пространства, доступного ядру.

Ответ 2

Думаю, вам стоит взглянуть на hdf5. Это двоичный формат для хранения огромных объемов данных, собранных из таких вещей, как телескопы, физические эксперименты и машины для секвенирования генов. Преимущества использования чего-то подобного много, но три непосредственные мысли: (1) проверены, (2) поддерживают выбор гиперссылки, и (3) вы получаете сжатие бесплатно.

Доступны библиотеки C/С++, java, python, matlab.

Ответ 3

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

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

Ответ 4

Вы можете использовать файлы с отображением памяти для управления большими наборами данных с ограниченной памятью. Однако, если ваши размеры файлов будут 4 ГБ, тогда рекомендуется использовать бит 64 бит. У проекта boost есть хорошая многоплатформенная библиотека сопоставления памяти, которая работает очень близко к тому, что вы ищете.

http://en.wikipedia.org/wiki/Memory-mapped_file http://www.boost.org/doc/libs/1_44_0/libs/iostreams/doc/classes/mapped_file.html чтобы вы начали. Пример кода ниже -

#include <boost/iostreams/device/mapped_file.hpp>
boost::iostreams::mapped_file_source input_source;
input_source.open(std::string(argv[1]));
const char *data = input_source.data();
long size = input_source.size();
input_source.close();

Спасибо, Натан

Ответ 5

Один из вариантов, который я хотел бы рассмотреть, - это сопоставление памяти, вместо того чтобы сопоставлять все изображения, поддерживать связанный список изображений, которые лениво загружаются. По мере того как ваш фильтр работает через список изображений, загружайте по мере необходимости. На этапе загрузки нарисуйте анонимный (или фиксированный временный файл) блок того же размера и скопируйте его в качестве резервной копии. И когда вы применяете фильтры, вы просто создаете резервную копию для этой копии. Как сказал @Tony выше, 64-битный - это ваш лучший вариант, и для файлов с мультиплатформенной памятью, посмотрите на ускорение interprocess.

Ответ 6

Используйте STXXL: стандартная библиотека шаблонов для дополнительных больших наборов данных.

Я впервые услышал об этом на fooobar.com/questions/427902/...:)

Ответ 7

Вы можете использовать двухуровневую структуру: Массив указателей на отдельные изображения или (намного лучше) кучу изображений. Таким образом, вы можете сохранить 20 изображений в одном блоке памяти и поместить указатели в 20-изображения-блоки в массив. Это все еще быстро (по сравнению со связанным списком) при выполнении произвольного доступа.

Затем вы можете реализовать простой алгоритм подкачки: сначала все указатели в массиве имеют значение NULL. Когда вы впервые получаете доступ к блоку изображения, вы загружаете 20 изображений этого блока в память и записываете указатель в массив. Следующий доступ к этим изображениям не загружает ничего.

Если ваша память становится низкой, потому что вы загрузили и загрузили множество блоков изображений, вы можете удалить блок изображения, который вы наименее использовали (вы должны добавить второе поле рядом с указателем, в котором вы указали значение счетчика, которое вы подсчитывайте каждый раз, когда вы загружаете блок изображения). Блок изображения с самым низким счетчиком является наименее используемым и может быть удален (память используется повторно для нового блока, а указатель установлен в NULL).

Ответ 8

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

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

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

Ответ 9

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

Лучшим подходом было бы подумать об алгоритмах, которые вы хотите использовать, и о том, что они не могут быть написаны, что главным образом шагают по данным только в одном направлении. Хорошо, это не всегда возможно.

Если вы хотите запрограммировать решение среднего веса самостоятельно, вы должны сделать это следующим образом:

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

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

Опять же, это не забавно, если вы прыгаете по этим изображениям-вокселям. Ваш алгоритм должен соответствовать доступу к данным - для каждого решения, которое вы решили хранить ваши данные. Общий случайный доступ будет "разбивать" все, если ваши данные больше, чем ваша физическая память.

Ответ 10

Если аппаратное обеспечение и ОС позволяют это, я бы пошел 64 бит и отобразил файл в память (см. CreateFileMapping в Windows и mmap на Linux).

В Windows вы можете сделать вид над сопоставленным файлом, который позволяет копировать-на-запись. Я уверен, что вы можете получить эту функциональность и в Linux. В любом случае, если вы создаете представление только для чтения по исходному файлу, то это будут ваши "исходные данные". Затем вы создаете вид копирования на запись по исходному файлу - это будут "текущие данные".

При изменении текущих данных измененные базовые страницы будут скопированы и выделены для вас, а страницы для исходных данных останутся нетронутыми. Если вы убедитесь, что вы не записываете идентичные данные в ваши "текущие данные", вы также получите оптимальное использование памяти, поскольку ваши текущие данные и исходные данные будут разделять страницы памяти. Вы должны учитывать выравнивание страницы, потому что копирование на запись работает на странице.

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

Используя сопоставление файлов, утомительная работа по управлению памятью будет выполняться ОС. Он сможет эффективно использовать всю доступную память. Путь более эффективный, чем вы могли бы достичь при нормальных распределениях кучи.

Я бы начал с изучения CreateFileView() и MapViewOfFile() для использования в Windows. Для Linux у вас есть mmap(), но что касается моих знаний. Я ничего не трогал * nix с 2000 года...

Ответ 11

Посмотрите SciDB. Я не эксперт в этом, но из его примеров использования и документ описывая его, он позволяет естественным образом сопоставить ваши данные с массивом 3D (+ 1D для времени/версии) следующим образом:

CREATE ARRAY Pixels [
    x INT,
    y INT,
    z INT,
    version INT
] (
    pixel INT
);

И для реализации вашего запроса getXYPlaneSlice:

Slice (Pixels, z = 3, version = 1);

Чтобы избежать дублирования данных при изменении только части данных, вам не нужно заполнять весь массив для версии 1, поскольку SciDB поддерживает разреженный массив. Затем, когда вам нужно загрузить новейшие данные, вы можете загрузить с помощью version = 0, чтобы получить старую версию, и обновить результат другим путем с помощью version = 1.