Итак, сравниваем два метода. Полный код тут. Вкратце - чтоб не просто делители считать, но еще и использовать как-то наши vector
и map
, я еще и считаю общую сумму делителей и их степеней. Так, первое, что в голову пришло. Ну, и пришлось переписать немного код Qwertiy, чтоб лишнего поменьше делал...
Проверяю примерно так:
{
muTimer mu;
unsigned int total = 0;
for(unsigned int n = 2; n < N; ++n)
{
auto m = Qwertiy(n);
for(auto [p,k] : m) total += p + k;
}
mu.stop();
cout << "Qwertiy: " << total << " for " << mu.duration<muTimer::ms>() << " ms\n";
}
Заряжаем на 5 миллионов чисел:
Harry : 2479739720 for 4377 ms
Qwertiy: 2479739720 for 4056 ms
Компилировал VC++2017, 64-разрядное приложение, запускал на своей Intel(R) Core(TM) i5-2500 CPU @ 3.30 GHz 8G RAM --- Windows 7 x64.
Разница есть, но назвать ее критичной я не могу :) Вот если дописать резервирование памяти для вектора - тогда да, разница с 10% вырастает до 20%.
Кстати, замена map
на unordered_map
только ухудшает дело.
Update
А вот очень показательный пример - работаем с большими числами; код с проверкой подряд и код с проверкой с помощью готовой таблицы простых чисел - см. тут - показывает, как эффективнее факторизовать:
Harry : 647967786 for 9054 ms
PHarry : 647967786 for 105 ms
Qwertiy : 647967786 for 8975 ms
VecPrimes: 647967786 for 95 ms
Кстати, для больших чисел, когда главное - не во времени доступа к контейнеру, а в вычислениях - разница оказывается невелика.