Оптимизация гипотезы Коллатца в C ++

Question

Оптимизация гипотезы Коллатца в C ++

В задаче ProjectEuler № 14 нужно найти самую длинную цепочку Collatz, до 1 миллиона. Я нашел на полпути приличный способ сделать это, однако, мне кажется, что я просто глуп, потому что не могу найти способ сделать этот код более эффективным (код должен распечатывать решение только после его тестирования От 1 до 1 миллиона, но через 10 минут ничего не распечатывается). Я неправильно решаю эту проблему или есть способ оптимизировать мой существующий код?

#include <iostream>
using namespace std;

int main()
{
int i;
int x;
int n;
int superN;
int superI;

superN = 0;
superI = 0;

for (i = 1; i <= 1000000; i++) {
x = i;
n = 1;

do {
if (x % 2 == 0) {
x = x / 2;
}

if (x % 2 == 1 && x != 1) {
x = 3 * x + 1;
}

n++;

if (n > superN) {
superN = n;
superI = i;
}
} while (x != 1);
}

cout << "The number " << superI << " ran for " << superN << " terms.";
system("pause");
return 0;
}

0

c++collatz optimization

Решение

Другие решения

Я бы предложил не использовать памятку, так как для меня она работает медленнее; в моем случае (до 10 000 000) приведенный ниже код работает быстрее без запоминания.
Основные изменения:

только тестирование, если текущее число хотя бы один раз (не нужно для else-if).
использование побитовой операции вместо операции по модулю (немного быстрее)

Кроме того, я не знаю, почему ваш код такой длинный (мой меньше 200 миллисекунд), может быть, вы компилируете как отладку?

bool isEven(uint64_t value)
{
return (!(value & 1));
}

uint64_t solveCollatz(uint64_t start)
{
uint64_t counter = 0;
while (start != 1)
{
if(isEven(start))
{
start /= 2;
}
else
{
start = (3 * start) + 1;
}
counter++;
}

return counter;
}

0

Если вы можете использовать встроенные функции компилятора, особенно при подсчете и удалении конечных нулей, вы поймете, что вам не нужно переходить в основном цикле, вы всегда будете чередовать нечетные и четные. Методы запоминания, которые были представлены ранее, редко будут замыкаться вокруг математики, которую вы делаете, так как мы имеем дело с градообразующими числами — кроме того, большинство чисел имеют только одну точку входа, поэтому, если вы видите их один раз, вы никогда не увижу их снова.

В GCC это будет выглядеть примерно так:

#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <map>
using namespace std;

using n_iPair = std::pair<uint32_t, uint64_t>;

auto custComp = [](n_iPair a, n_iPair b){
return a.first < b.first;
};

int main()
{
uint64_t x;
uint64_t n;
n_iPair Super = {0,0};

for (auto i = 1; i <= 1000000; i++){
x = i;
n = 0;

if (x % 2 == 0) {
n += __builtin_ctz(x); // account for all evens
x >>= __builtin_ctz(x); // always returns an odd
}

do{ //when we enter we're always working on an odd number

x = 3 * x + 1; // always increases an odd to an even
n += __builtin_ctz(x)+1; // account for both odd and even transfer
x >>= __builtin_ctz(x); // always returns odd

}while (x != 1);

Super = max(Super, {n,i}, custComp);

}

cout << "The number " << Super.second << " ran for " << Super.first << " terms.\n";
return 0;
}

0

Источник

Accepted Answer

У вас есть несколько небольших проблем:

Я уверен, что вы переполнены int тип данных. Использовать uint64_t сделать это гораздо менее вероятно.
Вы должны только обновить superI а также superN вне цикла while. Это не должно иметь значения, но ухудшает производительность.
На каждой итерации вы должны только изменить x один раз. В настоящее время вы можете изменить его дважды, что может привести к тому, что вы попадете в бесконечный цикл. И ваш расчет n также будет выключен
Используйте памятку для улучшения производительности, кэшируя старые результаты.

Применяя это, вы можете придумать такой код:

#include <cstdint>
#include <iostream>
#include <map>
using namespace std;

int main()
{
uint64_t i;
uint64_t x;
uint64_t n;
uint64_t superN;
uint64_t superI;

std::map<uint64_t, uint64_t> memory;

superN = 0;
superI = 0;

for (i = 1; i <= 1000000; i++) {
x = i;
n = 1;

do {
if (memory.find(x) != memory.end()) {
n += memory[x];
break;
}

if (x % 2 == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}

n++;
} while (x != 1);

if (n > superN) {
superN = n;
superI = i;
}

memory[i] = n;
}

cout << "The number " << superI << " ran for " << superN << " terms.\n";
system("pause");
return 0;
}

На вывод которого уходит 4 секунды:

The number 837799 ran for 556 terms.

1