И ещё раз о множествах...
В сети на удивление много обсуждений "что будет быстрее искать count или find"
... и "на хлопський розум" обсужданты приходят к выводу:- что якобы find будет быстрее, потому как если найдёт, то сразу возвратится...
- а count должен будет искать до конца.
P.S. И тема, откровенно говоря, выросла из того, что ... мой нынешний работодатель указал на мой код: "а вот find был бы намного быстрее, чем count, да и логику происходящего лучше раскрывает"
Рассуждения принципиально неверные в корне:
- set - не линейная структура, это хэш-таблица, только в которой ключи совпадают со значениями;
- там просто нет никакого "конца" - поиск в шэш-таблице делается нелинейно, могут использоваться в реализации разные алгоритмы;
- после нахождения в count элемента, зная что это set, множество, и count не может быть >1 - нужно сразу прекращать поиск ... и реализаторы не могут этого не учитывать.
Но интересно это проверить ... а заодно сравнить время поиска с аналогичным поиском в линейной структуре ... вектор - как простейший прототип. И, очевидно, что время поиска будет сильно различаться для наличия искомого элемента и его полного отсутствия.
Итак:
Код: Выделить всё
#include <iostream>
#include <set>
#include <vector>
#include <chrono>
int main(int argc, char *argv[])
{
unsigned long num = (argc > 1 && atol( argv[1] ) > 0) ?
atol(argv[1]) : 10000;
std::set<unsigned long> exs;
std::vector<unsigned long> exv;
for(unsigned long i = 0; i < num; i++ )
{
exs.insert( i );
exv.push_back( i );
}
auto testv = [](std::vector<unsigned long> &v, unsigned long n)->void { find(v.begin(), v.end(), n); };
for(unsigned long m: {num / 2, num + 1})
{
auto tbegin = std::chrono::steady_clock::now();
testv(exv, m);
auto tend = std::chrono::steady_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin);
std::cout << "elapsed time = " << dur.count() << std::endl;
}
void (*tests[])(std::set<unsigned long>&, unsigned long) = {
[](std::set<unsigned long> &s, unsigned long n)->void { s.find(n); },
[](std::set<unsigned long> &s, unsigned long n)->void { s.count(n); },
[](std::set<unsigned long> &s, unsigned long n)->void { s.contains(n); }
};
for(size_t i = 0; i < sizeof(tests) / sizeof(tests[0]); i++ )
for(unsigned long m: {num / 2, num + 1})
{
auto tbegin = std::chrono::steady_clock::now();
tests[i](exs, m);
auto tend = std::chrono::steady_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin);
std::cout << "elapsed time = " << dur.count() << std::endl;
}
}
:
).