BLR> К сожалению скорость критична. использование мапки- это лишь вариант. Нужно получить, быстро, значение по ключу, обьем данных очень большой.
Если у тебя мап меняется часто, то быстро никак с ним не получится (если я не ошибаюсь мап — это сбалансированное дерево и следовательно при добавлении / удалении происходит его перебалансировка).
Я так понимаю что обьем у тебя набирается за счет того что большие данные.
Тогда можно рассмотреть другой вариант:
У тебя есть 2 файла:
первый содердит структуры данных последовательно как вектор (кстати для этого можно попробовать и использовать std::vector)
второй содержит: ключ и смещение к данным от начала первого файла (это будет сериализация map), а если просче это файл индексов.
Как работать:
Поиск
Ты загружаешь индексы в память (десериализацией например) или формируешь из используя значения из файла.
Ищешь нужное значение по ключу и получаешь смещение, а потом по смещению читаешь блок из 1-го файла
Добавление
Добавляешь в первый файл (в конец) значение и запоминаешь по какому смещению оно находится
Добавляешь в мапу новый ключ и ассоциируешь его с запомненным значением смещения.
Сохраняешь мапу (сериализация), это если только нужно.
Т.к. мап не будет содержать обьемных данных (думаю не более 4б на один элемент), то памяти это дело у тебя будет занимать не много, а файл с данными подгрузится по необходимости самой виндой, если будет место в памяти .
Единственной проблеммой становится если тебе этот мап нужно передавать между процессами. Хотя и это можно решить довольно эффективно .
Кстати это фактически, то что предложил Кодт, но только для быстроты я предлагаю держать ключи в отдельном файле и сохранять их модификации, допустим по завершению работы.
Здравствуйте, BLR, Вы писали:
BLR>Здравствуйте, Кодт, Вы писали:
К>>Здравствуйте, BLR, Вы писали:
BLR> Молодец. Почти. Фича в том что нужно обеспечить хранение большого числа значений Ключ — значение. При этом в памяти ничего держать нельзя, почти ничего. Обеспечить быстрый поиск по ключу его значений. Значений может быть немеренно. BLR>Использутся, для этих целей, файл отображаемый на память.
Если только поиск — то сделай массив пар <ключ, значение> (размести его в блоке файлмаппинга), отсортируй (алгоритмы sort / heapsort) и так храни.
Поиск над сортированным массивом — алгоритм search.
В качестве контейнера — или обычный сишный массив, или boost::array (тот же сишный массив в красивой обложке).
Если ещё и изменение, то либо операции вставки в массив (весьма затратно), либо сделать дерево, полностью размещённое в твоём файлмаппинге.
Обычные set, map использовать нельзя из-за статических переменных (во всяком случае, в STL от Dinkumware, который идёт в поставке VC).
Значит, придётся изобрести что-то своё, либо на основе Б-дерева, либо на Красно-Чёрном дереве.
Ещё один вариант: данные хранить как попало, но параллельно держать индекс, отражающий порядок сортировки.
(Элемент индексной таблицы — целое число, что, естественно, занимает гораздо меньше места).
Между прочим, нормальные СУБД так и поступают: отдельно куча из записей таблицы, отдельно индексы.
Да, естественно, что внутри файлмаппинга крайне нежелательно хранить указатели — вместо них должны быть хендлы (некоторые числа, из которых можно получить указатель; например, смещение в файле, номер записи, номер указателя, хранимого в таблице в памяти).
Так можно обеспечить персистентность данных и не привязываться к конкретному расположению файлмаппинга в адресном пространстве.
Здравствуйте, BLR, Вы писали:
BLR>Здравствуйте, Кодт, Вы писали:
BLR> Идея с мапкой появилась из-за неохоты делать Б+ деревья.
Мне кажется, что самым дешёвым способом будет сортированный индексный массив.
Дешёвым в смысле отношение скорость/секс.
Кстати говоря, можно хранить пирамиду, спроецированную на массив.
[0] — это корень, [1]..[2] — первый этаж, [3]..[7] — второй, и так далее.
Пирамида — это двоичное дерево, у которого родитель < ребёнки.
Доступ к пирамиде вдвое медленнее, чем к обычному двоичному дереву (т.к. нужно проверять оба дочерних узла).
Как вариант — использовать хеш-таблицу.
То есть в начале файла — таблица хешей, а в основной области — одно- или двухсвязные списки данных. Плюс ещё список свободных ячеек.
.
.
Перекуём баги на фичи!
