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

Question

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

Моя среда разработки - QT framework, MinGW для Windows и GCC для Linux.

В настоящее время я использую простую структуру данных для хранения данных волумедата в виде:

unsigned char *volumeData;

и сделайте одно огромное распределение следующим образом.

volumeData=new unsigned char[imageXsize * imageYsize * numofImages];

Ниже приведены важные методы доступа к данным изображения в заданной плоскости, например

.

unsigned char* getXYPlaneSlice(int z_value);
unsigned char* getYZPlaneSlice(int x_value);
unsigned char* getZXPlaneSlice(int y_value);

С моей простой структурой данных было легко реализовать описанные выше методы.

Но в будущем нам может потребоваться принять размер тома как 2000x2000x1000 (~ 3,7 ГБ). И текущая структура данных не сможет обработать эти огромные данные.

1. Как избежать фрагментации? Теперь даже при данных 1000x1000x200 сбой приложения дает bad_alloc. Каков наилучший способ изменить структуру данных для этого? Должен ли я использовать что-то вроде связного списка, каждый блок имеет размер 100 МБ.

2. Кроме того, пользователь должен иметь возможность выполнять некоторые фильтры обработки изображений на объемных данных, а также должен иметь возможность сбрасывать значение исходного пикселя. Это значит, что я должен хранить две копии тома. С текущей реализацией это как.

   unsigned char * volumeDataOriginal;

   unsigned char * volumeDataCurrent;

Таким образом, с диапазоном данных 2000x2000x1000 будет использоваться около 8 ГБ (4 ГБ для каждого тома). Но в Win32 адресное пространство составляет 4 ГБ. Как с этим справиться? Я должен идти с 64-битным приложением?

РЕДАКТИРОВАТЬ: Вот снимок моего приложения

По сути, я загружаю данные объема (из набора изображений, из формата MRC и т. Д.) И отображаю их в разных средствах просмотра плоскостей (XY, YX, YZ. Изображение показывает средство просмотра плоскостей XY). Мне нужно сохранить более 3 методов доступа к данным для отображения изображения в конкретной плоскости. Используя ползунок, пользователь может выбрать, какое изображение отображать в выбранной плоскости)

Заранее спасибо.

Answer 1

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

Есть C / C ++,Доступны библиотеки Java, Python, Matlab.

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

Answer 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();

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

Answer 5

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

Я впервые услышал об этом на SO :)

Answer 6

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

Answer 7

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

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

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

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

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

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

Answer 8

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

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

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

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

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

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

Answer 9

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

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

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

Answer 10

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

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

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