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

в 14:24, , рубрики: java, joker 2018, Блог компании Одноклассники, Занимательные задачки, Программирование

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

Алоха!

Вот и закончилась одна из самых хардкорных конференций в мире Java — Joker 2018, которая традиционно проходит в Санкт-Петербурге в «Экспофоруме». В этом году в конференции участвовало рекордное количество участников. «Одноклассники» традиционно предложили помочь нашим разработчикам решить нетривиальные задачи, которые возникают при создании одного из самых высоконагруженных проектов на Java.

Авторы заданий: ведущие разработчики из команды платформы, Андрей Паньгин и Вадим Цесько.

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

Те, кто хорошо ответил на вопросы, получили призы, а вам предлагаем краткий разбор наших задачек. Мы скрыли правильные ответы под спойлером, чур, открывать только после того, как сами додумались до решения ;-)

Поехали!

Дедупликатор

Кирилл хочет сэкономить память за счёт дедупликации объектов, равных по 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);

создаст сразу два объекта: один как результат вызова 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js