По вопросу выбора контейнера, подобного множеству, самые опытные разработчики C ++ скажут вам: «Используйте std::unordered_set вместо std::set. Это более эффективно. Конечно, для больших наборов данных ».
Если они достаточно дружелюбны, чтобы дать вам дальнейшие советы, они также расскажут вам о важности выбора хорошей хеш-функции и о том, что качественные хэши для вычисления могут быть дорогими. Кроме того, специальный оператор равенства, как того требует std::unordered_set, может увеличить стоимость использования хеш-таблицы. Не думайте, что ваш набор данных достаточно велик, чтобы сделать хеш-таблицу более эффективной, чем двоичный поиск по отсортированным данным (реализованный std::set); всегда измерять.
Зная все это, я решил сравнить производительность моего существующего кода, основанного на std::set, с реализацией, основанной на std::unordered_set. К моему большому удивлению, производительность нового кода была ужасающе низкой. Для больших наборов данных программа становилась настолько медленной, что казалось, что она зависает. Я совершил какую-то банальную ошибку? Разве я не понял совета? Вот история.
Объекты, которые я хешировал, были точками в трехмерном пространстве, которые обычно представлены набором из трех (декартовых) координат, скажем using Point3D = std::array<double, 3>;.
Если вы хотите вставить такую точку в хэш-карту , вам необходимо предоставить функцию хеширования. Эта функция должна генерировать хэш (значение size_t) для каждой точки. Обратите внимание, что количество различных точек намного больше, чем количество значений, которые может принимать size_t, поэтому невозможно, чтобы каждая точка имела уникальный хэш. Однако хорошая функция хеширования не покажет никаких зависимостей (предсказуемых результатов) между битами, представляющими точку (вход), и битами, представляющими хэш (выход). Из этого требования следует, что точки с одинаковыми координатами, но в разном порядке, скажем, (1.0, 2.0, 3.0) и (3.0, 2.0, 1.0), должны иметь разные хеши.
Зная это, я решил использовать boost :: hash_range (), который предназначен для создания (почти наверняка) разных хэшей для троек координат, которые идентичны, за исключением порядка чисел:
const auto hash = boost::hash_range(begin(coordinate_array),
end(coordinate_array));Точки, которые я хешировал, происходили из узлов решетки октодерева точечной области. Чтобы получить визуальное представление о типе набора точек, с которым мы имеем дело, посмотрите на следующее квадродерево (эквивалент октодерева в 2D), декомпозицию пространства с его узлами решетки, отмеченными красным:
Точки решетки октодерева очень похожи на точки в примере, за исключением того, что они расположены равномерно в 3D. Если ограничивающие значения координаты x равны x_min, x_max, то для всех точек решетки значение координаты x следует шаблону
p_x = x_min + (j / 2^i) * (x_max — x_min)
с j в [0, 2^i]. То же самое верно для y- и z-координат, хотя и с их собственными независимыми границами. Основываясь на этом соотношении, можно независимо воспроизвести проблему того, что std::unordered_set намного медленнее, чем std::set.
Вот код, который мы используем для случайной генерации регулярных точек:
#include <random>
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> intDis1(-1000, 1000);
std::uniform_int_distribution<> intDis2(0, 16);
using Point3D = std::array<double, 3>;
auto genRegularCoordinate = [&gen, &intDis1, &intDis2]()
{
return double(intDis1(gen)) +
double(intDis1(gen)) / pow(2.0, intDis2(gen));
};
auto genRegularPoint = [&]()
{
return Point3D{genRegularCoordinate(), genRegularCoordinate(),
genRegularCoordinate()};
};
Три примера обычных точек:
(-850.98974609375, 756.984680175781, -175.439453125) (-787.3984375, -1024, -314.46875) (-593.375, -920.15625, -161.5859375)
В качестве входных данных для теста эффективности строим вектор из 100000 точек:
auto inputPoints = std::vector<Point3D>{};
for (int n = 0; n < 100000; ++n)
{
inputPoints.emplace_back(genRegularPoint());
}
Чтобы проверить эффективность, мы заполняем набор этими точками и подсчитываем количество точек из вектора, которые находятся в наборе:
auto pointSet = std::set<Point3D>(begin(inputPoints),
end(inputPoints));
//auto pointSet = std::unordered_set<Point3D>(begin(inputPoints),
// end(inputPoints));
auto nFound = count_if(begin(inputPoints), end(inputPoints),
[&pointSet](const Point3D &point)
{
return pointSet.count(point) > 0;
});
На моей машине это занимает около 0,15 секунды для std::set и 30 секунд для std::unordered_set. Если я удвою количество баллов до 200000, то получится 0,30 секунды по сравнению со 150 секундами.
Так что же тогда не так? Первым делом я проверил, уникальны ли хэши. Оказывается, это так. Я распечатал статистику экземпляра std::unordered_set:
bucket_count = 131072 max_bucket_count = 131072 load_factor = 0.762939 max_load_factor = 1
Опять же, ничего необычного. load_factor сразу следует из количества элементов (100000), деленного на bucket_count. Отсутствующая статистика говорит нам о том, насколько хорошо эти 100000 элементов распределены по 131072 корзинам ...
В качестве последнего шага расследования я начал перебирать все ведра и распечатывать их содержимое. К моему большому удивлению, оказалось, что все 100000 точек без исключения находятся в одном ведре. Но как это возможно? Чтобы понять это, нам нужны некоторые базовые знания о том, как реализуется типичная хеш-карта.
При size_t возможных значениях хэшей невозможно связать каждый хэш с отдельным адресом памяти. Вместо этого хеш-карта создает несколько сегментов и сопоставляет хеши с сегментами. Все вставленные объекты хранятся в корзине, с которой сопоставлен их хэш. В нашем случае у нас есть 131072 ведра, что составляет 2¹⁷. Очевидный способ создать это сопоставление - разделить на количество сегментов и использовать остаток в качестве номера сегмента:
bucket_idx = hash % bucket_count;
Поскольку все наши разные хэши попадают в одну корзину, теперь мы знаем, что они должны иметь одинаковый остаток после деления. Поскольку в нашем случае количество сегментов - это степень двойки, остаток - это просто столько же младших битов, сколько мощность. Например:
731 % 2⁵ = 27
находится в двоичном формате
1011011011 % 100000 = 11011
Это означает, что в нашем случае последние 17 бит наших хэшей должны быть идентичны! Печать хэшей в двоичном формате действительно подтверждает это:
6224711552622665454 == 0101011001100010100111100010110101011011010110000001111011101110 5118867174346727150 == 0100011100001001110111101001001011111011010110000001111011101110 3439893115510988526 == 0010111110111100111101001001000000101111010110000001111011101110 12686064959077490414 == 1011000000001101111101001101110111011011010110000001111011101110 11837512432766951150 == 1010010001000111010010101101011011111011010110000001111011101110
Из этого небольшого образца видно, что даже последние 24 бита идентичны.
Теперь мы наконец понимаем, почему наша хеш-карта такая медленная: качество наших хэшей. Я нашел простое решение - хешировать получившийся хеш, например:
const auto hash = boost::hash_range(begin(coordinate_array),
end(coordinate_array));
const auto betterHash = std::hash<size_t>()(hash);
Повторный запуск экспериментов с этим изменением подтверждает, что std::unordered_set имеет ожидаемую производительность. Сравнивая тайминги для std::set, std::unordered_set с исходным хешем и std::unordered_set с дополнительным хешем, мы видим, что для достаточно большого количества элементов std::unordered_set фактически становится быстрее, чем std::set:
Другое решение - не использовать степень двойки для количества ведер. К сожалению, с MSVC ++ 12.0 мы не можем этого сделать. Если мы запрашиваем другой размер, bucket_count всегда принимает значение ближайшей большей степени двойки. Я также тестировал с libstdc ++ версии GCC 4.9.2., Которая использует простые числа для количества сегментов. Мои эксперименты подтвердили, что эта стратегия выбора нескольких сегментов эффективно позволяет избежать этой проблемы.
Обратите внимание, что то, что мы здесь обсуждали, применимо к std::unordered_map, а также к любому другому контейнеру, основанному на хэш-карте.
Программное обеспечение Plaxis упрощает моделирование сложных геоинженерных проектов. Посетите наш сайт, чтобы узнать о карьерных возможностях.
