Pull to refresh

Comments 37

Отличная статья, спасибо!
Однако, я бы не стал делать
if(set.add(item)) { 

Ибо слышал что влиять на данные в проверках не есть хорошо.
Рациональное зерно есть, конечно. Поклонники функционального программирования скажут, что почти любой вызов метода не должен давать побочных эффектов :-) Но та же стандартная библиотека Java (во всяком случае до JDK 7) вполне поощряет if(file.delete()) или if(folder.mkdirs()). Тут побочный эффект явно есть. И даже какой-нибудь if(matcher.find()) меняет состояние объекта — заполняет группы.
Справедливости ради, file.delete() и file.mkdirs() — это части устаревшего API. В NIO.2 ничего подобного, к счастью, нет.
На самом деле, вопрос даже не в том что изменение объекта в проверке спорная практика, а том что разработчики на Java не привыкли к трюкам вида «if(set.add(item))» или «put(...put( ))», поэтому если писать код, который будешь читать только ты — такое допустимо, а вот если ещё куча народа, то я лучше «if(!set.contains(item))… » напишу, чтобы не обяснять всем и каждому на код ревью, что я хотел тут сделать.
А чем плох вариант
boolean wasAdded = set.add(item);
if (wasAdded) {

Ничего (почти) лишнего. И объяснять никому ничего не надо.

p.s. И даже изменения в проверке нет.
Насчёт того, к чему привыкли разработчики, можно много говорить. Определённо, например, Java-разработчики не привыкли к лямбдам и Stream API, потому что они появились не так давно. Но это не повод их не использовать. Если в команде люди чего-то не знают, на мой взгляд лучше им объяснить, чем руководствоваться принципом «не буду использовать крутые штуки, а то ещё коллеги будут плеваться». Я всегда пишу как считаю нужным, не оглядываясь на уровень знаний коллег.

Конечно, put(...put( )) — довольно экстремальный пример, поэтому его стоит вынести в метод типа swapValues(map, key1, key2), тогда всё станет гораздо понятнее.
Добавлю:

1. Часто идет код с двойными проверками в Map, например if (!map.containsKey(key)) { map.put(key, value) }. Похоже на случай с Set, но осложняется тем, что в Map есть дополнительная неоднозначность: null вернули, потому что записи не было, или потому что была запись со значением null? Новые методы, добавленные в Java 8 в интерфейс Map, полностью покрывают возможные ситуации (конкретно в примере выше — map.putIfAbsent()).

2. Иногда встречается итерация по Map:

for (K key: map.keySet()) {
doSmth(key, map.get(key));
}

Очень неэффективно, не говоря об итерации через entrySet(), в Java 8 лучше использовать map.forEach((k, v) -> ...)
Спасибо за дополнение. Кстати, неправда ваша :-) Вот описание putIfAbsent:
If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.

От null-ключей и null-значений желательно отказаться вообще. Во-первых, их не поддерживают ConcurrentHashMap и ConcurrentSkipListMap. Сколько раз видел страдальцев, которые переделывали существующую HashMap на ConcurrentHashMap и обнаруживали, что всё стало падать из-за null'ов. Во-вторых, новые методы (семейство compute, merge) как раз предполагают, что null-значение — это отсутствие значения.
В чем неправда? Нуллы — плохо, да, я их упомянул лишь как фактор, который вносит дополнительное замешательство.
Неправда в том, что putIfAbsent не различает ситуации «значение null» и «значение отсутствует». Может, конечно, я не так понял :-)
If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.

Перевод:
Если указанный ключ ещё не связан с каким либо значением (или значение — null), связывает его с заданным значением и возвращает null, в ином случае возвращает его текущее значение.
Да не, английский я-то понял :-) Я мысль leventov мог не понять. Плохо сформулировал.
Если отбросить всякие нуллы, putIfAbent все равно в 2 операции только делается, до Java 8, и если это не ConcurrentMap
Да, в сторонних библиотеках много всего нужного. Я лично бы заменил на MoreCollectors.least() из моей библиотеки :-) Он и распараллеливается нормально :-)
Дубли в содержании
6. Arrays.asList может быть ключом
9. Arrays.asList может быть ключом
Для аргументов лучше использовать минимальный интерфейс последовательностей — Iterable<T>, если, конечно, не нужен какой-нибудь специфичный для класса коллекции метод:

void processItems(final Iterable<Item> items) {
    for (final Item item : items) {
        ...
    }
}

Тогда можно будет передавать в processItems() не только List, но и Set и другие коллекции, а также, если вам не чужда функциональщина, ленивые последовательности вроде Sequence<T> из библиотеки totallylazy ( https://github.com/bodar/totallylazy/ ). Если нужно иметь возможность модифицировать коллекцию — принимайте Collection<T>.
Iterable


ИМХО, использование Iterable хуже чем Collection (если вам реально не нужно Iterable), так как:

1. Вы не сможете получить size, соответственно как только вам потребуется создать массив, ArrayList и т.п. у вас будут проблемы, придется или выделять память c запасом или терять производительность,

2. Вы не сможете работать с большим количеством полезных функций из Collections (guava несколько исправляет эту проблему, но тем не менее),

3. Вы не сможете легко и просто создать stream в Java 8,

В целом, я бы крайне осторожно использовал бы замену Collection на Iterable в больших функциях, чтобы не пришлось рефакторить пол приложения, когда потребуется Collection или не делать костыли и терять производительность.
Процитирую сам себя:
если, конечно, не нужен какой-нибудь специфичный для класса коллекции метод
size() сюда же. Разумеется, Iterable не подходит для случаев, когда вы нужно знать точное количество элементов. Впрочем, это зависит от задачи.

Вы не сможете работать с большим количеством полезных функций из Collections (guava несколько исправляет эту проблему, но тем не менее)
Вы не сможете легко и просто создать stream в Java 8
Согласен. Впрочем, зато я легко смогу использовать totallylazy, которая функционально (нечаянный каламбур) гораздо богаче Stream из Java 8, частично заменяет Collections и доступна на Android (с Retrolambda идёт на ура).

В целом, я бы крайне осторожно использовал бы замену Collection на Iterable в больших функциях, чтобы не пришлось рефакторить пол приложения, когда потребуется Collection или не делать костыли и терять производительность.
Заменять и не надо. Просто пишите новые алгоритмы, исходя из принципа минимализма: нужна последовательность — принимай Iterable, понадобится менять последовательность — меняешь на Collection (не надо переписывать половину кода для этого).
Во избежание недопонимания: я только предлагаю использовать Iterable для аргументов, когда не нужна возможность менять последовательность — но и тогда лучше принимать базовые типы вроде Collection и List. Я не призываю возвращать Iterable из функций, тем более что это не нужно, т.к. любая коллекция реализует этот интерфейс, и не вызванному методу решать, как возвращаемая коллекция будет использоваться дальше (если, конечно, речь не идёт о каком-либо API).
Кстати, а что там такого актуального есть в totallylazy, чего в Stream API нету? Я заглянул что-то, думал идей натырить для моей либы, но сходу ничего интересного не нашёл.
К сожалению, документации по этой библиотеке кот наплакал, так что приходится копать исходники: https://github.com/bodar/totallylazy/blob/master/src/com/googlecode/totallylazy/Sequence.java
Просто сравните, какие методы есть у Sequence, и какие — у Stream. Мне, например, недавно пригодились groupBy и zip. К тому же, totallylazy — библиотека для ФП, так что кроме Sequence, там есть Either и Option, которые тоже умеют map/flatMap, а также всякие монады с функторами, предикаты и их модификаторы, да куча всего. Почти все методы доступны для статического импорта. Пример из приложения для Android:

final int color = option(json.optString("some_color", null))
    .filter(not(String::empty))
    .flatMap(Color::parseColor)
    .getOrElse(Color.WHITE);
view.setBackgroundColor(color);
UFO landed and left these words here
К сожалению, конструкторы коллекций, по соглашению, тоже принимают в качестве аргумента не Iterable<T>, а Collection<T>.
Мне кажется, программисты боятся использовать в качестве ключей возвращаемые из методов «хитрые» коллекции потому, что помнят, что у «нормальных» классов метод equals сначала проверяет одинаковость классов объектов. А с «производными» списками неодинаковость классов практически гарантирована.
ArrayList, хотя и тратит меньше памяти, чем LinkedList, но требует, чтобы память была выделена одним целым куском, а это более дорогой ресурс.

Если есть необходимость вставки в середину, то надо использовать LinkedList, и то, что эта задача названа экзотической, ничего не меняет.
Каждый LinkedList.Node требует выделение 24 байт (при CompressedOops или 32-битной JVM), реальное выделение будет, скорее всего 32 байта или больше (в зависимости от конкретной JVM и её настроек), плюс 24 байта на сам LinkedList.

Стандартный размер ArrayList — 10 элементов — 20 на ArrayList и 16 + 10*4 на массив из 10 элементов при тех же условиях (на примере hotspot 64bit при Xmx менее 32G).

Т. е. LinkedList на 10 элементов займёт 352 байта, а ArrayList — 96 байт при выравнивании на 32 байта. Не считая дикого насилия над кэшем и отсутствия нормального prefetch при итерации по LL.

Если есть необходимость вставки в середину, то надо использовать LinkedList, и то, что эта задача названа экзотической, ничего не меняет.
Очень сильно зависит от условий. Часто копирование линейного куска памяти много дешевле, чем выделение нового LL.Node и модификация ещё двух соседних.
Не считая дикого насилия над кэшем и отсутствия нормального prefetch при итерации по LL.
Это, пожалуй, самый важный момент. К тому же, если блок памяти целиком помещается в cache line, это полностью устраняет задержки на чтение RAM, поэтому экономить память и держать данные близко друг к другу очень важно для обеспечения максимальной производительности. Хотя JVM/Dalvik вряд ли дадут выжать из процессора все соки.
Да, зависит. А также зависит от соотношения количества операций вставки со всеми остальными операциями. Но вывод о том, что ArrayList или ArrayDeque всегда лучше LinkedList, все равно остается неверным. Именно с этим выводом, сделанным в статье, я не согласен. Нетрудно подобрать такие параметры коллекции и варианты использования, при которых LinkedList будет работать лучше.

Кстати, хорошая идея — реализовать LinkedList на массиве. Надо будет при случае попробовать.
Да, их подобрать и создать искусственный пример можно. Вопрос лишь в том, кому и когда в жизни пригодится этот искусственный пример. Напомню, что LinkedList больше, чем вдвое проигрывает по памяти ArrayList. Так что даже сделав полную копию с нужными вставками в нужные места, вы потратите меньше памяти.
Есть ещё забавный подход в scala.collection.immutable.Vector, строится на массивах по 32 элемента, эффективно поддерживает добавление элементов слева и справа, менее эффективно — вставку. Если элементов мало — хранит их в массиве, когда становится много — в trie таких массивов.
В Java внутри есть подобная штука — SpinedBuffer. Только она для внутреннего использования в Stream API, наружу не выставлена.
Only those users with full accounts are able to leave comments. Log in, please.