Я тут провел небольшой эксперимент...
Рандомно созданный вектор из N
чисел с положительными и отрицательными значениями, с использованием разных контейнеров:
size_t usingSet(const std::vector<int>& input)
{
std::set<unsigned> unique;
for(int item : input) {
unique.insert(abs(item));
}
return unique.size();
}
size_t usingHash(const std::vector<int>& input)
{
std::unordered_set<unsigned> unique;
unique.reserve(input.size());
for(int item : input) {
unique.insert(abs(item));
}
return unique.size();
}
size_t usingVec(const std::vector<int>& input)
{
std::vector<unsigned> uniq;
uniq.reserve(input.size());
for(int item : input) {
uniq.push_back(abs(item));
}
sort(uniq.begin(),uniq.end());
return unique(uniq.begin(),uniq.end()) - uniq.begin();
}
По 1000 раз выясняем количество уникальных элементов. Время в микросекундах, понятно, что плюс-минус... но для оценки вполне годится. Округлять не стал, думаю, самим в уме в секунды-миллисекунды прикинуть несложно.
Set Hash Vector
-----------------------------------------------------------
N = 10: 790 1256 253
N = 100: 8304 8243 1192
N = 1000: 130070 78354 27573
N = 10000: 1543452 757059 498093
N = 100000: 14545110 4232742 6182957
N = 1000000: 127603400 27039847 61045621
Итак, вектор начинает проигрывать между 10 и 100 тысячами хэшу. При малых значениях хэш проигрывает даже set
'у, сравниваясь на уровне 100 элементов. Дальше set
безнадежно проигрывает всем - как я понимаю, не только из-за O(N*ln N)
, но и из-за большого количества перераспределений памяти (члена reserve()
у него, в отличие от хэша и вектора, нет).
Как попроще проверить потребляемую память, я что-то не придумал, но понятно, что тут вектор всем даст фору :)
Словом, самый грустный вариант - set
, его использовать не имеет смысла вообще. При небольших размерах - до десятков тысяч - лучше брать вектор, а дальше смотреть, что важнее - скорость или память.
Все это на Visual C++ 2015, 32 bit.
Для Visual C++ 2010, 32 bit преимущества вектора видны еще ярче :) И хэш тут вообще проигрывает:
Set Hash Vector
-----------------------------------------------------------
N = 10: 813 1459 223
N = 100: 8688 10795 1448
N = 1000: 135905 102716 29086
N = 10000: 1623786 1068878 519483
N = 100000: 18334735 8822607 6316194
N = 1000000: 179540082 83667899 61899536
Кто хочет повторить для других компиляторов - you are welcome...
Кстати, с вектором можно еще оптимизировать - поскольку нам нужно только количество уникальных элементов - можно не использовать unique
с его перетасовкой в памяти, а просто пройти и пересчитать те элементы, у которых соседние не такие же.
Update. Я предполагал, что количество совпадений невелико; в комментариях меня поправили. Я все же не стал делать количество уникальных элементов мизерным - рука не лежит - но заполнил массив так:
for(int i = 0; i < N; ++i)
src.push_back((rand()%(N/5))*(i%2 ? 1 : -1));
Т.е. совпадений достаточно много, но все же уникальных элементов - O(N)
Результаты для 2015, миллиона дожидаться не стал:
Set Hash Vector
-----------------------------------------------------------
N = 10: 279 760 229
N = 100: 2693 2785 1185
N = 1000: 53087 24940 26121
N = 10000: 806965 273205 472123
N = 100000: 12350458 3440321 6006227
Граница несколько сместилась вниз, но принцип остался: set
пролетает, но бьет хэш на массивах до 100; хэш начинает лидировать где-то с 1000, а не с 10000.
В пределе, когда все N
элементов - единицы, результаты почти парадоксальные:
Set Hash Vector
-----------------------------------------------------------
N = 10: 200 895 219
N = 100: 888 1840 493
N = 1000: 7676 10020 2778
N = 10000: 73524 102685 25881
N = 100000: 733058 1167238 259100
N = 1000000: 7396809 11645557 3561249
вектор, и только вектор! Хэш в этом случае проигрывает даже set
'у.
Все, времени заниматься экспериментами просто больше нет; кто хочет - продолжайте :)
Update2 - В своей "Optimized C++" Гюнтерот недаром пишет, что unordered_set
хотя и дает эффект, но совершенно не тот, которого следовало бы ожидать, читая, как его расхваливают :) Цитата из книги: The hash table std::unordered_map
is faster than std::map
, but not by the order-of-magnitude difference that its reputation suggests.
O(N*lnN)
, но по реальному времени работы быстрее будет сортировка вектора + uniq...