Комментарии 30
А какое примерно отношение максимального числа к количеству ключей в кэше? Может проще иметь хеш-таблицу ключей, которые на предыдущем шаге привели к 1? Тогда храниться все будет в разы компактнее => больше ключей поместится в память, => можно будет быстрее исследовать больший диапазон. А после того, как мы достигли верхней границы, пробегаемся по ключам и считаем уже для них последовательности сведения к 1 (здесь можно и с кешированием полных путей) - то есть такая двухступенчатая ракета ;)
Ответ на этот вопрос сложнее чем кажется, варьируется сильно от диапазона и стратегии хранения ключей в кэше.
В статье есть ссылка, про исследование кэша на оптимальность: https://habr.com/ru/articles/673224/
В случае с хэш-таблицей, у меня есть подозрение, что на больших числах кэш все равно будет переполняться и сильно тормозить. Нужна стратегия чистки памяти, в моем случае soft references помогли
Так это без разницы. Храните по ключу null в качестве полезной нагрузки - это будет съедать явно меньше памяти, чем вся цепочка. Смысл моей идеи в том, чтобы опираться только на факт того, что встреченное число приводит последовательность после него к 1, и по завершению расчета проитерироваться по этим найденным фактам. Вот я и спрашиваю, какое отношение верхней границы к количеству известных цепочек, и главное, как меняется эта пропорция с увеличением N? Если она сублинейна - то дело выгодное :)
С текущей конфигурацией кэша:
при проходе 23млн кэш хранит в себе каждый ключ,
на 24м миллионе освобождает память и выкидывает 15млн ключей из памяти.
Ну и в дальнейшем эти история повторяется, размер кэша скачет от 8 до 23х млн значений, вне зависимости от верхней границы.
Но вообще, это количество, при использовании обычного кэша действительно около-линейно.
Ваш комментарий натолкнул меня на мысль (хотя возможно это и имелось ввиду):
Когда мы итерируемся от 1 до +ထ, и находимся в некоторой точке K, то если рекурсия заходит в любое число, меньшее К, мы можем завершать проход, и начинать следующую итерацию, увеличив K на 1(поскольку, по умолчанию, если мы попали в число, меньшее чем K, то это значит, что некоторое время назад мы его валидировали, и успешно)
Если нам не нужно количество шагов, то можно вообще не использовать никакой кэш, а написать что то вроде:
функция, которая выходит из бесконечного цикла либо при приходе в 1, либо в точку, уже валидированную ранее:
static void validateNumberCollatz(BigInteger n, long maxValidated){
while(!n.equals(BigInteger.ONE)){
if(n.compareTo(BigInteger.valueOf(maxValidated))<=0) break;
if(!n.testBit(0)) n = n.divide(BigInteger.valueOf(2));
else n = n.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE);
}
}метод main
for (long i = 1; i < 100_000_000_000L; i++) {
validateNumberCollatz(BigInteger.valueOf(i), i-1);
}Более того, первые 50млн чисел этот код проверяет(но не считает шаги) на соответствие гипотезе за 10 секунд!
Это зависит от развития последовательности с какого-то числа - если тех, что быстро уходят вниз, много, то да. Но нет гарантии, что последовательность не будет долго болтаться где-то между K и K*3, и я бы делал так - если число меньше К - то сразу перезапускать, иначе проверить в хэш-таблице. Если там нет - сделать следующее действие. То есть меньшие числа - перезапуск, большие - кэш.
А если проверять на чётность не всё число, а только последнюю цифру, то не экономичнее выйдет по ресурсам?
В статье есть про это строчка:
Но затем заменил на более лаконичное:
private static boolean isEven(BigDecimal n) {return !n.testBit(0);}А, или вы про передачу в сам метод только последней цифры?
У четных чисел, представленных в двоичной системе, нулевой бит равен 0. Что значит проверять последнюю цифру?
Не очень понятно, зачем так извращаться, тем более с Guava, если программа на С без оптимизаций справляется за 11 секунд (в однопоточном режиме).
ЯП не панацея от всех бед, статья скорее про способы оптимизации самого алгоритма.
Ну так и с алгоритмом можно поступить проще. Если вам не нужно знать точное число шагов, а только факт завершения, то достаточно проверить, что текущее число меньше максимального уже проверенного.
Даже если вы таки хотите считать точное число шагов, то полноценный кэш тоже не нужен. Достаточно обычного массива с числом шагов, индексируемого целым числом.
Интересный факт, в википедии указано, что «По состоянию на июль 2023 года проверены все натуральные числа до 10¹⁰⁰ (десять в сотой степени), и каждое из них продемонстрировало соответствие гипотезе Коллатца.»
Число 10¹⁰⁰ взято с потолка. Ссылки на источник в википедии нет. Да и не скоро появятся компьютерные мощности для такой проверки. В английской вики указано 2⁶⁸ ≈ 3*10²⁰ на июль 2020. В русской (версия от 06.08.2023) 9,8*10²¹ на апрель 2021. Это больше похоже на правду.
А тут нет такой зависимости, что с ростом начального числа подцепочка, которую можно применить, в большинстве случаев является последней, то есть, генерирована с БОЛЬШЕГО начального числа? Тогда никаких мапов выгоднее не применять, а просто последнее начальное число с количеством цепочки хранить в массиве, а поиск в этом массиве начинать с конца, с самом большом числе и просто перебирать?
Логично же, что число с большей длиной цепочки при прохождении далее по числам по порядку будет чаще задействоваться?
Не уверен, что до конца понял вашу идею. Можете привести пример цепочки/подцепочки и поиска?
Если я правильно понял, то хвост рекурсии для большинства пар (N, N + 1) совпадает. Из-за чего хранить все значения от 2 до N - 1 в кеше очень расточительно по памяти. Достаточно хранить те, которые присутствовали на последнем шаге (на M последних шагах).
Пример
1000 -> 500 -> 250 -> 125 -> 376 -> 188 -> 94 -> 47 -> 142 -> 71 -> 214 -> 107 -> 322 -> 161 -> 484 -> 242 -> 121 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
1001 -> 3004 -> 1502 -> 751 -> 2254 -> 1127 -> 3382 -> 1691 -> 5074 -> 2537 -> 7612 -> 3806 -> 1903 -> 5710 -> 2855 -> 8566 -> 4283 -> 12850 -> 6425 -> 19276 -> 9638 -> 4819 -> 14458 -> 7229 -> 21688 -> 10844 -> 5422 -> 2711 -> 8134 -> 4067 -> 12202 -> 6101 -> 18304 -> 9152 -> 4576 -> 2288 -> 1144 -> 572 -> 286 -> 143 -> 430 -> 215 -> 646 -> 323 -> 970 -> 485 -> 1456 -> 728 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
1002 -> 501 -> 1504 -> 752 -> 376 -> 188 -> 94 -> 47 -> 142 -> 71 -> 214 -> 107 -> 322 -> 161 -> 484 -> 242 -> 121 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
1003 -> 3010 -> 1505 -> 4516 -> 2258 -> 1129 -> 3388 -> 1694 -> 847 -> 2542 -> 1271 -> 3814 -> 1907 -> 5722 -> 2861 -> 8584 -> 4292 -> 2146 -> 1073 -> 3220 -> 1610 -> 805 -> 2416 -> 1208 -> 604 -> 302 -> 151 -> 454 -> 227 -> 682 -> 341 -> 1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Жирным выделены значения, совпавшие с предыдущим вычислением.
Ну даже в вашем примере 1002 и 1003 демонстрируют, насколько разными могут быть пути в 1.
+в паре рядом стоящих чисел всегда одно четное, а другое - нет, поэтому их дороги разойдутся сразу же(одно поделится на 2, второе умножится на 3). Мне не очевидно, что эти хвосты будут совпадать
Да, с 1002 и 1003 на 10% совпадают, а 1001 и 1002 на 90%. В среднем может оказаться что программа с таким подходом отработает за 10 минут вместо 7, но памяти потребует на порядок меньше. На больших числах это вполне может сработать, особенно если хранить 2-3 предыдущих цепочки.
Про память сложно спорить.
Но мне все равно неочевидно что у рядом стоящих чисел должны быть схожие цепочки. Раз уж мы делим на 2, я бы подумал про хранение таких цепочек в радиусе от чисел- 2ⁿ, условно сохранять цепочки из чисел 63,65, 1023,1025 и тд.
Но опять же, мне сложно отследить их связность без тестирования на больших данных, либо математического/логического вывода
Я накидал простой скрипт, чтобы это проверить. На большинстве диапазонов до 1000000 средняя длина общей цепочки (N, N + 1) равна половине средней длины цепочки для N. Для двух и трех последних чисел скорее всего охват будет до 90%, но нужно проверить.
Мне кажется вполне логичным предположить, что на больших числах эта тенденция не будет меняться.
Функция расчета
function mean_length(from, to)
local diff_length = [];
local curr_length = [];
local result = [];
local pred = Set();
for i = from:to
local curr = Set();
local t = i;
push!(curr, t)
while t > 1
if t % 2 == 0
t = div(t, 2)
else
t = t * 3 + 1
end
push!(curr, t)
end
push!(curr_length, length(curr))
push!(diff_length, length(intersect(pred, curr)))
pred = curr
end
mean(curr_length), mean(diff_length)
endВывод для разных диапазонов
for i = 1:10
println(i*100000, ":", (i+1)*100000, " -> ", mean_length(i*100000, (i+1)*100000))
end
100000:200000 -> (122.84768152318478, 61.473475265247345) # средняя длина, средняя разность
200000:300000 -> (128.31124688753113, 64.26448735512645)
300000:400000 -> (131.92660073399267, 65.98678013219867)
400000:500000 -> (134.72327276727233, 67.37789622103779)
500000:600000 -> (136.33956660433395, 68.02739972600274)
600000:700000 -> (138.21428785712143, 69.15675843241567)
700000:800000 -> (139.85148148518516, 69.9819001809982)
800000:900000 -> (140.99823001769983, 70.55780442195578)
900000:1000000 -> (142.59238407615925, 71.4380156198438)
1000000:1100000 -> (142.85390146098538, 71.35284647153529)
Упрощенно можно рассматривать условием завершения не достижение единицы а достижение 2 в степени n.
Я далеко не математик, но интуитивно понял, что главная проблема здесь в том, что мы не знаем, до каких пор будет расти число, поскольку множитель 3 больше делителя 2, на который мы делим число в случае его четности.
Неверно. Мы либо пытаемся доказаться, что функция точно убывающая (то бишь сходится к некоторому значению), либо что функцией можно покрыть все числа.
Ну, когда я это писал, в моей голове было что-то схожее со сходимостью, из разряда, что если каждый четный член в последовательности увеличивается на 1, а каждый нечетный уменьшается на 2 относительно предыдущего, то с какого бы мы числа не начали, она уменьшится до определенного числа.
Я хотел сказать только то, что в случае этой последовательнсти, такого явного зигзага, который доказуемо уменьшается - нет.
Это называется мемоизация.
Дилемма 3n+1 на Java. Кэшируем рекурсию