Комментарии 32
Так, а что не так с свежей java?
Если мы пишем на kotlin и запускаем на последнем релизе — мы молодцы и можно не переживать?
Все боятся несовместимостей в языке, основной фишкой которого является обратная совместимость
У многих другое: работает — не трогай. Немногие хотят получить потенциально неприятные и сложноуловимые проблемы в обмен на сомнительные фичи/фиксы. Поэтому тянут, пока последние не перевесят.
Как видим, проблемы нашлись где не ожидали.
Энтерпрайз он такой, да.
У Kotlin своих коллекций нет, используются стандартные. Но если очень хочется, то можно так
fun <T> MutableSet<T>.fastRemoveAll(collection: Collection<T>): Boolean {
var modified = false
for (element in collection) {
modified = modified or remove(element)
}
return modified
}Или в просто Java использовать решение
source.removeAll(new HashSet<>(removals));
Похоже, в JDK выбран довольно убогий способ справиться с задачей
Все мы любим покритиковать код, который был написан, когда мы ещё ходили под стол пешком. Но вопрос не в этом. Как правильно-то надо было сделать, расскажи нам :-)
По-хорошему, надо было не делать проверки size() > c.size(), оставив подобные оптимизации в зоне ответственности вызывающего кода.
Всё равно у removeAll нет никакой возможности определить, какая именно асимптотика скрывается за c.contains, а значит и оптимизация не имеет никакого смысла.
Теперь так поступить уже нельзя (существующий код может рассчитывать на эту оптимизацию), и придётся городить новые костыли эвристики. Например, можно добавить проверку что переданная коллекция является множеством, поскольку у множеств операция contains должна быть "быстрой". Но тут "в пролёте" окажутся мультимножества...
А какую ветку из исходного кода оставить, если убрать проверку?
Разумеется. ту где итерация идёт по внешней коллекции.
Почему?
Потому что это для неё известна асимптотика. Для другой ветки асимптотика неизвестна.
Ладно, но есть метод retainAll, который реализован через обход нашей коллекции. Причём его реализовать через обход переданной коллекции невозможно без использования O(N) дополнительной памяти. Выходит, у removeAll по твоему предложению будет contains-семантика текущей коллекции, а у retainAll будет contains-семантика переданной коллекции. Она может отличаться. Например, нам передан TreeSet с компаратором.
Далее, кто сказал, что известная асимптотика лучше? Например, моя задача требует передавать параметром Guava Multiset. Я знаю, что contains в нём очень быстрый. Мне может интуитивно кажется, что обойти его тоже быстро, даже если там элементы с огромным количеством повторов. По факту же обход будет включать в себя все повторы, и я также получу провал в производительности на ровном месте.
Ладно, но есть метод retainAll, который реализован через обход нашей коллекции. Причём его реализовать через обход переданной коллекции невозможно без использования O(N) дополнительной памяти.
Возможно, метода retainAll вообще не должно было быть.
Выходит, у removeAll по твоему предложению будет contains-семантика текущей коллекции, а у retainAll будет contains-семантика переданной коллекции.
Зато сейчас у removeAll вообще не определена семантика. Возможно, по-настоящему весёлые баги нас ещё ждут...
Далее, кто сказал, что известная асимптотика лучше?
Я исхожу из того, что стандартная библиотека должна работать предсказуемо.
Библиотека Guava могла бы и предоставить свою реализацию removeAll, принимающую MultiSet, в статическом хелпере.
Возможно, метода retainAll вообще не должно было быть.
Вот это зря, очень полезный метод. Понимаю желание убрать всё, что не вписывается в красивую картину мира, которую мы себе рисуем в голове, но надо не забывать про то что API должно быть практичным.
Зато сейчас у removeAll вообще не определена семантика
Это правда. Я лишь хотел показать, что вопрос "как правильно сделать" гораздо менее тривиальный, чем кажется, и мгновенное "разумеется" вовсе не так разумеется. Любое решение будет набором компромиссов.
Я исхожу из того, что стандартная библиотека должна работать предсказуемо.
Вариант всегда использовать contains целевой коллекции настолько же предсказуем. Ты вот делаешь неявное предположение, что у переданной коллекции iterator.next() быстрый, а это может быть и не так. К примеру, коллекция может быть фильтруемой на лету вьюшкой над большим сетом. Степень предсказуемости абсолютно одинаковая, она в любом случае зависит от устройства переданной коллекции, и с этим ничего не сделаешь.
Библиотека Guava могла бы и предоставить свою реализацию removeAll, принимающую MultiSet, в статическом хелпере.
Во-первых, это не нужно, потому что достаточно сделать mySet.removeAll(multiSet.toElementSet()) (подразумевая твою реализацию). Во-вторых, речь о неожиданных перформансных эффектах. Как ты обучишь каждого пользователя не использовать стандартный метод (или использовать его нестандартно) там, где он работает, выдаёт правильный результат и выполняется быстро на небольших тестовых данных? Либо ждать пока обожжётся (что мы, кстати, имеем в обсуждаемом примере), либо ожидать, что каждый пользователь прочитает и запомнит всю документацию от корки до корки (глупо), либо прокачивать статический анализ (вариант хороший, но ненадёжно).
Кстати, вот реализация retainAll в .NET — HashSet.cs#L496
Отличия от Java:
- Этот метод всегда использует компаратор текущей коллекции, а не переданной
- Этот метод делает проверку на совпадение типа коллекции и компаратора. Если совпали — идёт по оптимальному пути (использует чужой Contains). Если не совпали — использует O(N) дополнительной памяти.
Мне кажется, что-то более сложное "наворачивать" нет необходимости.
Увы, но контейнер не обязан находиться в стандартной библиотеке. Пользователь может подключить что-то ещё или даже свою реализацию написать.
* предварительный анализ — а выгодно ли вообще для N строить индекс. И влезет ли он в память, если возьмёмся строить.
Я не понял, а в чем ужас-то? Работа метода задокументирована. Метод AbstractSet.removeAll() ведет себя as expected. Никаких гарантий по сложности этого метода ни Set, ни AbstractSet, ни HashSet не дают. Нужно быстрее, пишешь свою реализацию. В чем проблема?
Работа метода задокументирована.
1) Чтобы это играло роль, надо документацию прочитать. Здесь изначально необходимость этого совершенно не видна.
2) Когда документация прочитана, почти единственным правильным решением во всех случаях будет не использовать метод с таким странным поведением.
Я с вами согласен и со статьей в принципе тоже. Я с оценкой, данной в заголовке, не могу согласиться. Я сам ни разу не использовал этот метод, хотя кое-где необходимость в нем возникала. Меня как раз не устраивала реализация.
Это, кстати, не единственный пример. Кажется, метод AbstractMap.merge() тоже сделан неэффективно, и в TreeMap он не переопределен.(Могу быть не прав. Если наврал, поправьте меня, пожалуйста).
Прекрасная статья, спасибо! Век живи — век учись )
stackoverflow.com/questions/28671903/the-hashsett-removeall-method-is-surprisingly-slow
Интересно в C# всё норм или тоже в определенных случаях может работать за O(N²)
Вот ссылка на реализацию: HashSet.cs#L532
Нет, в C# соответствующий метод просто в цикле вызывает Remove без всяких хитрых эвристик, а потому работает за O(N) (точнее, O(M), где M — количество удаляемых элементов).
Ужасы Set.removeAll