Я сейчас пишу алгоритм обработки изображений, и в какой-то момент мне нужно было собрать некоторую статистическую информацию о преобразованных пикселях, чтобы получить некоторое представление о направлении, которому я должен следовать при дальнейшей разработке. Информация, которую мне нужно было собрать, была в формате:
key: RGB value
value: int
Что я сделал, так это то, что я открыл преобразованное изображение и перебрал его, сохранив нужные мне значения в std::unordered_map со следующей подписью:
typedef std::unordered_map<boost::gil::rgb8_pixel_t, unsigned int> pixel_map_t;
В цикле:
for(int y = 0; y < vi.height(); y++) {
SrcView::x_iterator dst_it = src.row_begin(y);
for(int x = 0; x < vi.width(); x++, hits++) {
diff_map.insert(std::make_pair(dst_it[x], /* some uint32 */));
}
Я также пишу пользовательскую хеш-функцию (это была идеальная хеш-функция: 256^2 x R + 256 x G +
B - поэтому коллизии должны быть минимальными независимо от сегментов и макета хеш-таблицы (в разумных пределах).
Что я заметил, так это то, что вставка была ужасно медленной! - после достижения 11-й итерации скорость вставки снижается примерно в 100 раз. У меня было огромное количество столкновений!
Несмотря на очень небольшое количество дублированных цветов на изображении.
После этого я захотел устранить любую возможную ошибку в моем коде и начал сравнивать unordered_map с использованием хеш-функций STL с примитивными типами ключей, такими как int.
Код для теста был:
std::size_t hits = 0, colls = 0;
for(int y = 0; y < vi.height(); y++) {
SrcView::x_iterator dst_it = src.row_begin(y);
for(int x = 0; x < vi.width(); x++, hits++) {
if(diff_map.find(x*y) != diff_map.cend())
colls++;
diff_map.insert(std::make_pair(x*y, 10));
}
std::cout << y << "/" << vi.height() << " -> buckets: "
<< diff_map.bucket_count() << "("
<< std::floor(diff_map.load_factor() * 100)
<< "% load factor) [ " << colls << " collisions / " << hits << " hits ]" << std::endl;
}
... и вот результаты для первых 20 итераций внешнего цикла (с использованием только хеш-функции STL для типа int):
0/480 -> buckets: 8(12% load factor) [ 639 collisions / 640 hits ]
1/480 -> buckets: 4096(15% load factor) [ 640 collisions / 1280 hits ]
2/480 -> buckets: 4096(23% load factor) [ 960 collisions / 1920 hits ]
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions / 2560 hits ]
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions / 3200 hits ]
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions / 3840 hits ]
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions / 4480 hits ]
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions / 5120 hits ]
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions / 5760 hits ]
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions / 6400 hits ]
10/480 -> buckets: 4096(77% load factor) [ 3872 collisions / 7040 hits ]
11/480 -> buckets: 4096(85% load factor) [ 4161 collisions / 7680 hits ]
12/480 -> buckets: 4096(90% load factor) [ 4612 collisions / 8320 hits ]
13/480 -> buckets: 4096(99% load factor) [ 4901 collisions / 8960 hits ]
14/480 -> buckets: 32768(13% load factor) [ 5315 collisions / 9600 hits ]
15/480 -> buckets: 32768(13% load factor) [ 5719 collisions / 10240 hits ]
16/480 -> buckets: 32768(14% load factor) [ 6148 collisions / 10880 hits ]
17/480 -> buckets: 32768(15% load factor) [ 6420 collisions / 11520 hits ]
18/480 -> buckets: 32768(16% load factor) [ 6870 collisions / 12160 hits ]
19/480 -> buckets: 32768(17% load factor) [ 7135 collisions / 12800 hits ]
20/480 -> buckets: 32768(17% load factor) [ 7584 collisions / 13440 hits ]
21/480 -> buckets: 32768(18% load factor) [ 7993 collisions / 14080 hits ]
Не слишком ли много коллизий в этом случае? Библиотеки STL в целом имеют высокое качество, но имеют 639/640 и 640/1280 для простого, как минимум, странного звука клавиш.
А может я что-то не так делаю?
И это была моя хеш-функция (теоретически, вообще не должно быть коллизий, но числа были очень близки):
template<>
struct std::hash<boost::gil::rgb8_pixel_t> :
public std::unary_function<const boost::gil::rgb8_pixel_t&, size_t>
{
size_t operator()(const boost::gil::rgb8_pixel_t& key) const
{
size_t ret = (static_cast<size_t>(key[0]) << 16) |
(static_cast<size_t>(key[1]) << 8) |
(static_cast<size_t>(key[2]));
//return 256 * 256 * key[0] + 256 * key[1] + key[2];
return ret;
}
};
Теперь это уже не смешно ...
Я написал эту хеш-функцию:
template<>
struct std::hash<int> :
public std::unary_function<const int&, size_t>
{
size_t operator()(const int& key) const
{
return 5;
}
};
Теоретически, у меня должна быть 100% частота столкновений, верно? но результаты:
0/480 -> buckets: 8(12% load factor) [ 639 collisions / 640 hits ]
1/480 -> buckets: 4096(15% load factor) [ 640 collisions / 1280 hits ]
2/480 -> buckets: 4096(23% load factor) [ 960 collisions / 1920 hits ]
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions / 2560 hits ]
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions / 3200 hits ]
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions / 3840 hits ]
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions / 4480 hits ]
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions / 5120 hits ]
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions / 5760 hits ]
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions / 6400 hits ]
Почему?
Конверт: MSVS2010