Author Archives: elwood
Иногда бывает нужно решить такую задачу: есть массив, из которого мы по очереди выбираем рандомные элементы. И нужно сделать так, чтобы однажды выбранные элементы больше нам не попадались. Очевидное решение в лоб – завести рядом Set, в котором хранить либо сами выбранные элементы, либо их идентификаторы – совсем не годится: мало того, что придётся использовать дополнительную память, так ещё и нет гарантии, что следующий элемент получится найти сразу же. Чем больше мы будем выбирать элементов, тем дольше мы будем вынуждены искать следующий рандомный элемент, который еще отсутствует во множестве использованных. Другой способ – перекладывать использованные элементы в другую коллекцию – работоспособен только если исходная коллекция допускает операцию remove, и она реализована в ней эффективно. Поэтому для массивов не подходит (remove просто нет), да и для ArrayList’ов тоже не годится (remove неэффективен). Вот с LinkedList будет работать вполне себе неплохо. Смущает только невозможность восстановить исходное состояние коллекции после завершения работы алгоритма. Тогда уж проще скопировать исходную коллекцию целиком, и удалять из неё элементы. Но это не очень, если коллекция большая, а элементов нам нужно всего с десяток.
В общем, воспользуемся солдатской смекалкой и сделаем следующий алгоритм: каждый очередной выбираемый элемент мы меняем с последним элементом массива, и уменьшаем длину используемой части массива на единицу. В конце массива таким образом скапливаются “использованные” элементы. А чтобы сохранить возможность вернуться к исходному состоянию, рядом в ArrayList будем записывать оригинальные индексы использованных элементов.
Собственно, я написал класс, реализующий эту идею, и, находя его полезным, привожу код.
Пример использования:
Integer[] array = new Integer[100]; try (Picker<Integer> picker = new Picker<>(array)) { Integer randomItem = picker.pickRandom(); } |
Код класса:
Недавно я наткнулся на проблему с рендерингом console framework в стандартном эмуляторе терминала для KDE – Konsole. Проблема заключалась в том, что при перемещении окошек влево в терминале с шириной, равной или меньше ширины буфера экрана, справа от окна появлялись артефакты:
До этого я тестировал в других эмуляторах терминала (gnome-terminal, xterm, putty), и таких проблем не возникало никогда. После некоторых исследований стало ясно, что это бага в самом Konsole. Я был очень удивлён и не питал особых надежд на то, что такой баг можно легко воспроизвести, а тем более убедить мейнтейнеров проекта. Во всяком случае прикладывать к багрепорту аттач с программой на моно, которая внутри неочевидно (для мейнтейнеров) работает, имело бы мало смысла. Поэтому я решил попробовать сделать тестовую программу на чистом Си, минимального размера, но чтобы проблема была наглядно продемонстрирована. И это получилось ! Текст программы можно посмотреть в описании бага. Демонстрация проблемы была наглядна:
После этого я попросил в конференции гентоводов проверить, воспроизводится ли проблема у них. Пользователи Gentoo устанавливают одни из самых последних билдов программ, поэтому проверка у них – это важно. Оказалось, что баг действительно воспроизводится. Прошла неделя, я потихоньку уже сам стал разбираться в исходниках Konsole, научился собирать из исходников, логировать данные в момент обновления экрана, и вот сегодня – баг получил статус CONFIRMED, а значит, и некоторый шанс на то, что им кроме меня кто-то займётся.
Написал я тут обобщённый метод, который выглядит так:
private <T> T getParamValue(ProceedingJoinPoint joinPoint, String name) { if (! (joinPoint.getSignature() instanceof CodeSignature)) throw new RuntimeException( "JoinPoint is not a method." ); String[] parameterNames = (( CodeSignature ) joinPoint.getSignature()).getParameterNames(); int index = -1; for (int i = 0; i < parameterNames.length; i++) { if (parameterNames[i].equals( name )) { index = i; break; } } if (-1 == index) throw new RuntimeException( String.format( "Parameter '%s' not found.", name ) ); return ( T ) joinPoint.getArgs()[index]; } |
В принципе, тело метода мало чем интересно. Интересен оператор return, который выполняет приведение типа к T. Мне захотелось разобраться, как работает этот cast и почему эта конструкция работоспособна с любым типом T. Известно, что в java оператор приведения типа может привести к ClassCastException во время выполнения, однако с другой стороны мы знаем, что джавские дженерики компилируются таким образом, что в class-файлах информации о типах не остаётся, и компилятор не может добавить в код метода инструкцию приведения типа к типу T. Значит, скорее всего, приведение типа к типу-аргументу не порождает байткод, в отличие от обычного приведения к конкретному типу, известному на момент компиляции. Эту гипотезу легко проверить, берём декомпилятор, и – да, действительно, он декомпилирует последнюю строчку как
return joinPoint.getArgs()[index]; |
Как мы видим, компилятор сгенерировал метод, возвращающий Object, а для того, чтобы что-то превратить в Object, не нужно выполнять checkcast (байткод операции проверки приведения типа). Так и работают обобщения в Java. Компилятор превращает переменные типов T в переменные типа Object, и при присвоении
T var = someObject; |
компилятор генерирует код
Object var = someObject; |
А вот когда наоборот объект обобщённого типа мы присваиваем переменной конкретного типа, то компилятор добавляет байткод checkcast:
String str = this.<String>getParamValue(); |
превращается в
String str = (String) this.getParamValue(); // this.getParamValue() возвращает Object |
Так всё и работает. Поэтому в принципе не так уж и важно, правильно ли компилятор выведет тип при вызове getParamValue(). В любом случае будет вызов метода, возвращающего Object, и последующий каст к конкретному типу переменной (поля, аргумента функции).
Примитивные типы обрабатываются несколько особым образом. Допустим, мы вызываем наш метод и пытаемся присводить результат переменной-примитиву:
long id = getParamValue(); |
Кажется, что здесь может потребоваться явное указание типа T, так как long не может выступать в качестве типа-аргумента, однако компилятор достаточно умён и выполнит вывод ссылочного типа Long, соответствующего примитивному типу long, автоматически, и ещё добавит анбоксинг:
long id = ((Long) getParamValue()).longValue(); |
Осталось рассмотреть предупреждение компилятора “Unchecked cast: X to Y”, которое выдается при компиляции кода, преобразующего Object в обобщённый тип, либо в тип, зависящий от обобщённого типа:
List<String> list = (List<String>) map.get("list"); |
Теперь нам понятно, почему компилятор выдаёт это предупреждение. Инструкция checkcast добавляется в сгенерированный байткод, но она проверяет только то, что объект является списком List. Но то, что этот список был создан с типом-аргументом String, эта инструкция проверить не может. Аналогичное предупреждение мы получаем в строчке
return ( T ) joinPoint.getArgs()[index]; |
– и тут компилятор вообще ничем не может нам помочь, поскольку информация о T будет недоступна во время выполнения, переменная будет иметь тип Object, и мы не сможем быть уверены, что там хранится объект типа T, а не что-либо другое.
0