Предыстория: я впервые изучил С++ и Java в школе несколько лет назад, но за последние 9 лет я не много программировал, поскольку моя предыдущая карьера не требовала этого.
Я решил изучить Project Euler, чтобы освежить мое программирование и решить проблему 14, которая предлагает найти целое число от одного до миллиона с самой длинной последовательностью Collatz. (Последовательность Collatz продолжается, начиная с начального числа, умножая число на 3 и добавляя 1, если это нечетно, или уменьшает число, если оно равно. Процесс продолжается до тех пор, пока число не достигнет 1.)
Сначала я решил проблему с использованием грубой силы, как показано в приведенном ниже коде.
int n;
long temp; // long is necessary since some Collatz sequences go outside scope of int
int[] n_length = new int[1000000];
for(n = 0; n < 1000000; n++){
temp = n + 1;
n_length[n] = 1;
while (temp > 1){
n_length[n]++;
if (temp % 2 == 0) temp = temp/2;
else temp = 3*temp + 1;
}
}
int max = 0;
int max_index = 0;
for (int i = 0; i < 1000000; i++){
if (n_length[i] > max){
max = n_length[i];
max_index = i;
}
}
System.out.println("The number with the longest Collatz sequence is " + (max_index + 1));
Я думал, что этот подход будет неэффективным, поскольку он выполняет алгоритм значительно чаще, чем необходимо. Любое число, которое является частью предыдущей последовательности последовательности Collatz, будет эффективно определять свою последовательность, и поэтому вы в конечном итоге вычисляете последовательность каждого отдельного номера каждый раз, когда она появляется в последовательности Collatz.
Я решил, что было бы лучше сохранить каждый номер на карте, как только он появится в последовательности Collatz, поэтому вам нужно будет только рассчитать его. Для этого я использовал TreeMap с числами, используемыми в качестве ключей, и ассоциированной длиной последовательности Collatz, как значение, и использовал рекурсивную функцию для вставки каждого числа в карту, как только он появился в последовательности Collatz. (См. Код ниже.)
public static TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();
public static void main(String[] args) {
tm.put((long)1, 1);
int maxVal = 1;
long keyWithMaxVal = 1;
int maybeMax;
for (long i = 2; i <= 1000000; i++){
if(!(tm.containsKey(i))){
maybeMax = addKey(i);
if (maybeMax >= maxVal){
maxVal = maybeMax;
keyWithMaxVal = i;
}
}
}
System.out.println("The number with the longest Collatz sequence is " + keyWithMaxVal + " with length " + maxVal);
}
public static int addKey(long key){
while (!(tm.containsKey(key))){
if (key % 2 == 0){
tm.put(key, 1 +addKey(key/2));
}
else{
tm.put(key, 1 + addKey(3*key + 1));
}
}
return tm.get(key);
}
Я использовал TreeMap, так как он автоматически сортирует ключи при вводе, так как я повторяю цикл for, я могу быстро проверить, были ли ключи уже вставлены, и избегать вызова метода addKey для добавления ключей, если только не нужно. Я думал, что этот алгоритм будет намного, намного быстрее.
Однако, когда я действительно запускал код, я с удивлением обнаружил, что алгоритм грубой силы мгновенно пришел к ответу, а рекурсивный алгоритм TreeMap занял гораздо больше времени, около 6 секунд. Когда я модифицировал свои программы до 5 миллионов, а не миллиона, разница стала еще более выраженной. Я добавил код для каждой программы, чтобы убедиться, что вторая программа работает меньше, чем первая, и действительно я определил, что метод addKey вызывается только один раз для каждого ключа, тогда как количество циклов while, необходимое для итерации в первой программе была равна сумме длин всех чисел последовательностей Collatz (т.е. намного чаще, чем число вызовов методов во втором алгоритме).
Итак, почему первый алгоритм намного быстрее второго? Это потому, что массив примитивов в первом алгоритме требует меньше ресурсов, чем объекты TreeMap Wrapper во втором? Является ли поиск на карте проверкой того, существует ли ключ уже медленнее, чем я ожидал (не должно быть время журнала?)? Рекурсивные методы, требующие большого количества вызовов методов, изначально медленнее? Или есть что-то еще, что я пропускаю
source: