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

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

Я не совсем уверен, как это сделать с массивом фиксированной длины 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;
}

c collatz
person Aaron Yodaiken    schedule 22.06.2010    source источник
comment
пожалуйста, попробуйте выкопать свой вопрос C из вашего конкретного приложения. тогда у вас гораздо больше шансов получить ответ.   -  person Jens Gustedt    schedule 22.06.2010
comment
возможный дубликат вопроса 14 проекта Эйлера (проблема Коллатца)   -  person kennytm    schedule 22.06.2010

Ответы (3)


arrow_upward
3
arrow_downward

Вашей исходной программе требуется 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;
}
person yehnan    schedule 22.06.2010
comment
+1 просто сохранит несколько из них, и если 3n + 1 больше, чем максимальное значение, которое вы сохраняете, вычислите его снова. 2 ~ 3 лишних строки очень простого кода для увеличения скорости на порядок! - person BlueRaja - Danny Pflughoeft; 22.06.2010

arrow_upward
1
arrow_downward

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

int lengthfrom[UPTO] = {};

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

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

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

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

person psmears    schedule 22.06.2010
comment
Проблема с этим подходом в том, что вы не можете знать правильное значение UPTO. - person Itay Karo; 22.06.2010
comment
Истинный. Но, учитывая, что цель состоит в том, чтобы просто найти правильный ответ на конкретный вопрос (а не создавать программу, которая успешно работает на всех входных данных), не повредит увеличить размер массива и запустить его снова. Если это не сработает (когда массив начинает приближаться к размеру памяти машины), можно реализовать один из более сложных подходов (например, хеш-таблица с корзинами), но вы можете сэкономить время, попробовав простой путь первый :) - person psmears; 22.06.2010

arrow_upward
1
arrow_downward

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

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

person IVlad    schedule 22.06.2010