Хм. У меня переполнение наступает позже, на числе 23,035,537,407 (за две минуты доходит до этого числа на джаве). Я оптимизировал следующим образом. Во-первых, уже отметили, что можно рассматривать только нечётные числа. Соответственно будем перебирать не x из исходной постановки задачи, а y = (x-1)/2. То есть x = 2y+1, и тогда следующее число за ним — 3x+1 = 6y+4. Очевидно, оно чётное, сразу делим пополам (3y+2). Далее его делим на два пока делится (то есть обрезаем правые нулевые биты), а потом вычитаем единицу и ещё раз делим на два, чтобы получить новый y (то есть обрезаем ещё один единичный бит). По сути надо сдвинуть результат вправо на numberOfTrailingZeros+1. NumberOfTrailingZeros — это инструкция TZCNT, быстро работает. С помощью этих оптимизаций мы также отыгрываем один битик от числа, то есть можем работать с 65-битным промежуточным результатом.
Код на Java
public class Collatz {
public static void main(String[] args) {
long limit = Long.divideUnsigned(-1L, 3) - 2;
for (long num = 1; ; num++) {
for (long next = update(num); next >= num; next = update(next)) {
if (next == num || next > limit) {
System.out.println((next == num ? "Found: " : "Overflow at: ") + (num * 2 + 1));
return;
}
}
}
}
private static long update(long value) {
value = value * 3 + 2;
return value >>> (Long.numberOfTrailingZeros(value) + 1);
}
}
В Java нет типа unsigned long, но это никому не мешает. Сложение и умножение для signed и unsigned работает одинаково, есть операция беззнакового битового сдвига >>>, а для деления есть специальный метод divideUnsigned.
Как правило, полное доказательство таких гипотез даёт попутный субпродукт — новую разработанную методологию решения математических задач. Она позволит атаковать другие проблемы, которые вполне могут иметь практическую ценность, даже если от самой изначальной гипотезы пользу нет. В математике никогда заранее точно не знаешь, где появится полезное знание, но практика показывает, что это происходит весьма часто. Поэтому надо продолжать копать.
Ну вот как раз подобный кейс со скоррелированным состоянием в том же методе, который разбирается на пятом месте (смотри мой комментарий ниже). Почему-то в хит-парад попал не он, а ложное срабатывание =)
9.2 репортить было бы хорошо, но это тоже unsound warning (а вдруг снаружи метода всегда проверяется, что x != index_64.length?). У меня была черновая реализация, но возникают помимо хороших варнингов реально очень мутные false-positive, где голову сломаешь перед тем как докажешь, что анализатор неправ. Я поэтому убрал этот код. Возможно, стоит вернуться.
3 должен репортиться инспекцией Integer multiplication or shift implicitly cast to long, но почему-то не срабатывает. Проверю, починю, спасибо!
2 — это интересная штука, у нас прямого аналога нет. Кое-какие циклы инициализации репортятся косвенно, но прямо такой нету.
1 — варнинг крутой, но как я понял инспекция у вас эвристическая. Возникает вопрос, сколько мусора она репортит. Вообще преаллоцированные массивы в toArray() в наши дни — антипаттерн. У нас на это есть инспекция, которая подсвечивает верхний по дефолту, но как раз молчит в нижнем, потому что вдруг пользователь реально хотел массив другой длины (чтобы были null'ы в хвосте).
final int roundCarryMask = (1 << (bitShiftsInWord - 1)); // <=
Это тоже вообще не ошибка. Я потому не делаю подобные unsound-варнинги, потому что в них сбалансировать false-positive/false-negative очень сложно. Здесь откровенно мусорный варнинг, который только отвлечёт программистов от реальных проблем. Видите выше noRestore = bitShiftsInWord == 0? А ниже посмотрите на использования noRestore. Вы сразу увидите, что когда bitShiftsInWord == 0, результат битового сдвига (переменная roundCarryMask) не используется вообще. Поэтому абсолютно наплевать, какое там значение.
Почему-то вы, кстати, молчите про другую вещь в том же методе:
Здесь очевидно noRestore всегда ложно, потому что случай wordShifts == 0 && bitShiftsInWord == 0 был обработан выше. Идея радостно подсвечивает эти ветки и предлагает автоматически упростить код в один клик. PVS-Studio не может так? ;-)
Я ж вам про это говорил вроде. Это вообще не ошибка, просто перестраховка. Вы смотрите хоть немного логику метода. Да, если на входе строка "0", она отсекается двумя разными способами, в обоих случаях return false; произойдёт, поэтому без разницы, в какую ветку мы зайдём. Может сбить с толку, если не вчитаться в код, но ошибки здесь нет. Сама Идея этот код подсвечивает ещё с 2017-го года (и не заводите волынку, что раз мы его не исправили, то нищитово).
С ArrayList у тебя стандартная проблема бенчмарк-энтузиаста, кстати. Ты увидел кейс, который в твоей практике случается часто, заточил библиотеку под этот кейс и написал бенчмарк тоже под этот кейс. Почему не потестировать другие кейсы? Если туда HashSet прилетает, сколько съедает лишняя проверка? А если разные реализации прилетают, например emptyList/singletonList/ArrayList/unmodifiableList в равной пропорции (вполне жизненная ситуация)? Насколько ускорится или замедлится каждый случай? Тело метода стало больше, влияет ли это на решения об инлайнинге?
Я не к тому, что твоя идея плоха. Она может и хороша. Я к тому, что надо критически смотреть на свои гениальные идеи.
Мораль сей басни такова: ваш гениальный патч могут зарезать на ревью просто потому, что не увидят в нём особой ценности. Ну да, есть повторяющийся код, но он никому особо не мешает, так что пусть живёт.
Дело не совсем в этом, тебе же сказали. Если делаешь метод в Arrays, нужны как минимум специализации для int/long/double, а желательно и для byte/boolean/short/char/float. В итоге имеем девять методов. И логично иметь версии с диапазоном поиска. Вот уже 18 методов. И ещё lastIndexOf — итого 36. Это уже серьёзная заявка. Люди надеются на светлое будущее и специализацию дженериков, когда можно будет обойтись четырьмя методами. Поэтому не хотят плодить новый код, связанный с речной специализацией. Только когда это будет — неясно.
Странно, что это называется assert. Это же precondition. Либо библиотека писалась для ассертов, но используется для прекондишнов. Технически разница может невелика, но семантика у ассерта и прекондишна разная.
Начнём с того, что ни у кого нет цели сделать из Джавы новый Котлин или Скалу. Какой смысл, если Котлин и Скала уже существуют? Джава — это отдельный язык со своей философией. У Котлина и Скалы другая философия. Это прекрасно, что у программистов есть выбор, какой философии следовать. Если сделать из Джавы второй Котлин, выбор пропадёт.
В Джаве есть одна хорошая вещь: в большинстве случаев локального контекста понятно, чтобы выяснить, что делает данная строчка кода. Скажем, если вы видите a[b] = c * d, вы знаете точно, что здесь у вас происходит запись произведения в элемент массива в куче, вне зависимости от того, что такое a, b, c и d, вне зависимости от того, какие у вас есть импорты и библиотеки, в каком классе вы выполняете этот код. Вы точно знаете, что в этой строчке у вас нет сетевого запроса или доступа к базе данных. В Котлине или Скале вы не уверены, эта строчка может делать абсолютно всё что угодно. Я считаю, что ясность — важная отличительная черта Джавы, и Джава перестанет быть Джавой, если потеряет ясность. Причём это усложнит не только чтение кода человеком, но и средства автоматического анализа кода. Некоторые вещи могут вообще перестать работать.
Зависит от проекта. В исходниках IntelliJ IDEA тоже многие тысячи instanceof. По сути дела многие инспекции — это поиск паттернов по дереву, паттерн-матчинг в чистом виде. Ну и в целом нет ничего плохого в instanceof, если правильно его использовать. Часто это существенно лучше, чем visitor pattern, который в джаве выглядит откровенно по-уродски, занимает больше места в исходниках и имеет больше накладных расходов при исполнении.
Хм. У меня переполнение наступает позже, на числе 23,035,537,407 (за две минуты доходит до этого числа на джаве). Я оптимизировал следующим образом. Во-первых, уже отметили, что можно рассматривать только нечётные числа. Соответственно будем перебирать не x из исходной постановки задачи, а y = (x-1)/2. То есть x = 2y+1, и тогда следующее число за ним — 3x+1 = 6y+4. Очевидно, оно чётное, сразу делим пополам (3y+2). Далее его делим на два пока делится (то есть обрезаем правые нулевые биты), а потом вычитаем единицу и ещё раз делим на два, чтобы получить новый y (то есть обрезаем ещё один единичный бит). По сути надо сдвинуть результат вправо на numberOfTrailingZeros+1. NumberOfTrailingZeros — это инструкция TZCNT, быстро работает. С помощью этих оптимизаций мы также отыгрываем один битик от числа, то есть можем работать с 65-битным промежуточным результатом.
В Java нет типа unsigned long, но это никому не мешает. Сложение и умножение для signed и unsigned работает одинаково, есть операция беззнакового битового сдвига
>>>, а для деления есть специальный метод divideUnsigned.Как правило, полное доказательство таких гипотез даёт попутный субпродукт — новую разработанную методологию решения математических задач. Она позволит атаковать другие проблемы, которые вполне могут иметь практическую ценность, даже если от самой изначальной гипотезы пользу нет. В математике никогда заранее точно не знаешь, где появится полезное знание, но практика показывает, что это происходит весьма часто. Поэтому надо продолжать копать.
Ну вот как раз подобный кейс со скоррелированным состоянием в том же методе, который разбирается на пятом месте (смотри мой комментарий ниже). Почему-то в хит-парад попал не он, а ложное срабатывание =)
del
В целом:
x != index_64.length?). У меня была черновая реализация, но возникают помимо хороших варнингов реально очень мутные false-positive, где голову сломаешь перед тем как докажешь, что анализатор неправ. Я поэтому убрал этот код. Возможно, стоит вернуться.toArray()в наши дни — антипаттерн. У нас на это есть инспекция, которая подсвечивает верхний по дефолту, но как раз молчит в нижнем, потому что вдруг пользователь реально хотел массив другой длины (чтобы были null'ы в хвосте).Это тоже вообще не ошибка. Я потому не делаю подобные unsound-варнинги, потому что в них сбалансировать false-positive/false-negative очень сложно. Здесь откровенно мусорный варнинг, который только отвлечёт программистов от реальных проблем. Видите выше
noRestore = bitShiftsInWord == 0? А ниже посмотрите на использованияnoRestore. Вы сразу увидите, что когдаbitShiftsInWord == 0, результат битового сдвига (переменнаяroundCarryMask) не используется вообще. Поэтому абсолютно наплевать, какое там значение.Почему-то вы, кстати, молчите про другую вещь в том же методе:
Здесь очевидно
noRestoreвсегда ложно, потому что случайwordShifts == 0 && bitShiftsInWord == 0был обработан выше. Идея радостно подсвечивает эти ветки и предлагает автоматически упростить код в один клик. PVS-Studio не может так? ;-)Я ж вам про это говорил вроде. Это вообще не ошибка, просто перестраховка. Вы смотрите хоть немного логику метода. Да, если на входе строка
"0", она отсекается двумя разными способами, в обоих случаяхreturn false;произойдёт, поэтому без разницы, в какую ветку мы зайдём. Может сбить с толку, если не вчитаться в код, но ошибки здесь нет. Сама Идея этот код подсвечивает ещё с 2017-го года (и не заводите волынку, что раз мы его не исправили, то нищитово).Выше написали же. В целом это абьюз фичи. Фичи следует использовать по назначению.
Вот ещё я по теме писал, но только про пул констант. Зато с красивой картинкой!
Не пользуйтесь этим ужасом. Забудьте как страшный сон.
С ArrayList у тебя стандартная проблема бенчмарк-энтузиаста, кстати. Ты увидел кейс, который в твоей практике случается часто, заточил библиотеку под этот кейс и написал бенчмарк тоже под этот кейс. Почему не потестировать другие кейсы? Если туда HashSet прилетает, сколько съедает лишняя проверка? А если разные реализации прилетают, например emptyList/singletonList/ArrayList/unmodifiableList в равной пропорции (вполне жизненная ситуация)? Насколько ускорится или замедлится каждый случай? Тело метода стало больше, влияет ли это на решения об инлайнинге?
Я не к тому, что твоя идея плоха. Она может и хороша. Я к тому, что надо критически смотреть на свои гениальные идеи.
Дело не совсем в этом, тебе же сказали. Если делаешь метод в Arrays, нужны как минимум специализации для int/long/double, а желательно и для byte/boolean/short/char/float. В итоге имеем девять методов. И логично иметь версии с диапазоном поиска. Вот уже 18 методов. И ещё lastIndexOf — итого 36. Это уже серьёзная заявка. Люди надеются на светлое будущее и специализацию дженериков, когда можно будет обойтись четырьмя методами. Поэтому не хотят плодить новый код, связанный с речной специализацией. Только когда это будет — неясно.
Почему? Вроде ровно посередине.
Странно, что это называется assert. Это же precondition. Либо библиотека писалась для ассертов, но используется для прекондишнов. Технически разница может невелика, но семантика у ассерта и прекондишна разная.
В плане скоупинга переменных паттерна работает аналогично. Про вывод типов никто ничего не говорил.
Но
boolean x = obj instanceof String str && !str.isEmpty();— уже вполне полезный код.Начнём с того, что ни у кого нет цели сделать из Джавы новый Котлин или Скалу. Какой смысл, если Котлин и Скала уже существуют? Джава — это отдельный язык со своей философией. У Котлина и Скалы другая философия. Это прекрасно, что у программистов есть выбор, какой философии следовать. Если сделать из Джавы второй Котлин, выбор пропадёт.
В Джаве есть одна хорошая вещь: в большинстве случаев локального контекста понятно, чтобы выяснить, что делает данная строчка кода. Скажем, если вы видите
a[b] = c * d, вы знаете точно, что здесь у вас происходит запись произведения в элемент массива в куче, вне зависимости от того, что такое a, b, c и d, вне зависимости от того, какие у вас есть импорты и библиотеки, в каком классе вы выполняете этот код. Вы точно знаете, что в этой строчке у вас нет сетевого запроса или доступа к базе данных. В Котлине или Скале вы не уверены, эта строчка может делать абсолютно всё что угодно. Я считаю, что ясность — важная отличительная черта Джавы, и Джава перестанет быть Джавой, если потеряет ясность. Причём это усложнит не только чтение кода человеком, но и средства автоматического анализа кода. Некоторые вещи могут вообще перестать работать.Зависит от проекта. В исходниках IntelliJ IDEA тоже многие тысячи instanceof. По сути дела многие инспекции — это поиск паттернов по дереву, паттерн-матчинг в чистом виде. Ну и в целом нет ничего плохого в instanceof, если правильно его использовать. Часто это существенно лучше, чем visitor pattern, который в джаве выглядит откровенно по-уродски, занимает больше места в исходниках и имеет больше накладных расходов при исполнении.
Про перекрытие полей спросил. А про
|| false— это в amber-dev можно спросить, там открытый мейлинг-лист.Нет, пока не обсуждается. Честно говоря, мне кажется, что это плохая фича для джавы.