Вставка карты C++ и выполнение поиска и устройство хранения данных наверху
Ctrl + Сдвиг + F4 для закрытия всех окон. Необходимо отобразить его сами:
Инструкции:
- В Visual Studio, перейдите к Инструменту |, Опции
- Под Средой выбирают Клавиатуру
- На Шоу, управляет содержащий, введите Окно. CloseAllDocuments. Необходимо получить однократный въезд в поле списка ниже его
- Помещенный курсор в сочетания клавиш Нажатия и нажатие Ctrl + Сдвиг + F4 .
- Нажимают "OK"
Кредит к Kyle Baley по codebetter.com . Я изменил его пример для использования сдвига вместо высокого звука, потому что это было легче на моих руках.
8 ответов
Учитывая то, что вы сказали, я бы очень серьезно подумал об использовании std :: vector и использовании std :: lower_bound , std :: upper_bound и / или std :: equal_range для поиска значений.
Хотя точные накладные расходы of std :: map может (и действительно) варьироваться, мало или нет места для сомнений в том, что он обычно потребляет дополнительную память и ищут значения медленнее, чем двоичный поиск в вектор. Как вы отметили, обычно (и почти неизбежно) он реализуется как своего рода сбалансированное дерево, которое накладывает накладные расходы на указатели и информацию о балансировке и обычно означает, что каждый узел также выделяется отдельно. Поскольку ваши узлы довольно малы (обычно 8 байт), дополнительных данных, вероятно, будет не меньше, чем то, что вы на самом деле храните (т.е. не менее 100% накладных расходов). Раздельное распределение часто означает плохую локальность ссылки, что приводит к плохому использованию кеша.
Большинство реализаций std :: map используют красно-черное дерево. Если вы собирались использовать std :: map , реализация, использующая дерево AVL, вероятно, лучше подошла бы для ваших целей - дерево AVL имеет несколько более жесткие ограничения на балансировку. Это дает немного более быстрый поиск за счет немного более медленной вставки и удаления (поскольку требуется более частая перебалансировка, чтобы поддерживать более строгую интерпретацию термина «сбалансированный»). Однако пока ваши данные остаются неизменными во время использования, std :: vector почти наверняка лучше.
Еще одна возможность, на которую стоит обратить внимание: если ваши ключи хотя бы справедливо даже распределены, вы можете попробовать найти с помощью интерполяции вместо деления пополам. т.е. вместо того, чтобы всегда начинать с середины вектора, вы выполняете линейную интерполяцию, чтобы угадать наиболее вероятную начальную точку для поиска. Конечно, если ваши ключи следуют некоторому известному нелинейному распределению, вы можете вместо этого использовать соответствующую интерполяцию.
Предполагая, что ключи достаточно равномерно распределены (или, по крайней мере, следуют некоторому предсказуемому шаблону, который поддается интерполяции), поиск интерполяции имеет сложность O (log log N). Для 130 миллионов ключей это примерно 4 зонда, чтобы найти предмет. Чтобы добиться значительно лучших результатов при (нормальном / неидеальном) хешировании, вам нужен хороший алгоритм, и вам нужно поддерживать достаточно низкий коэффициент загрузки в таблице (обычно около 75% или около того, то есть вам нужно предусмотреть что-то вроде 32 миллионов дополнительных (пустых) мест в вашей таблице, чтобы улучшить ожидаемый сложность от четырех зондов до трех). Возможно, я старомоден, но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.
OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - - набор известен заранее, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
и вам нужно поддерживать коэффициент загрузки в таблице достаточно низким (обычно около 75% или около того, то есть вам нужно предусмотреть что-то вроде 32 миллионов дополнительных (пустых) мест в вашей таблице, чтобы улучшить ожидаемую сложность с четырех зондов до трех ). Возможно, я старомоден, но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - - набор известен заранее, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
и вам нужно поддерживать коэффициент загрузки в таблице довольно низким (обычно около 75% или около того, то есть вам нужно предусмотреть что-то вроде 32 миллионов дополнительных (пустых) мест в вашей таблице, чтобы улучшить ожидаемую сложность с четырех зондов до трех ). Возможно, я старомоден, но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - - набор известен заранее, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
вам нужно учесть что-то вроде 32 миллионов дополнительных (пустых) мест в таблице, чтобы улучшить ожидаемую сложность с четырех зондов до трех). Возможно, я старомоден, но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - - набор известен заранее, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
вам нужно учесть что-то вроде 32 миллионов дополнительных (пустых) мест в таблице, чтобы улучшить ожидаемую сложность с четырех зондов до трех). Возможно, я старомоден, но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - - набор известен заранее, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - набор известен заранее время, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
но мне кажется, что это много дополнительного хранилища, которое можно использовать для такого небольшого увеличения скорости.OTOH, это правда, что это почти идеальная ситуация для идеального хеширования - набор известен заранее время, а ключ довольно маленький (важно, поскольку хеширование обычно линейно зависит от размера ключа). Даже в этом случае, если ключи не распределены довольно неравномерно, я не ожидал бы каких-либо значительных улучшений - идеальная хеш-функция часто (обычно?) Довольно сложна.
Вектор абсолютно уничтожит карту здесь, если вам не нужно делать вставки в середине вектора. Я написал специальный распределитель для отслеживания использования памяти, и вот результаты в Visual Studio 2005:
std :: map
1.3 million insertions
Total memory allocated: 29,859 KB
Total blocks allocated: 1,274,001
Total time: 17.5 seconds
std :: vector
1.3 million insertions
Total memory allocated: 12,303 KB
Total blocks allocated: 1
Total time: 0.88 seconds
std :: map использует в два раза больше памяти и в 20 раз больше времени для вставки всех элементов.
Если введенные вами данные отсортированы, вам следует попробовать только векторный и двоичный поиск (например, lower_bound () ). Это может оказаться достаточным (это также O (log n)). В зависимости от распределения ваших ключей и используемой хэш-функции, hash_map также может работать. Я думаю, что это tr1 :: unordered_map в gcc.
Большинство компиляторов поставляются с нестандартными (но работающими) hash_map (или unordered_map ), которые могут быть быстрее для вас. Он поступает в C ++ 0x (находится в tr1), а также (как всегда) в boost .
GCC тоже сделал это, но я не использовал C ++ для этого .. 12 лет .., но он все еще должен быть где-то там.
Вы можете взглянуть на 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;
}
Если ваши ключи не меняются, вы можете рассмотреть идеальную хеш-функцию как альтернативу стандартному контейнеру.
Я не знаю, какие препятствия вы встретите. столкнуться с набором данных такого размера, но, возможно, стоит потратить несколько минут на эксперименты.
Учитывая огромный объем используемой памяти, вы также должны учитывать, что любой доступ к памяти при поиске приведет к сбою кеш-памяти.
В этом отношении смешанное решение небольшой хэш-карты как Первый уровень и отсортированные векторы для сегментов, вероятно, являются лучшими.
Идея состоит в том, чтобы хранить индекс хеш-таблицы в кэш-памяти и выполнять поиск в меньших отсортированных контейнерах, чтобы уменьшить количество ошибок кеша.
В качестве частичного ответа на ваш вопрос, касающийся производительности поиска, вы должны рассмотреть свой шаблон вставки . Вы заметили, что std :: map использует красно-черное дерево в качестве защиты от линеаризации тщательно отсортированной вставки в связанный список. Следовательно, такое дерево обеспечивает время поиска O (log n) , несмотря на неправильный порядок вставки. Вы платите за это, однако, за производительность вставки, удаления и обхода, а также за потерю местоположения ссылки при повторном чтении «ближайших» данных.
Хэш-таблица может предложить более быстрый поиск, если вы можете настроить хэш функция для вашего типа ключа (вы скажете, целое число), которая предотвратит коллизии. Если ваш набор данных был фиксированным, так что вы могли загрузить его один раз и только потом прочитать, вы можете использовать параллельные массивы целых чисел и чисел с плавающей запятой и использовать std :: lower_bound , чтобы найти совпадение с помощью двоичного поиска. Правильная сортировка параллельных массивов была бы сложной задачей,