Проблемы с эффектами памяти (Collatz Hailstone Sequence)

Question

Меня особенно интересовали последние несколько дней (более с алгоритмической точки зрения, чем математическая перспектива) при исследовании длины последовательности Hailstone данного номера (Collatz conjecture). Реализация рекурсивного алгоритма, вероятно, является самым простым способом вычисления длины, но мне показалось, что это ненужная трата времени вычисления. Многие последовательности перекрываются; принять для последовательности градины в примере 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 существу будет сделать, это начать в заданном числе и проработайте это последовательность Hailstone этого номера, пока она не встретится с номером уже в 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: ~ 65ms для итерационного каротажа, ~ 75 мс для рекурсивных не-каротажа
• n = 1,000,000: ~ 500 мс и ~ 900ms
• n = 10,000,000: ~ 14,000ms и ~ 10,000ms

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

Так что мой вопрос: Почему алгоритм каротажа внезапно начинает принимать дольше, чем наивный рекурсивный алгоритм при больших значениях 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 выдает ошибку памяти, поэтому его нельзя даже сравнивать, но, учитывая его поведение при более низких значениях, я чувствую, что он не будет хорошо сравнивать.

Answer 1

С манжетой, я предполагаю, что он проводит много времени, перераспределяя хэш-карту. Похоже, вы начинаете его пустым и продолжаете добавлять к нему материал. Это означает, что по мере роста размера ему потребуется выделить большую часть памяти для хранения ваших данных и пересчитать хеш для всех элементов, что является O (N). Попробуйте заранее выделить размер, который вы ожидаете от него. См. https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html для более подробного обсуждения.