В последние несколько дней меня особенно интересовало (больше с алгоритмической, чем с математической точки зрения) исследование длины последовательности градина данного числа (гипотеза Коллатца). Реализация рекурсивного алгоритма, вероятно, самый простой способ вычисления длины, но мне он показался ненужной тратой времени вычисления. Многие последовательности перекрываются; возьмем, например, последовательность града 3:

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Это имеет длину 7; более конкретно, требуется 7 операций, чтобы получить 1. Если мы возьмем 6:

6 -> 3 -> ...

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

Я попытался реализовать это на Java с помощью HashMap (казалось подходящим, учитывая O (1) вероятностную сложность получения/ввода):

import java.util.HashMap;

/* NOTE: cache.put(1,0); is called in main to act as the
 * 'base case' of sorts. 
 */

private static HashMap<Long, Long> cache = new HashMap<>();

/* Returns length of sequence, pulling prerecorded value from
 * from cache whenever possible, and saving unrecorded values
 * to the cache.
 */
static long seqLen(long n) {
    long count = 0, m = n;
    while (true) {
        if (cache.containsKey(n)) {
            count += cache.get(n);
            cache.put(m, count);
            return count;
        }
        else if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3*n + 1;
        }
        count++;
    }
}

По сути, seqLen начнет с заданного числа и будет работать с последовательностью града этого числа, пока не наткнется на число, уже находящееся в cache, и в этом случае он добавит его к текущему значению count, а затем зарегистрирует значение и связанная длина последовательности в HashMap как пара (key,val).

У меня также был следующий довольно стандартный рекурсивный алгоритм для сравнения:

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

Алгоритм ведения журнала должен, судя по всему, работать немного быстрее, чем наивный рекурсивный метод. Однако в большинстве случаев он работает ненамного быстрее, а для больших входных данных работает медленнее. Выполнение следующего кода дает времена, которые значительно различаются по мере изменения размера n:

long n = ... // However many numbers I want to calculate sequence
             // lengths for.

long st = System.nanoTime();
// Iterative logging algorithm
for (long i = 2; i < n; i++) {
    seqLen(i);
}
long et = System.nanoTime();
System.out.printf("HashMap algorithm: %d ms\n", (et - st) / 1000000);

st = System.nanoTime();
// Using recursion without logging values:
for (long i = 2; i < n; i++) {
    recSeqLen(i);
}
et = System.nanoTime();
System.out.printf("Recusive non-logging algorithm: %d ms\n",
                    (et - st) / 1000000);

• n = 1,000: ~2 мс для обоих алгоритмов
• n = 100,000: ~65 мс для итеративного ведения журнала, ~75 мс для рекурсивного без ведения журнала
• n = 1,000,000: ~500 мс и ~900 мс
• n = 10,000,000: ~14 000 мс и ~10 000 мс

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

Итак, мой вопрос: почему алгоритм ведения журнала внезапно начинает работать больше, чем наивный рекурсивный алгоритм для больших значений n?

РЕДАКТИРОВАТЬ:

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

private static final int CACHE_SIZE = 80000000;
private static long[] cache = new long[CACHE_SIZE];

static long seqLen(long n) {
    int count = 0;
    long m = n;

    do {
        if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3*n + 1;
        }
        count++;
    } while (n > m);

    count += cache[(int)n];
    cache[(int)m] = count;
    return count;
}

Перебор всего размера кеша (80 миллионов) теперь занимает всего 3 секунды, в отличие от 93 секунд при использовании рекурсивного алгоритма. Алгоритм HashMap выдает ошибку памяти, поэтому его даже нельзя сравнивать, но, учитывая его поведение при более низких значениях, у меня есть ощущение, что он не будет хорошо сравниваться.