mmap-загружаемая библиотека структуры данных для C++ (или C)
У меня есть некоторая большая структура данных (N> 10,000), который обычно только должен быть создан однажды (во времени выполнения) и может быть снова использован много раз впоследствии, но оно должно быть загружено очень быстро. (Это используется для обработки ввода данных пользователем на iPhoneOS.) mmap- луг файл, кажется, лучший выбор.
Есть ли какие-либо библиотеки структуры данных для C++ (или C)? Что-то вдоль строки
ReadOnlyHashTable table ("filename.hash");
// mmap(...) inside the c'tor
...
int freq = table.get('a');
...
// munmap(...); inside the d'tor.
Спасибо!
Подробнее:
Я записал подобный класс для хэш-таблицы сам, но мне довольно трудно поддержать, таким образом, я хотел бы видеть, существуют ли уже существующие решения. Библиотека должна
- Содержите стандартную программу создания, которые сериализируют структуру данных в файл. Эта часть не должна быть быстрой.
- Содержите загружающуюся стандартную программу, что mmap файл в только для чтения (или чтение-запись) структура данных, которая может быть применимой в O (1) шаги обработки.
- Используйте O (N) сумма диска/пространства памяти с небольшим постоянным множителем. (Устройство имеет серьезное ограничение памяти.)
- Маленькое время наверху к средствам доступа. (т.е. сложность не изменяется.)
Предположения:
- Разрядное представление данных (например, порядок байтов, кодирование
float, и т.д.), не имеет значения, так как это только используется локально. - До сих пор возможные типы данных, в которых я нуждаюсь, являются целыми числами, строками, и
structиз них. Указатели не появляются.
P.S. Boost.intrusive может помочь?
5 ответов
Похоже, что возможно вы могли бы использовать одну из утилит "идеального хэша". Они тратят некоторое время на оптимизацию хэш-функции для конкретных данных, чтобы не было коллизий хэша и (для минимально совершенных хэш-функций) чтобы в хэш-таблице не было (или, по крайней мере, было мало) пустых пробелов. Очевидно, что это предназначено для того, чтобы генерироваться редко, но использоваться часто.
CMPH утверждает, что справляется с большим количеством ключей. Однако я никогда не использовал его.
Есть большая вероятность, что он генерирует только хэш-функцию, оставляя вам возможность использовать ее для создания структуры данных. Это не должно быть особенно сложно, но, возможно, вы останетесь там же, где и сейчас - будете поддерживать хотя бы часть кода самостоятельно.
WRT boost.intrusive, я только что посмотрел. Это интересно. И раздражает, поскольку из-за этого одна из моих собственных библиотек выглядит немного бессмысленной.
Я подумал, что этот раздел выглядит особенно актуальным.
Если вы можете использовать "умные указатели" для ссылок, предположительно, тип умного указателя может быть реализован с помощью простого целого числа со смещением от адреса базы (и я думаю, что в этом смысл примера). Подскрипт массива может быть столь же валидным.
Безусловно, есть поддержка неупорядоченных множеств/мультимножеств (код C++ для хэш-таблиц).
Вы можете попытаться создать файл с отображением памяти, а затем создать структуру карты STL с распределитель клиентов. Затем ваш клиентский распределитель просто берет начало памяти файла с отображением памяти, а затем увеличивает его указатель в соответствии с запрошенным размером. В конце концов, вся выделенная память должна находиться в памяти файла с отображением памяти. и должен быть перезагружен позже.
Вам нужно будет проверить, свободна ли память картой STL. Если это так, ваш распределитель клиентов потеряет часть памяти файла с отображением памяти, но если это ограничено, вы, вероятно, сможете с этим жить.
Просто подумал о другом варианте - Datadraw . Опять же, я не использовал его, поэтому никаких гарантий, но он претендует на то, чтобы быть быстрым постоянным генератором кода базы данных.
Можно использовать cmph. У него есть механизм сериализации для самой хэш-функции, но вам все равно необходимо сериализовать ключи и данные, помимо добавления слоя разрешения конфликтов поверх него, если ваш юниверс набора запросов не известен заранее. Если вы заранее знаете все ключи, то это правильный путь, поскольку вам не нужно хранить ключи, и вы сэкономите много места. В противном случае для такого маленького набора я бы сказал, что это перебор.
Вероятно, лучший вариант - использовать sparse_hash_map от Google. У него очень низкие накладные расходы, а также есть необходимые вам крючки сериализации.
http://google-sparsehash.googlecode.com/svn/trunk/doc/sparse_hash_map.html#io