Обработка больших групп чисел

Question

Проект Эйлера, задача 14:

Следующая итерационная последовательность определено для набора положительных целые числа:

n → n / 2 (n четно) n → 3n + 1 (n равно нечетные)

Использование правила выше и начиная с 13, мы генерируем следующее последовательность: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Видно, что эта последовательность (начиная с 13 и заканчивая 1) содержит 10 терминов. Хотя это не имеет было доказано еще (проблема Коллатца), это Считается, что все стартовые числа финиш в 1.

Какой стартовый номер, под одним миллион, производит самую длинную цепочку?

Мой первый инстинкт - создать функцию для вычисления цепочек и запускать ее с каждым числом от 1 до 1 миллиона. Очевидно, это занимает длинное время. По данным страницы Project Euler «About», путь дольше, чем это решение должно занять . Я обнаружил несколько проблем в Project Euler, связанных с большими группами чисел, которые программа, выполняемая часами, не заканчивала. Понятно, что я делаю что-то не так.

Как быстро обрабатывать большие группы чисел?

Что мне здесь не хватает?

Answer 1

Прочитайте о памятка .Ключевое понимание заключается в том, что если у вас есть последовательность, начинающаяся с A, которая имеет длину 1001, а затем вы получаете последовательность B, которая производит A, вам не придется повторять всю эту работу снова.

Answer 2

Это код в Mathematica, использующий запоминание и рекурсию.Всего четыре строки:)

f[x_] := f[x] = If[x == 1, 1, 1 + f[If[EvenQ[x], x/2, (3 x + 1)]]]; 
Block[{$RecursionLimit = 1000, a = 0, j},
 Do[If[a < f[i], a = f[i]; j = i], {i, Reverse@Range@10^6}];
 Print@a; Print[j];
]

Вывод .... длина цепочки´525´ и число ... ооооо ... шрифт слишком маленький!:)

Кстати, здесь вы можете увидеть график частоты для каждой длины цепи

Answer 3

Предположим, у вас есть функция CalcDistance(i), которая вычисляет «расстояние» до 1. Например, CalcDistance(1) == 0 и CalcDistance(13) == 9. Вот наивная рекурсивная реализация этой функции (в C #):

public static int CalcDistance(long i)
{
    if (i == 1)
        return 0;

    return (i % 2 == 0) ? CalcDistance(i / 2) + 1 : CalcDistance(3 * i + 1) + 1;
}

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

static int[] list = new int[1000000];

Мы предварительно заполняем каждое значение в списке -1, чтобы указать, что значение для этой позиции еще не рассчитано. После этого мы можем оптимизировать функцию CalcDistance():

public static int CalcDistance(long i)
{
    if (i == 1)
        return 0;

    if (i >= 1000000)
        return (i % 2 == 0) ? CalcDistance(i / 2) + 1 : CalcDistance(3 * i + 1) + 1;

    if (list[i] == -1)
        list[i] = (i % 2 == 0) ? CalcDistance(i / 2) + 1: CalcDistance(3 * i + 1) + 1;

    return list[i];
}

Если i >= 1000000, то мы не можем использовать наш список, поэтому мы всегда должны его вычислять. Если i < 1000000, то мы проверяем, есть ли значение в списке. Если нет, мы сначала вычисляем его и сохраняем в списке. В противном случае мы просто возвращаем значение из списка. С этим кодом для обработки всех миллионов чисел потребовалось около 120 мс.

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

Answer 4

Начиная с 1 000 000, создайте цепочку. Следите за каждым числом, сгенерированным в цепочке, поскольку вы точно знаете, что их цепочка меньше, чем цепочка для начального номера. Как только вы достигнете 1, сохраните начальный номер вместе с длиной цепи. Возьмите следующее наибольшее число, которое не было сгенерировано ранее, и повторите процесс.

Это даст вам список чисел и длину цепочки. Возьмите наибольшую длину цепи, и это ваш ответ.

Я сделаю код для уточнения.

 public static long nextInChain(long n) {
    if (n==1) return 1;

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


public static void main(String[] args) {
    long iniTime=System.currentTimeMillis();
    HashSet<Long> numbers=new HashSet<Long>();
    HashMap<Long,Long> lenghts=new HashMap<Long, Long>();

    long currentTry=1000000l;
    int i=0;
    do {
        doTry(currentTry,numbers, lenghts);
        currentTry=findNext(currentTry,numbers);
        i++;
    } while (currentTry!=0);
    Set<Long> longs = lenghts.keySet();
    long max=0;
    long key=0;
    for (Long aLong : longs) {
        if (max < lenghts.get(aLong)) {
            key = aLong;
            max = lenghts.get(aLong);
        }
    }
    System.out.println("number = " + key);
    System.out.println("chain lenght = " + max);
    System.out.println("Elapsed = " + ((System.currentTimeMillis()-iniTime)/1000));
}


private static long findNext(long currentTry, HashSet<Long> numbers) {
    for(currentTry=currentTry-1;currentTry>=0;currentTry--) {
        if (!numbers.contains(currentTry)) return currentTry;
    }
    return 0;
}

private static void doTry(Long tryNumber,HashSet<Long> numbers, HashMap<Long, Long> lenghts) {
    long i=1;
    long n=tryNumber;
    do {
        numbers.add(n);
        n=nextInChain(n);
        i++;
    } while (n!=1);
    lenghts.put(tryNumber,i);
}

Answer 5

Этот вариант не использует HashMap, но пытается только не повторять первые 1000000 чисел. Я не использую хэш-карту, поскольку наибольшее найденное число составляет около 56 миллиардов, и хэш-карта может дать сбой.

Я уже сделал несколько premature optimization. Вместо / я использую >>, вместо % я использую &. Вместо * я использую немного +.

void Main()
{
    var elements = new bool[1000000];       

    int longestStart = -1;
    int longestRun = -1;

    long biggest = 0;

    for (int i = elements.Length - 1; i >= 1; i--) {
        if (elements[i]) {
            continue;
        }

        elements[i] = true;

        int currentStart = i;
        int currentRun = 1;

        long current = i;

        while (current != 1) {
            if (current > biggest) {
                biggest = current;
            }

            if ((current & 1) == 0) {
                current = current >> 1;
            } else {
                current = current + current + current + 1;
            }

            currentRun++;

            if (current < elements.Length) {
                elements[current] = true;
            }
        }

        if (currentRun > longestRun) {
            longestStart = i;
            longestRun = currentRun;
        }
    }   

    Console.WriteLine("Longest Start: {0}, Run {1}", longestStart, longestRun);
    Console.WriteLine("Biggest number: {0}", biggest);
}

Answer 6

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