Алоха!
Вот и закончилась одна из самых хардкорных конференций в мире Java — Joker 2018, которая традиционно проходит в Санкт-Петербурге в «Экспофоруме». В этом году в конференции участвовало рекордное количество участников. «Одноклассники» традиционно предложили помочь нашим разработчикам решить нетривиальные задачи, которые возникают при создании одного из самых высоконагруженных проектов на Java.
Авторы заданий: ведущие разработчики из команды платформы, Андрей Паньгин и Вадим Цесько.
Те, кто хорошо ответил на вопросы, получили призы, а вам предлагаем краткий разбор наших задачек. Мы скрыли правильные ответы под спойлером, чур, открывать только после того, как сами додумались до решения ;-)
Поехали!
Дедупликатор
Кирилл хочет сэкономить память за счёт дедупликации объектов, равных по equals(). Помогите ему реализовать потокобезопасный метод dedup по аналогии со String.intern, но не только для строк.
public static Object dedup(Object obj) {
}
java.util.concurrent, вспомнил о замечательном методе computeIfAbsent. Этот метод выполнит переданную ему в параметре лямбду только при отсутствии ключа в Map, запишет её результат и вернет. Если такой ключ уже есть, лямбда вычисляться не будет, и вернется текущее ассоциированное с ключом значение. К тому же, вспомнил Кирилл, для ConcurrentHashMap этот метод работает атомарно, что позволяет очень элегантно решить задачу. Довольный Кирилл написал вот такой код:
private static final ConcurrentHashMap map = new ConcurrentHashMap();
public static Object dedup(Object obj) {
return map.computeIfAbsent(obj, o -> o);
}и с удовольствием почесал нос еще раз.
IP адрес
Дима разрабатывает новый сетевой протокол. Исправьте ошибку в его методе для перевода в строку IPv4-адреса, представленного в виде байтового массива.
String ipToString(byte[] ip) {
return ip[0] + '.' +
ip[1] + '.' +
ip[2] + '.' +
ip[3];
}'.', имеющий тип char, складывается с байтом как целочисленный тип. Заменив '.' на ".", Дима так обрадовался успешно скомпилированному коду, что сразу запустил его без тестирования. «Ай-ай-ай, Дима», подумала JVM и выдала вместо IP-адреса какую-то ерунду. В отличие от Димы, JVM точно знала, что в Java тип byte служит для хранения чисел со знаком, то есть все адреса, имеющие октеты больше 127, будут представлены в Java отрицательными числами. По правилам же приведения этих чисел в int, отрицательный знак числа такой же, как и в оригинальном байте. Эх, Дмитрий, надо же было принять дополнительные меры для того, чтобы отбросить знаковую часть, например так:
return (ip[0] & 255) + "." +
(ip[1] & 255) + "." +
(ip[2] & 255) + "." +
(ip[3] & 255);
Спискомешалка
Марине нужно перемешать элементы списка в случайном порядке. Почему не подойдёт такой вариант, и как бы вы его исправили?
Random random = ThreadLocalRandom.current();
list.sort((o1, o2) -> {
return random.nextBoolean() ? +1 : -1;
});Comparator требует стабильности: при сравнении двух одинаковых значений результат сравнения должен быть одинаков. А в реализации Марины результат для каждой пары строго случаен, что запросто может привести к исключению java.lang.IllegalArgumentException: Comparison method violates its general contract! Если бы Марина читала вечерами документацию, она бы знала, что в данном случае лучше всего воспользоваться методом Collections.shuffle().
Ответ: Нарушен контракт компаратора. Сортировка может выкинуть исключение. Лучше воспользоваться методом Collections.shuffle().
Вертеп функциональщика
Егор очень любит писать в функциональном стиле, не заботясь об эффективности кода. Оцените, сколько объектов создаёт каждый вызов данного метода, если в него передаётся ArrayList из 10 строк?
Predicate<String> equalsAny(List<String> list) {
Predicate<String> p = s -> false;
for (String s : list) {
p = p.or(s::contains);
}
return p;
}p = p.or(s::contains);
создаст сразу два объекта: один как результат вызова p.or(), а второй для создания предиката s::contains. Последний не может быть закэширован, так как захватывает в контекст переменную s. Умножив на количество итераций, получим 20 объектов. А ведь еще и скрытый Iterator может быть создан, если JIT его не оптимизирует. «20 или даже 21 объект, если не повезет, грешновато», подумала Алина.
Ответ: 10 предикатов or + 10 предикатов contains + 1 Iterator в зависимости от JIT-оптимизаций.
Максим включает на максимум
Максим вычисляет максимум в многопоточной программе, но хочет обойтись без блокировок. Помогите ему исправить ошибку.
AtomicLong max = new AtomicLong();
void addValue(long v) {
if (v > max.get()) {
max.set(v);
}
}AtomicLong ещё не делает программу потокобезопасной. Для этого есть атомарная операция AtomicLong.compareAndSwap. А начиная с Java 8 и вовсе не обязательно писать CAS-цикл самому, ведь появился замечательный атомарный метод accumulateAndGet. И тут удобно использовать как раз его:
void addValue(long v) {
max.accumulateAndGet(v, Math::max);
}
Автор: privatelv
