Хабрахабр

Разбор задачек Joker 2018

Алоха!

В этом году в конференции участвовало рекордное количество участников. Вот и закончилась одна из самых хардкорных конференций в мире 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];
}

Решение

Первую ошибку сразу же показала IDE, не дав Диме даже дописать метод до конца. Символ '.', имеющий тип 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);

Последний не может быть закэширован, так как захватывает в контекст переменную s. создаст сразу два объекта: один как результат вызова p.or(), а второй для создания предиката s::contains. А ведь еще и скрытый Iterator может быть создан, если JIT его не оптимизирует. Умножив на количество итераций, получим 20 объектов. «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);
}

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть