Пример очень специфичный. У вас уже есть существующий прототип, вы знаете, как он себя ведет и что должен делать. У вас как раз-таки есть те самые гарантии, что после написание тестов ничего не изменится. Спецификации, черт побери!
А выше люди говорят о том, что одна из главных проблем TDD это то, что при доработке сложных систем, изменений api, например, у написанных заранее тестов есть неиллюзорный шанс оказаться в мусорной корзине.
Есть мнение, что тесты, написанные после модуля, будут проходить с большей вероятностью, чем тесты написанные заранее.
Да и я склонен верить, что самостоятельное тестирование собственного приложения после его написания, выявит меньше потенциальных багов, чем обратная ситуация.
С текущей конфигурацией кэша: при проходе 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 секунд!
Ну, когда я это писал, в моей голове было что-то схожее со сходимостью, из разряда, что если каждый четный член в последовательности увеличивается на 1, а каждый нечетный уменьшается на 2 относительно предыдущего, то с какого бы мы числа не начали, она уменьшится до определенного числа.
Я хотел сказать только то, что в случае этой последовательнсти, такого явного зигзага, который доказуемо уменьшается - нет.
Но мне все равно неочевидно что у рядом стоящих чисел должны быть схожие цепочки. Раз уж мы делим на 2, я бы подумал про хранение таких цепочек в радиусе от чисел- 2ⁿ, условно сохранять цепочки из чисел 63,65, 1023,1025 и тд.
Но опять же, мне сложно отследить их связность без тестирования на больших данных, либо математического/логического вывода
Ну даже в вашем примере 1002 и 1003 демонстрируют, насколько разными могут быть пути в 1. +в паре рядом стоящих чисел всегда одно четное, а другое - нет, поэтому их дороги разойдутся сразу же(одно поделится на 2, второе умножится на 3). Мне не очевидно, что эти хвосты будут совпадать
Конкретно этот пароль было бы логично держать в файле dangerous_passwords.txt
Но вообще я не проводил ресерча по настоящим методам валидаций паролей, я понимаю, что там все сложнее, чем : 8 символов и спецзнак. Тут скорее я использовал стереотип, который был у меня в голове для примера. Я действительно брал эти условия с потолка. Прям совсем с потолка.
В случае с хэш-таблицей, у меня есть подозрение, что на больших числах кэш все равно будет переполняться и сильно тормозить. Нужна стратегия чистки памяти, в моем случае soft references помогли
Про null references и equals - подписываюсь под каждым словом.
Благодарю, поправил.
Я что-то не понимаю, или lombok - это не многопоточность? На моей памяти был библиотекой для сокращения количества бойлер-плейт кода)
Пример очень специфичный. У вас уже есть существующий прототип, вы знаете, как он себя ведет и что должен делать. У вас как раз-таки есть те самые гарантии, что после написание тестов ничего не изменится. Спецификации, черт побери!
А выше люди говорят о том, что одна из главных проблем TDD это то, что при доработке сложных систем, изменений api, например, у написанных заранее тестов есть неиллюзорный шанс оказаться в мусорной корзине.
Да, склоняюсь, к тому, что это оптимальное решение из тех, что у меня в голове сейчас.
Есть мнение, что тесты, написанные после модуля, будут проходить с большей вероятностью, чем тесты написанные заранее.
Да и я склонен верить, что самостоятельное тестирование собственного приложения после его написания, выявит меньше потенциальных багов, чем обратная ситуация.
Дико извиняюсь, в комментарии выше изобрел велосипед, вы буквально это и сказали.
Ну, написал реализацию к вашей мысли и время выполнения замерил)
С текущей конфигурацией кэша:
при проходе 23млн кэш хранит в себе каждый ключ,
на 24м миллионе освобождает память и выкидывает 15млн ключей из памяти.
Ну и в дальнейшем эти история повторяется, размер кэша скачет от 8 до 23х млн значений, вне зависимости от верхней границы.
Но вообще, это количество, при использовании обычного кэша действительно около-линейно.
Ваш комментарий натолкнул меня на мысль (хотя возможно это и имелось ввиду):
Когда мы итерируемся от 1 до +ထ, и находимся в некоторой точке K, то если рекурсия заходит в любое число, меньшее К, мы можем завершать проход, и начинать следующую итерацию, увеличив K на 1(поскольку, по умолчанию, если мы попали в число, меньшее чем K, то это значит, что некоторое время назад мы его валидировали, и успешно)
Если нам не нужно количество шагов, то можно вообще не использовать никакой кэш, а написать что то вроде:
функция, которая выходит из бесконечного цикла либо при приходе в 1, либо в точку, уже валидированную ранее:
метод main
Более того, первые 50млн чисел этот код проверяет(но не считает шаги) на соответствие гипотезе за 10 секунд!
Давно вынашивал схожие сомнения на этот счет.
Тезисно выразил в статье : https://habr.com/ru/articles/839658/
Ну, когда я это писал, в моей голове было что-то схожее со сходимостью, из разряда, что если каждый четный член в последовательности увеличивается на 1, а каждый нечетный уменьшается на 2 относительно предыдущего, то с какого бы мы числа не начали, она уменьшится до определенного числа.
Я хотел сказать только то, что в случае этой последовательнсти, такого явного зигзага, который доказуемо уменьшается - нет.
Про память сложно спорить.
Но мне все равно неочевидно что у рядом стоящих чисел должны быть схожие цепочки. Раз уж мы делим на 2, я бы подумал про хранение таких цепочек в радиусе от чисел- 2ⁿ, условно сохранять цепочки из чисел 63,65, 1023,1025 и тд.
Но опять же, мне сложно отследить их связность без тестирования на больших данных, либо математического/логического вывода
Где n - количество шагов, которое можно прибавить к текущему и получить общее количетво шагов, чтоб прийти в единицу.
Можно хранить
Mapсо степенями двойки и их значениями, и использовать как доп.кэш. Действительно, элегантно.Ну даже в вашем примере 1002 и 1003 демонстрируют, насколько разными могут быть пути в 1.
+в паре рядом стоящих чисел всегда одно четное, а другое - нет, поэтому их дороги разойдутся сразу же(одно поделится на 2, второе умножится на 3). Мне не очевидно, что эти хвосты будут совпадать
Конкретно этот пароль было бы логично держать в файле dangerous_passwords.txt
Но вообще я не проводил ресерча по настоящим методам валидаций паролей, я понимаю, что там все сложнее, чем : 8 символов и спецзнак. Тут скорее я использовал стереотип, который был у меня в голове для примера. Я действительно брал эти условия с потолка. Прям совсем с потолка.
Не уверен, что до конца понял вашу идею. Можете привести пример цепочки/подцепочки и поиска?
ЯП не панацея от всех бед, статья скорее про способы оптимизации самого алгоритма.
Ответ на этот вопрос сложнее чем кажется, варьируется сильно от диапазона и стратегии хранения ключей в кэше.
В статье есть ссылка, про исследование кэша на оптимальность: https://habr.com/ru/articles/673224/
В случае с хэш-таблицей, у меня есть подозрение, что на больших числах кэш все равно будет переполняться и сильно тормозить. Нужна стратегия чистки памяти, в моем случае soft references помогли
Да, согласен. Смутило то, что отдельно друг от друга каждый отдельный миллиард считается достаточно быстро. Поправлю
А, или вы про передачу в сам метод только последней цифры?
В статье есть про это строчка: