Нужно хранить строку как идентификатор для объектов в некоторой быстрой структуре данных

Question

Я реализую хранилище сессий для веб-сервера. Ключи строковые и сохраненные объекты являются указателями. Я пытался использовать карту, но нужно что-то Быстрее. Я посмотрю объект 5-20 раз так часто, как вставить.

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

Я пишу c / c ++ под Linux. Я не хочу совершать форсирование, поскольку мой веб-сервер переживет форсирование. :)

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

Answer 1

Я собирался предложить map, но я вижу, что вы уже исключили это.

Я пытался использовать карту, но что-то нужно быстрее.

Это границы производительности std :: map, предоставленные страницей Википедии :

• Поиск элемента занимает O (log n) времени
• Вставка нового элемента занимает O (log n) времени
• Увеличение / уменьшение итератора занимает O (log n) времени
• Итерация по каждому элементу карты занимает O (n) времени
• Удаление одного элемента карты занимает O (log n) времени
• Копирование всей карты занимает O (n log n) времени.

Как вы измерили и определили, что карта недостаточно оптимизирована для вас? Вполне возможно, что любые узкие места, которые вы видите, находятся в других частях кода, и map вполне подходит.

Вышеуказанные границы выглядят так, как будто бы они соответствуют всем, кроме самых строгих требований к масштабируемости.

Answer 2

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

1. Сколько предметов будет в хранилище сеансов? 50? 100000? 10000000000
2. Насколько велика каждая позиция в магазине (размер в байтах)?
3. Какой тип ввода строки используется для ключа? ASCII-7? UTF-8? UCS2? ...

Хеш-таблицы обычно очень хороши для поиска. Вы можете оптимизировать их для большей скорости, написав их самостоятельно (и да, вы можете изменить размер таблицы). Предложения по повышению производительности с помощью хеш-таблиц:

1. Выберите хорошую хэш-функцию! желательно, чтобы оно было равномерно распределено по вашей хэш-таблице и не требовало значительных затрат времени (это будет зависеть от формата ввода с клавиатуры).
2. Убедитесь, что если вы используете сегменты, длина которых не превышает 6. Если вы превышаете 6 сегментов, то ваша хэш-функция, вероятно, распределяется недостаточно равномерно. Длина ковша <3 предпочтительна. </li>
3. Следите за тем, как вы распределяете свои объекты. Если это вообще возможно, попытайтесь разместить их рядом друг с другом в памяти, чтобы воспользоваться преимуществами ссылки. Если вам нужно, напишите свой собственный распределитель / менеджер кучи. Также придерживайтесь выровненных границ для лучшей скорости доступа (выровненный зависит от процессора / шины, поэтому вам нужно будет определить, хотите ли вы ориентироваться на конкретный тип процессора).

BTrees также очень хороши и в целом работают хорошо. (Кто-то может вставить информацию о деревьях здесь).

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

struct foo {
  int a;
  char my_string[0]; // allocate an instance of foo to be 
                     // sizeof(int) + sizeof(your string data) etc
}

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

Answer 3

Можно сделать самостоятельно. Но у вас не должно возникнуть проблем с boost или std :: tr1 :: unordered_map.

Тройной три может быть быстрее, чем хэш-карта для меньшего числа элементов.