Хранение известных последовательностей в C

Question

Я работаю на Проект Euler #14 в C и выяснили основной алгоритм; Тем не менее, он работает невыносимо медленного для большого количества, например, 2 000 000, по желанию; Я предполагаю, потому что она должна генерировать последовательность снова и снова, хотя должен быть способ хранить известные последовательности (например, как только мы доберемся до 16, мы знаем из предыдущего опыта, что следующие цифры 8, 4, 2 , тогда 1).

Я не совсем уверен, как это сделать с массивом CIS-длины C, но должен быть хороший способ (это удивительно эффективно, я уверен). Заранее спасибо.

Вот что у меня в настоящее время есть, если это поможет.

#include <stdio.h>
#define UPTO 2000000

int collatzlen(int n);

int main(){
    int i, l=-1, li=-1, c=0;
    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);
    return 1;
}

/* n != 0 */
int collatzlen(int n){
    int len = 0;
    while(n>1) n = (n%2==0 ? n/2 : 3*n+1), len+=1;
    return len;
}

Answer 1

Ваша оригинальная программа нуждается в 3,5 секунды на моей машине. Это невыносимо медленно для вас?

Моя грязная и уродливая версия нуждается в 0,3 секунды. Он использует глобальный массив для хранения уже рассчитанных значений. И использовать их в будущих расчетах.

int collatzlen2(unsigned long n);
static unsigned long array[2000000 + 1];//to store those already calculated

int main()
{
    int i, l=-1, li=-1, c=0;
    int x;
    for(x = 0; x < 2000000 + 1; x++) {
        array[x] = -1;//use -1 to denote not-calculated yet
    }

    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen2(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);

    return 1;
}

int collatzlen2(unsigned long n){
    unsigned long len = 0;
    unsigned long m = n;
    while(n > 1){
        if(n > 2000000 || array[n] == -1){ // outside range or not-calculated yet
            n = (n%2 == 0 ? n/2 : 3*n+1);
            len+=1;
        }
        else{ // if already calculated, use the value
            len += array[n];
            n = 1; // to get out of the while-loop
        }
    }
    array[m] = len;
    return len;
}

Answer 2

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

int lengthfrom[UPTO] = {};

Если ваш максимальный размер - это несколько миллионов, то мы говорим мегабайты памяти, которые должны легко вписываться в ОЗУ одновременно.

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

Не испытывайте искушения использовать локальную переменную для массива такого размера: это попытается выделить ее в стеке, что не будет достаточно большим и, вероятно, будет разбиться.

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

Answer 3

Если я правильно вспомнку, ваша проблема не является медленным алгоритмом: алгоритм, который у вас сейчас достаточно быстро для того, что PE просит вас сделать. Проблема в переполнении: вы иногда в конечном итоге умножьте ваш номер на 3 на 3 так много раз, что в конечном итоге он в конечном итоге превысит максимальное значение, которое может храниться в подписанном INT. Используйте unsigned ints, и если это все еще не работает (но я уверен, что он делает), используйте 64 бит INT (long long).

Это должно работать очень быстро, но если вы хотите сделать это даже быстрее, другие ответы уже рассмотрели это.