Обновление: программы на C ++ (как показано ниже) были скомпилированы без дополнительных флагов, т.е. g++ program.cpp.Однако повышение уровня оптимизации не меняет того факта, что перебор работает быстрее, чем метод запоминания (0,1 секунды VS 1 секунда на моем компьютере).
Context
Я пытаюсь вычислить число (<1 миллион) с самой длинной <a href="https://en.wikipedia.org/wiki/Collatz_conjecture" rel="nofollow noreferrer"> последовательностью Коллатца .Я написал алгоритм грубой силы и сравнил его с предложенной оптимизированной программой (которая в основном использует мемоизацию).
Мой вопрос: что может быть причиной того, что грубая сила выполняется быстрее, чем предположительно оптимизированная(памятка) версия на C ++?
Ниже приведены сравнения, которые я имею на своем компьютере (Macbook Air);времена в начале кода программы в комментариях.
C ++ (грубая сила)
/**
* runs in 1 second
*/
#include <iostream>
#include <vector>
unsigned long long nextSequence(unsigned long long n)
{
if (n % 2 == 0)
return n / 2;
else
{
return 3 * n + 1;
}
}
int main()
{
int max_counter = 0;
unsigned long long result;
for (size_t i = 1; i < 1000000; i++)
{
int counter = 1;
unsigned long long n = i;
while (n != 1)
{
n = nextSequence(n);
counter++;
}
if (counter > max_counter)
{
max_counter = counter;
result = i;
}
}
std::cout << result << " has " << max_counter << " sequences." << std::endl;
return 0;
}
C ++ (памятка)
/**
* runs in 2-3 seconds
*/
#include <iostream>
#include <unordered_map>
int countSequence(uint64_t n, std::unordered_map<uint64_t, uint64_t> &cache)
{
if (cache.count(n) == 1)
return cache[n];
if (n % 2 == 0)
cache[n] = 1 + countSequence(n / 2, cache);
else
cache[n] = 2 + countSequence((3 * n + 1) / 2, cache);
return cache[n];
}
int main()
{
uint64_t max_counter = 0;
uint64_t result;
std::unordered_map<uint64_t, uint64_t> cache;
cache[1] = 1;
for (uint64_t i = 500000; i < 1000000; i++)
{
if (countSequence(i, cache) > max_counter)
{
max_counter = countSequence(i, cache);
result = i;
}
}
std::cout << result << std::endl;
return 0;
}
В Python памяткатехника действительно работает быстрее.
Python (запоминание)
# runs in 1.5 seconds
def countChain(n):
if n in values:
return values[n]
if n % 2 == 0:
values[n] = 1 + countChain(n / 2)
else:
values[n] = 2 + countChain((3 * n + 1) / 2)
return values[n]
values = {1: 1}
longest_chain = 0
answer = -1
for number in range(500000, 1000000):
if countChain(number) > longest_chain:
longest_chain = countChain(number)
answer = number
print(answer)
Python (перебор)
# runs in 30 seconds
def countChain(n):
if n == 1:
return 1
if n % 2 == 0:
return 1 + countChain(n / 2)
return 2 + countChain((3 * n + 1) / 2)
longest_chain = 0
answer = -1
for number in range(1, 1000000):
temp = countChain(number)
if temp > longest_chain:
longest_chain = temp
answer = number
print(answer)