Содержание:
- List.subList
- PriorityQueue
- EnumSet и EnumMap
- Set.add(E) и Set.remove(E) возвращают булево значение
- Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент
- Map.keySet() и Map.values()
- Arrays.asList может быть ключом
- Collections.max
- LinkedList, Stack, Vector, Hashtable
List.subList
Про это уже писали, но стоит повторить. Наверно, самый недооценённый метод из Collections API. Бывает, что надо каким-то образом обработать часть списка (например, в алгоритмах семейства «разделяй и властвуй» или при распараллеливании задачи). Многие создают метод или класс, который завязывается на три параметра: List, from и to:
void processListPart(List<Item> list, int from, int to) {
for(int idx = from; idx < to; idx++) {
Item item = list.get(idx);
...
}
}Так незачем делать. Реализации алгоритма должно быть плевать, что она обрабатывает часть списка. Пишите:
void processList(List<Item> list) {
for(Item item : list) {
...
}
}И вызывайте
processList(list.subList(from, to));Даже если у вас всё в одном методе, удобнее воспользоваться расширенным циклом for, чем возиться с индексами:
for(Item item : list.subList(from, to)) {...}Кроме того, subList — полнофункциональный список, он работает и на запись, внося соответствующие изменения в родительский список. Нужно удалить много элементов из середины списка? Ничего нет проще:
list.subList(from, to).clear();У популярных реализаций вроде ArrayList это выполняется очень быстро.
Надо выяснить, начинается ли список с определённых элементов? И тут subList в руки!
List<String> prefix = Arrays.asList("a", "prefix", "values");
if(myList.size() >= prefix.size() &&
myList.subList(0, prefix.size()).equals(prefix)) {...}Надо добавить в один список все элементы другого списка за исключением первого? И тут subList придёт на помощь:
list1.addAll(list2.subList(1, list2.size()));Не забывайте, что можно писать
Arrays.asList(array).subList(from, to), поэтому вышесказанное применимо и для непримитивных массивов. Структурно менять вы их не сможете, но передавать кусок массива в метод, принимающий список для чтения — легко.PriorityQueue
Если subList — самый недооценённый метод, то PriorityQueue — это, на мой взгляд, самый недооценённый класс. Многие сталкиваются с задачей отыскать, скажем, 10 минимальных значений большого несортированного списка. Чаще всего список сортируют и потом берут первые 10 значений. Если исходный список менять нельзя, придётся его ещё скопировать для сортировки. А ведь очередь с приоритетом легко справится с этой задачей:
public static <T extends Comparable<T>> List<T> leastN(Collection<T> input, int n) {
assert n > 0;
PriorityQueue<T> pq = new PriorityQueue<>(Collections.reverseOrder());
for (T t : input) {
if (pq.size() < n) {
pq.add(t);
} else if (pq.peek().compareTo(t) > 0) {
pq.poll();
pq.add(t);
}
}
List<T> list = new ArrayList<>(pq);
Collections.sort(list);
return list;
}Такой код в зависимости от данных может работать гораздо быстрее, чем сортировка. Например, для n = 10 и случайно заполненного списка из миллиона элементов очередь с приоритетом почти в сто раз обгоняет подход с сортировкой. При этом дополнительной памяти требуется O(n) и входные элементы можно обрабатывать в потоковом режиме (например, выбрать 10 наименьших чисел из входного файла).
Вообще людям свойственно изучить пару-тройку структур данных и пользоваться ими везде. Не ленитесь, познакомьтесь с разными структурами.
EnumSet и EnumMap
До сих пор встречается код, где значения типа enum используют в качестве ключей в HashSet и HashMap. Хотя это работает, но оно неоправданно расточительно. Существующие специальные классы EnumSet и EnumMap значительно производительнее. Так если в enum не больше 64 разных значений, EnumSet хранит всё в одном поле типа long в битовой маске. EnumMap содержит все значения в обычном массиве той же длины, сколько элементов в enum, а ключи не хранит вовсе. Так как у каждого значения в enum есть порядковый номер ordinal(), можно легко перейти от enum-ключа к элементу массива. Также никогда не нужно менять размер массива.
Set.add(E) и Set.remove(E) возвращают булево значение
Часто вижу подобный код:
if(!set.contains(item)) {
set.add(item);
// do something
} else {
// do something else
}Не надо забывать, что операция добавления в Set возвращает true, если добавление успешно (то есть элемента не было) и false, если такой элемент уже был. Незачем усложнять код и два раза пробивать элемент по хэш-таблице или двоичному дереву, ведь можно написать:
if(set.add(item)) {
// do something
} else {
// do something else
}Аналогично с удалением. Цепочка
if(set.contains(item)) { set.remove(item); ... } заменяется на if(set.remove(item)) { ... }.Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент
Из той же оперы ситуация. Методы, изменяющие или удаляющие элемент в коллекции возвращают предыдущее значение, и этим надо пользоваться. Не надо писать, например, так:
Item item = myMap.get(key);
myMap.put(key, newItem);Написать просто
Item item = myMap.put(key, newItem);. Хотите поменять местами две записи в Map с ключами key1, key2? Временная переменная не нужна:myMap.put(key1, myMap.put(key2, myMap.get(key1)));Map.keySet() и Map.values()
Многие почему-то забывают, что
Map.keySet() и Map.values() возвращают отображения исходного Map, которые позволяют удалять элементы (если Map модифицируемый). Надо оставить в Map только записи с определёнными значениями (и любыми ключами)? Пожалуйста:myMap.values().retainAll(toRetain);Также работает
removeAll, а с Java-8 ещё и removeIf:// Сгруппируем сотрудников по названиям подразделений
Map<String, List<Employee>> perDepartment = employees.stream().collect(groupingBy(Employee::getDepartmentName, HashMap::new, toList()));
// Оставим только крупные подразделения с числом сотрудников от 10
perDepartment.values().removeIf(list -> list.size() < 10);Arrays.asList может быть ключом
Бывает, что вам нужно сформировать Map или Set, используя кортеж значений. Например, у вас есть PoJo-объекты
Item, у которых имеются поля name, type, version. У них уже написан equals и hashCode, их можно складывать в HashSet, всё нормально. Но вы хотите выбрать из коллекции уникальные объекты только по полям name и type, игнорируя version. Менять существующие equals и hashCode нельзя. В таких ситуациях люди часто создают отдельный класс только с полями name и type и используют его в качестве ключа. Однако для одноразовой операции проще использовать Arrays.asList():Map<List<Object>, Item> map = new HashMap<>();
for(Item item : items) {
map.put(Arrays.asList(item.name, item.type), item);
}
Collection<Item> unique = map.values();Arrays.asList() создаёт список из нужного числа элементов и у него как раз подходящие реализации equals и hashCode: никакой boilerplate не нужен. Так можно создать ключ любой длины, причём корректно обработаются null-значения и примитивы (брагодаря боксингу). Не сработает только, если вы хотите в составе ключа иметь массив.Collections.min/max
Удивительно, насколько часто можно встретить написанный вручную код, который находит максимальный или минимальный элемент чего-то по какому-нибудь критерию. Казалось бы, такая тривиальная задача должна быть давно решена. На самом деле она и так давно решена: есть методы
Collections.min и Collections.max. Раньше было не очень удобно писать компараторы, но в Java-8 всё стало легче.К примеру, вам нужно найти ключ в Map, соответствующий максимальному значению. Пишите так:
maxKey = Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();Можно и через Stream API, но
Collections.max() несколько быстрее. Если вы не можете использовать Java-8 и компараторы вроде Entry.comparingByValue() вам недоступны, их нетрудно написать.Stack, Vector, Hashtable, LinkedList
Просто не используйте эти классы. Пользы от них никакой нет. Вместо Stack пользуйтесь ArrayDeque, вместо Vector — ArrayList, вместо Hashtable — HashMap. Если вам нужна потокобезопасность, они вам всё равно не помогут. Возможно, в девятке их всё-таки пометят @Deprecated (смотрите JEP 277).
С LinkedList случай особый. Вроде бы лучшего аналога связного списка нет и ходят легенды, что он на самом деле полезен. В действительности ситуаций, когда LinkedList лучше, чем ArrayList, в реальной жизни исключительно мало. До Java-8 LinkedList ещё мог пригодиться, если вы часто удаляете элементы, идущие не последовательно, по какому-то условию. В Java-8 для этих целей появился
List.removeIf, который в ArrayList, конечно, реализован оптимальнее (элементы передвигаются только один раз). Если вам надо сделать много вставок в разные места (задача сама по себе экзотическая), скорее всего быстрее будет создать новый ArrayList, чем вставлять в существующий LinkedList. Ну и помните, что LinkedList кушает в несколько раз больше памяти, так как каждый элемент — это отдельный объект в куче со ссылками на следующий и предыдущий. LinkedList можно использовать только в качестве учебного примера.На сегодня всё. Программируйте с удовольствием!
Комментарии (37)
leventov
17.12.2015 21:08+1Добавлю:
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) -> ...)
lany
18.12.2015 04:48Спасибо за дополнение. Кстати, неправда ваша :-) Вот описание 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-значение — это отсутствие значения.leventov
18.12.2015 04:53В чем неправда? Нуллы — плохо, да, я их упомянул лишь как фактор, который вносит дополнительное замешательство.
lany
18.12.2015 05:36Неправда в том, что putIfAbsent не различает ситуации «значение null» и «значение отсутствует». Может, конечно, я не так понял :-)
poxu
18.12.2015 16:58If 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
18.12.2015 23:58Если отбросить всякие нуллы, putIfAbent все равно в 2 операции только делается, до Java 8, и если это не ConcurrentMap
naething
18.12.2015 07:40Пример с PriorityQueue проще заменить на Ordering.leastOf() из Guava.
lany
18.12.2015 08:18Да, в сторонних библиотеках много всего нужного. Я лично бы заменил на MoreCollectors.least() из моей библиотеки :-) Он и распараллеливается нормально :-)
burjui
18.12.2015 16:30Для аргументов лучше использовать минимальный интерфейс последовательностей — 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>.
vedenin1980
18.12.2015 16:57+3Iterable
ИМХО, использование Iterable хуже чем Collection (если вам реально не нужно Iterable), так как:
1. Вы не сможете получить size, соответственно как только вам потребуется создать массив, ArrayList и т.п. у вас будут проблемы, придется или выделять память c запасом или терять производительность,
2. Вы не сможете работать с большим количеством полезных функций из Collections (guava несколько исправляет эту проблему, но тем не менее),
3. Вы не сможете легко и просто создать stream в Java 8,
В целом, я бы крайне осторожно использовал бы замену Collection на Iterable в больших функциях, чтобы не пришлось рефакторить пол приложения, когда потребуется Collection или не делать костыли и терять производительность.burjui
18.12.2015 17:58Процитирую сам себя:
если, конечно, не нужен какой-нибудь специфичный для класса коллекции метод
size() сюда же. Разумеется, Iterable не подходит для случаев, когда вы нужно знать точное количество элементов. Впрочем, это зависит от задачи.
Вы не сможете работать с большим количеством полезных функций из Collections (guava несколько исправляет эту проблему, но тем не менее)
Вы не сможете легко и просто создать stream в Java 8
Согласен. Впрочем, зато я легко смогу использовать totallylazy, которая функционально (нечаянный каламбур) гораздо богаче Stream из Java 8, частично заменяет Collections и доступна на Android (с Retrolambda идёт на ура).
В целом, я бы крайне осторожно использовал бы замену Collection на Iterable в больших функциях, чтобы не пришлось рефакторить пол приложения, когда потребуется Collection или не делать костыли и терять производительность.
Заменять и не надо. Просто пишите новые алгоритмы, исходя из принципа минимализма: нужна последовательность — принимай Iterable, понадобится менять последовательность — меняешь на Collection (не надо переписывать половину кода для этого).burjui
18.12.2015 18:08Во избежание недопонимания: я только предлагаю использовать Iterable для аргументов, когда не нужна возможность менять последовательность — но и тогда лучше принимать базовые типы вроде Collection и List. Я не призываю возвращать Iterable из функций, тем более что это не нужно, т.к. любая коллекция реализует этот интерфейс, и не вызванному методу решать, как возвращаемая коллекция будет использоваться дальше (если, конечно, речь не идёт о каком-либо API).
lany
18.12.2015 18:38Кстати, а что там такого актуального есть в totallylazy, чего в Stream API нету? Я заглянул что-то, думал идей натырить для моей либы, но сходу ничего интересного не нашёл.
burjui
18.12.2015 19:03К сожалению, документации по этой библиотеке кот наплакал, так что приходится копать исходники: 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);
Flammar
18.12.2015 23:18К сожалению, конструкторы коллекций, по соглашению, тоже принимают в качестве аргумента не
Iterable<T>, аCollection<T>.
Flammar
19.12.2015 00:41+1Мне кажется, программисты боятся использовать в качестве ключей возвращаемые из методов «хитрые» коллекции потому, что помнят, что у «нормальных» классов метод
equalsсначала проверяет одинаковость классов объектов. А с «производными» списками неодинаковость классов практически гарантирована.
sergey-b
23.12.2015 20:40-3ArrayList, хотя и тратит меньше памяти, чем LinkedList, но требует, чтобы память была выделена одним целым куском, а это более дорогой ресурс.
Если есть необходимость вставки в середину, то надо использовать LinkedList, и то, что эта задача названа экзотической, ничего не меняет.
grossws
23.12.2015 21:54+4Каждый 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 и модификация ещё двух соседних.burjui
24.12.2015 02:17Не считая дикого насилия над кэшем и отсутствия нормального prefetch при итерации по LL.
Это, пожалуй, самый важный момент. К тому же, если блок памяти целиком помещается в cache line, это полностью устраняет задержки на чтение RAM, поэтому экономить память и держать данные близко друг к другу очень важно для обеспечения максимальной производительности. Хотя JVM/Dalvik вряд ли дадут выжать из процессора все соки.
sergey-b
24.12.2015 02:41Да, зависит. А также зависит от соотношения количества операций вставки со всеми остальными операциями. Но вывод о том, что ArrayList или ArrayDeque всегда лучше LinkedList, все равно остается неверным. Именно с этим выводом, сделанным в статье, я не согласен. Нетрудно подобрать такие параметры коллекции и варианты использования, при которых LinkedList будет работать лучше.
Кстати, хорошая идея — реализовать LinkedList на массиве. Надо будет при случае попробовать.lany
24.12.2015 04:46Да, их подобрать и создать искусственный пример можно. Вопрос лишь в том, кому и когда в жизни пригодится этот искусственный пример. Напомню, что LinkedList больше, чем вдвое проигрывает по памяти ArrayList. Так что даже сделав полную копию с нужными вставками в нужные места, вы потратите меньше памяти.
grossws
24.12.2015 18:56Есть ещё забавный подход в scala.collection.immutable.Vector, строится на массивах по 32 элемента, эффективно поддерживает добавление элементов слева и справа, менее эффективно — вставку. Если элементов мало — хранит их в массиве, когда становится много — в trie таких массивов.
lany
25.12.2015 06:43+1В Java внутри есть подобная штука — SpinedBuffer. Только она для внутреннего использования в Stream API, наружу не выставлена.
Fen1kz
Отличная статья, спасибо!
Однако, я бы не стал делать
Ибо слышал что влиять на данные в проверках не есть хорошо.
lany
Рациональное зерно есть, конечно. Поклонники функционального программирования скажут, что почти любой вызов метода не должен давать побочных эффектов :-) Но та же стандартная библиотека Java (во всяком случае до JDK 7) вполне поощряет
if(file.delete())илиif(folder.mkdirs()). Тут побочный эффект явно есть. И даже какой-нибудьif(matcher.find())меняет состояние объекта — заполняет группы.Googolplex
Справедливости ради,
file.delete()иfile.mkdirs()— это части устаревшего API. В NIO.2 ничего подобного, к счастью, нет.terryP
На самом деле, вопрос даже не в том что изменение объекта в проверке спорная практика, а том что разработчики на Java не привыкли к трюкам вида «if(set.add(item))» или «put(...put( ))», поэтому если писать код, который будешь читать только ты — такое допустимо, а вот если ещё куча народа, то я лучше «if(!set.contains(item))… » напишу, чтобы не обяснять всем и каждому на код ревью, что я хотел тут сделать.
dougrinch
А чем плох вариант
Ничего (почти) лишнего. И объяснять никому ничего не надо.
p.s. И даже изменения в проверке нет.
lany
Насчёт того, к чему привыкли разработчики, можно много говорить. Определённо, например, Java-разработчики не привыкли к лямбдам и Stream API, потому что они появились не так давно. Но это не повод их не использовать. Если в команде люди чего-то не знают, на мой взгляд лучше им объяснить, чем руководствоваться принципом «не буду использовать крутые штуки, а то ещё коллеги будут плеваться». Я всегда пишу как считаю нужным, не оглядываясь на уровень знаний коллег.
Конечно,
put(...put( ))— довольно экстремальный пример, поэтому его стоит вынести в метод типаswapValues(map, key1, key2), тогда всё станет гораздо понятнее.