Комментарии 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))… » напишу, чтобы не обяснять всем и каждому на код ревью, что я хотел тут сделать.
А чем плох вариант
Ничего (почти) лишнего. И объяснять никому ничего не надо.
p.s. И даже изменения в проверке нет.
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) -> ...)
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:
От null-ключей и null-значений желательно отказаться вообще. Во-первых, их не поддерживают ConcurrentHashMap и ConcurrentSkipListMap. Сколько раз видел страдальцев, которые переделывали существующую HashMap на ConcurrentHashMap и обнаруживали, что всё стало падать из-за null'ов. Во-вторых, новые методы (семейство compute, merge) как раз предполагают, что 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-значений желательно отказаться вообще. Во-первых, их не поддерживают 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
Статья очень хорошая, спасибо!
.
Пример с PriorityQueue проще заменить на Ordering.leastOf() из Guava.
Да, в сторонних библиотеках много всего нужного. Я лично бы заменил на MoreCollectors.least() из моей библиотеки :-) Он и распараллеливается нормально :-)
Дубли в содержании
6. Arrays.asList может быть ключом
9. Arrays.asList может быть ключом
6. Arrays.asList может быть ключом
9. Arrays.asList может быть ключом
Для аргументов лучше использовать минимальный интерфейс последовательностей — Iterable<T>, если, конечно, не нужен какой-нибудь специфичный для класса коллекции метод:
Тогда можно будет передавать в processItems() не только List, но и Set и другие коллекции, а также, если вам не чужда функциональщина, ленивые последовательности вроде Sequence<T> из библиотеки totallylazy ( https://github.com/bodar/totallylazy/ ). Если нужно иметь возможность модифицировать коллекцию — принимайте Collection<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:
Просто сравните, какие методы есть у 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);
А, ну такое-то есть в Optional: и filter, и flatMap, и orElse.
НЛО прилетело и опубликовало эту надпись здесь
К сожалению, конструкторы коллекций, по соглашению, тоже принимают в качестве аргумента не
Iterable<T>, а Collection<T>.Мне кажется, программисты боятся использовать в качестве ключей возвращаемые из методов «хитрые» коллекции потому, что помнят, что у «нормальных» классов метод
equals сначала проверяет одинаковость классов объектов. А с «производными» списками неодинаковость классов практически гарантирована.
ArrayList, хотя и тратит меньше памяти, чем LinkedList, но требует, чтобы память была выделена одним целым куском, а это более дорогой ресурс.
Если есть необходимость вставки в середину, то надо использовать 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.
Стандартный размер 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 на массиве. Надо будет при случае попробовать.
Да, их подобрать и создать искусственный пример можно. Вопрос лишь в том, кому и когда в жизни пригодится этот искусственный пример. Напомню, что LinkedList больше, чем вдвое проигрывает по памяти ArrayList. Так что даже сделав полную копию с нужными вставками в нужные места, вы потратите меньше памяти.
Есть ещё забавный подход в scala.collection.immutable.Vector, строится на массивах по 32 элемента, эффективно поддерживает добавление элементов слева и справа, менее эффективно — вставку. Если элементов мало — хранит их в массиве, когда становится много — в trie таких массивов.
В Java внутри есть подобная штука — SpinedBuffer. Только она для внутреннего использования в Stream API, наружу не выставлена.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Коллекции в Java: о чём многие забывают