Вставка карты C ++ и поиск производительности и накладных расходов на хранение

Question

Я бы хотел сохранить отображение ключа integer в значение float в памяти.

У меня примерно 130 миллионов ключей (и, соответственно, 130 миллионов значений).

Я сосредоточен на производительности поиска - мне нужно сделать много-много миллионов поисков.

Библиотека C ++ STL имеет класс map для ассоциативных массивов такого рода. У меня есть несколько вопросов о map.

Каковы затраты на хранение map для набора данных указанного выше размера? Как масштабируется общий объем хранения с map?

Похоже, основная структура данных для map представляет собой красно-черное сбалансированное двоичное дерево. Звучит как реальная производительность , для вставки и извлечения - O(log n).

Упоминается O(1) для намека на вставку. Мои входные данные предварительно отсортированы, поэтому я считаю, что должен быть в состоянии предоставить подсказку для событий вставки. Как бы я дал эту подсказку, используя методы, перечисленные здесь ?

Существует ли контейнер STL, обеспечивающий лучшую производительность поиска?

Существуют ли другие общедоступные платформы с открытым исходным кодом с классом связанного массива, который использует базовую структуру данных, которая работает лучше, чем STL map?

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

Я использую GCC 4 для этой задачи под управлением Linux или Mac OS X.

Я заранее прошу прощения, если это глупые вопросы. Спасибо за ваш совет.

Answer 1

Учитывая то, что вы сказали, я бы очень серьезно подумал об использовании std::vector<pair<int, float> > и использовании std::lower_bound, std::upper_bound и / или std::equal_range для поиска значений.

В то время как точные служебные данные std::map могут (и могут) изменяться, практически нет места для вопроса о том, что он обычно потребляет дополнительную память и ищут значения более медленно чем бинарный поиск в векторе. Как вы заметили, это обычно (и почти неизбежно) реализуется как некое сбалансированное дерево, которое накладывает накладные расходы на указатели и информацию о балансировке и, как правило, означает, что каждый узел также выделяется отдельно. Поскольку ваши узлы довольно малы (обычно 8 байт), дополнительные данные, вероятно, будут как минимум такими же, как те, что вы на самом деле храните (т. Е. Как минимум 100% накладных расходов). Отдельное распределение часто означает плохую локальность ссылок, что приводит к плохому использованию кэша.

В большинстве реализаций std::map используется красно-черное дерево. Если вы собираетесь использовать std::map, реализация, использующая дерево AVL, вероятно, подойдет вам лучше - дерево AVL имеет несколько более жесткие ограничения на балансировку. Это дает немного более быстрый поиск за счет немного более медленного вставки и удаления (так как он должен чаще балансировать, чтобы поддерживать более строгую интерпретацию «сбалансированного»). Пока ваши данные остаются постоянными во время использования, std::vector почти наверняка лучше.

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

Предполагая, что ключи достаточно равномерно распределены (или, по крайней мере, следуют некоторому предсказуемому шаблону, который поддается интерполяции), поиск интерполяции имеет сложность O (log log N). Для 130 миллионов ключей это составляет около 4 проб, чтобы найти предмет. Чтобы сделать это значительно лучше, чем при обычном / неидеальном хешировании, вам нужен хороший алгоритм, и вы должны держать коэффициент загрузки в таблице достаточно низким (обычно около 75% или около того), т.е. вам необходимо учитывать что-то вроде 32 миллионов дополнительных (пустых) мест в вашей таблице, чтобы увеличить ожидаемую сложность с четырех проб до трех). Возможно, я просто старомоден, но мне кажется, что много дополнительного хранилища для такого небольшого улучшения скорости.

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

Answer 2

Вектор обязательно убьет карту, предполагая, что вам не нужно делать вставки в середине вектора. Я написал собственный распределитель для отслеживания использования памяти, и вот результаты в Visual Studio 2005:

std::map<int, float>:

1.3 million insertions
Total memory allocated: 29,859 KB
Total blocks allocated: 1,274,001
Total time: 17.5 seconds

std::vector<std::pair<int, float> >:

1.3 million insertions
Total memory allocated: 12,303 KB
Total blocks allocated: 1
Total time: 0.88 seconds

std :: map использует вдвое больше памяти и занимает 20 раз больше времени, чтобы вставить все элементы.

Answer 3

Если ваш вход отсортирован, вы должны попробовать только вектор и двоичный поиск (т.е. lower_bound()). Это может оказаться адекватным (это также O (log n)). В зависимости от распределения ваших ключей и используемой хеш-функции, hash_map также может работать. Я думаю, что это tr1::unordered_map в GCC.

Answer 4

Большинство компиляторов поставляются с нестандартной (но работающей) hash_map (или unordered_map), которая может быть быстрее для вас. Это происходит в C ++ 0x (в tr1), а также (как всегда) уже в boost .

GCC сделал то же самое, но я не делал C ++ для этого в течение ... 12 лет ..., но он все еще должен быть где-то там.

Answer 5

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

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

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

Answer 6

Если ваши ключи неизменны, вы можете рассмотреть совершенную хэш-функцию в качестве альтернативы стандартному контейнеру.

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

Answer 7

Вы можете взглянуть на std :: tr1 :: unorderd_map.

Но если у вас есть 32-разрядные целочисленные ключи без знака (4294967296 возможных значений) и 130 миллионов различных ключей, то вы должны написать собственный контейнер, оптимизированный для этой задачи. Особенно, если случай с ключом в 130 миллионов является обычным случаем (и не только редким максимумом).

4294967296/130000000 = 33, так что каждый 33-й номер во всем пространстве используется в ваших данных.

Например, вы можете разделить диапазон ключей на разделы фиксированного размера. Если ключи распределены достаточно равномерно, вы должны разделить пространство ключей, например, на: Контейнеры размером 256 или даже 32 размера зависят от того, сколько памяти вы хотите потратить, когда хранится только несколько значений.

Пример, чтобы дать вам идею:

#define BUCKET_SIZE  256
#define BUCKET_SIZE_SHIFT  8
struct Bucket {
  uint32_t key;
  float value;
  Bucket* pNext;
};

Bucket data[ 4294967296 / BUCKET_SIZE ];

Bucket* find( uint32_t key ) {
  uint32_t bucket_index = key / BUCKET_SIZE;
  // or faster: uint32_t bucket_index = key >> BUCKET_SIZE_SHIFT;
  Bucket* pBucket = &data[ bucket_index ];
  while( pBucket ) {
    if( pBucket->key == key ) return pBucket;
    pBucket = pBucket->pNext;
  }
  return NULL;
}

Answer 8

В качестве частичного ответа на ваш вопрос, касающийся производительности поиска, вы должны рассмотреть шаблон вставки . Вы отметили, что std::map использует красно-черное дерево в качестве хеджирования против линеаризации тщательно отсортированной вставки в связанный список. Следовательно, такое дерево обеспечивает O (log n) время поиска, несмотря на неправильный порядок вставки. Однако вы платите за это затраты на вставку, удаление и выполнение, а также за потерю локальности для повторного чтения «соседних» данных.

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