Я решил проверить решения Дмана и Чарльза Бейли здесь.Я назову их решениями A и B соответственно.Мой тест - посещение каждой комбинации размером vector<int> = 100, 5 одновременно.Вот код теста:
Код теста
struct F
{
unsigned long long count_;
F() : count_(0) {}
bool operator()(std::vector<int>::iterator, std::vector<int>::iterator)
{++count_; return false;}
};
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double> sec;
typedef std::chrono::duration<double, std::nano> ns;
int n = 100;
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 0);
std::vector<int>::iterator r = v.begin() + 5;
F f;
Clock::time_point t0 = Clock::now();
do
{
f(v.begin(), r);
} while (next_combination(v.begin(), r, v.end()));
Clock::time_point t1 = Clock::now();
sec s0 = t1 - t0;
ns pvt0 = s0 / f.count_;
std::cout << "N = " << v.size() << ", r = " << r-v.begin()
<< ", visits = " << f.count_ << '\n'
<< "\tnext_combination total = " << s0.count() << " seconds\n"
<< "\tnext_combination per visit = " << pvt0.count() << " ns";
}
Весь код был скомпилирован с использованием clang ++ -O3 на Intel Core i5 с частотой 2,8 ГГц.
Решение A
Решение A приводит к бесконечному циклу.Даже когда я делаю n очень маленьким, эта программа никогда не завершается.Впоследствии по этой причине проголосовали.
Решение B
Это редактирование.Решение B изменилось в процессе написания этого ответа.Сначала он давал неправильные ответы, а из-за очень быстрого обновления теперь дает правильные ответы.Он печатает:
N = 100, r = 5, visits = 75287520
next_combination total = 4519.84 seconds
next_combination per visit = 60034.3 ns
Решение C
Далее я попробовал решение из N2639 , которое выглядит очень похоже на решение A, но работаетправильно.Я назову это решение C, и оно напечатает:
N = 100, r = 5, visits = 75287520
next_combination total = 6.42602 seconds
next_combination per visit = 85.3531 ns
Решение C в 703 раза быстрее, чем решение B.
Решение D
Наконец, решение D найдено здесь .Это решение имеет другую сигнатуру / стиль и называется for_each_combination и используется так же, как std::for_each.Приведенный выше код драйвера изменяется между вызовами таймера следующим образом:
Clock::time_point t0 = Clock::now();
f = for_each_combination(v.begin(), r, v.end(), f);
Clock::time_point t1 = Clock::now();
Решение D выводит на печать:
N = 100, r = 5, visits = 75287520
for_each_combination = 0.498979 seconds
for_each_combination per visit = 6.62765 ns
Решение D в 12,9 раз быстрее, чем решение C, и в 9000 раз быстреечем решение B.
Я считаю, что это относительно небольшая проблема: только 75 миллионов посещений.По мере того как количество посещений увеличивается до миллиардов, расхождение в производительности между этими алгоритмами продолжает расти.Решение B уже громоздко.Решение C в конечном итоге становится громоздким.Решение D - это самый эффективный алгоритм для посещения всех известных мне комбинаций.
Ссылка , показывающая решение D , также содержит несколько других алгоритмов для перечисления и посещения перестановок с различными свойствами (циклический,обратимый и т. д.).Каждый из этих алгоритмов был разработан с производительностью в качестве одной из целей.И обратите внимание, что ни один из этих алгоритмов не требует, чтобы начальная последовательность была в отсортированном порядке.Элементы не должны быть даже LessThanComparable.