How to become an author
Search
Write a publication
Pull to refresh

Comments 32

Так, а что не так с свежей java?
Если мы пишем на kotlin и запускаем на последнем релизе — мы молодцы и можно не переживать?

Total votes 5: ↑2 and ↓3-1
Всё с ней так. Не так здесь с огромной инерцией пользователей. Все боятся несовместимостей в языке, основной фишкой которого является обратная совместимость. Парадоксально, но факт.
Total votes 4: ↑4 and ↓0+4
Все боятся несовместимостей в языке, основной фишкой которого является обратная совместимость

У многих другое: работает — не трогай. Немногие хотят получить потенциально неприятные и сложноуловимые проблемы в обмен на сомнительные фичи/фиксы. Поэтому тянут, пока последние не перевесят.
Total votes 2: ↑2 and ↓0+2

Как видим, проблемы нашлись где не ожидали.

Total votes 3: ↑1 and ↓2-1
Я про этап, когда уже все или почти все написано. А если так, то на эту проблему уже должны были найти решение или костыль. Если разработка только началась, то конечно имеет смысл брать более-менее свежую версию.
Total votes 2: ↑2 and ↓0+2
За это как раз стоит благодарить авторов библиотек, которые в погоне за странным пересекают границу, за которой заканчиваются гарантии совместимости языка (reflection, unsafe). И сами при этом не сильно заботятся о совместимости между своими версиями, что вносит здоровый пессимизм в вопрос обновления — вроде бы доверяем языку и не против обновиться, но не доверяем библиотекам и поэтому хороним идею.
Total votes 4: ↑4 and ↓0+4

Пока последний stable 13 — его и используем.

Total votes 1: ↑1 and ↓0+1

У 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));
Total votes 2: ↑2 and ↓0+2
Похоже, в JDK выбран довольно убогий способ справиться с задачей

Все мы любим покритиковать код, который был написан, когда мы ещё ходили под стол пешком. Но вопрос не в этом. Как правильно-то надо было сделать, расскажи нам :-)

Total votes 4: ↑4 and ↓0+4

По-хорошему, надо было не делать проверки size() > c.size(), оставив подобные оптимизации в зоне ответственности вызывающего кода.


Всё равно у removeAll нет никакой возможности определить, какая именно асимптотика скрывается за c.contains, а значит и оптимизация не имеет никакого смысла.


Теперь так поступить уже нельзя (существующий код может рассчитывать на эту оптимизацию), и придётся городить новые костыли эвристики. Например, можно добавить проверку что переданная коллекция является множеством, поскольку у множеств операция contains должна быть "быстрой". Но тут "в пролёте" окажутся мультимножества...

Total votes 2: ↑2 and ↓0+2

А какую ветку из исходного кода оставить, если убрать проверку?

Total votes 1: ↑1 and ↓0+1

Потому что это для неё известна асимптотика. Для другой ветки асимптотика неизвестна.

Total votes 2: ↑2 and ↓0+2

Ладно, но есть метод retainAll, который реализован через обход нашей коллекции. Причём его реализовать через обход переданной коллекции невозможно без использования O(N) дополнительной памяти. Выходит, у removeAll по твоему предложению будет contains-семантика текущей коллекции, а у retainAll будет contains-семантика переданной коллекции. Она может отличаться. Например, нам передан TreeSet с компаратором.


Далее, кто сказал, что известная асимптотика лучше? Например, моя задача требует передавать параметром Guava Multiset. Я знаю, что contains в нём очень быстрый. Мне может интуитивно кажется, что обойти его тоже быстро, даже если там элементы с огромным количеством повторов. По факту же обход будет включать в себя все повторы, и я также получу провал в производительности на ровном месте.

Total votes 1: ↑1 and ↓0+1
Ладно, но есть метод retainAll, который реализован через обход нашей коллекции. Причём его реализовать через обход переданной коллекции невозможно без использования O(N) дополнительной памяти.

Возможно, метода retainAll вообще не должно было быть.


Выходит, у removeAll по твоему предложению будет contains-семантика текущей коллекции, а у retainAll будет contains-семантика переданной коллекции.

Зато сейчас у removeAll вообще не определена семантика. Возможно, по-настоящему весёлые баги нас ещё ждут...


Далее, кто сказал, что известная асимптотика лучше?

Я исхожу из того, что стандартная библиотека должна работать предсказуемо.


Библиотека Guava могла бы и предоставить свою реализацию removeAll, принимающую MultiSet, в статическом хелпере.

Total votes 2: ↑2 and ↓0+2
Возможно, метода retainAll вообще не должно было быть.

Вот это зря, очень полезный метод. Понимаю желание убрать всё, что не вписывается в красивую картину мира, которую мы себе рисуем в голове, но надо не забывать про то что API должно быть практичным.


Зато сейчас у removeAll вообще не определена семантика

Это правда. Я лишь хотел показать, что вопрос "как правильно сделать" гораздо менее тривиальный, чем кажется, и мгновенное "разумеется" вовсе не так разумеется. Любое решение будет набором компромиссов.


Я исхожу из того, что стандартная библиотека должна работать предсказуемо.

Вариант всегда использовать contains целевой коллекции настолько же предсказуем. Ты вот делаешь неявное предположение, что у переданной коллекции iterator.next() быстрый, а это может быть и не так. К примеру, коллекция может быть фильтруемой на лету вьюшкой над большим сетом. Степень предсказуемости абсолютно одинаковая, она в любом случае зависит от устройства переданной коллекции, и с этим ничего не сделаешь.


Библиотека Guava могла бы и предоставить свою реализацию removeAll, принимающую MultiSet, в статическом хелпере.

Во-первых, это не нужно, потому что достаточно сделать mySet.removeAll(multiSet.toElementSet()) (подразумевая твою реализацию). Во-вторых, речь о неожиданных перформансных эффектах. Как ты обучишь каждого пользователя не использовать стандартный метод (или использовать его нестандартно) там, где он работает, выдаёт правильный результат и выполняется быстро на небольших тестовых данных? Либо ждать пока обожжётся (что мы, кстати, имеем в обсуждаемом примере), либо ожидать, что каждый пользователь прочитает и запомнит всю документацию от корки до корки (глупо), либо прокачивать статический анализ (вариант хороший, но ненадёжно).

Total votes 1: ↑1 and ↓0+1

Кстати, вот реализация retainAll в .NET — HashSet.cs#L496
Отличия от Java:


  1. Этот метод всегда использует компаратор текущей коллекции, а не переданной
  2. Этот метод делает проверку на совпадение типа коллекции и компаратора. Если совпали — идёт по оптимальному пути (использует чужой Contains). Если не совпали — использует O(N) дополнительной памяти.

Мне кажется, что-то более сложное "наворачивать" нет необходимости.

Total votes 2: ↑2 and ↓0+2

Мы, кстати, обсуждаем реализацию из AbstractSet, а не возможную специализацию в HashSet. Конечно, когда мы больше знаем хотя бы про свой Set, нам будет проще выделить fast-path.

Total votes 1: ↑1 and ↓0+1

Ну, AbstractSet в .NET просто нет, и, как мне кажется, как раз по причине подобных приколов с производительностью.

Total votes 2: ↑2 and ↓0+2
Почему это неизвестна? Реальный тип можно посмотреть, контейнеров в стандартной библиотеке ограниченное количество, для каждой пары (своя / чужая) можно выбрать нужную реализацию. Хоть if-ами. Выглядеть будет страшно (один раз при разработке и профилировании) работать быстро на миллионах машин.
Total votes 1: ↑1 and ↓0+1

Увы, но контейнер не обязан находиться в стандартной библиотеке. Пользователь может подключить что-то ещё или даже свою реализацию написать.

Total votes 2: ↑2 and ↓0+2
Вот эту бы проблему я JavaDoc-ом решал — честно проинформировал, о том, что будем проверять в переданной коллекции каждый элемент, случайным образом. Передал туда что-то с безумным временем поиска — сам себе злобный буратино. Был бы архитектором — предложил бы ещё один метод сделать, что-то типа removeAllIndexed, который бы после предварительного анализа* строил индекс над списком элементов для удаления. Хоть это и дополнительная память. Зато минус велосипедостроительство в каждом конкретном куске кода.
* предварительный анализ — а выгодно ли вообще для N строить индекс. И влезет ли он в память, если возьмёмся строить.
Total votes 2: ↑1 and ↓10

В итоге получаем нифига не расширяемую систему типов, где ничего нельзя делать.


Если уж так хочется всё усложнить — лучше завести отдельные маркерные интерфейсы "быстрый Itareble", "Collection с быстрым contains", и смотреть уже на них.

Total votes 2: ↑2 and ↓0+2

Я не понял, а в чем ужас-то? Работа метода задокументирована. Метод AbstractSet.removeAll() ведет себя as expected. Никаких гарантий по сложности этого метода ни Set, ни AbstractSet, ни HashSet не дают. Нужно быстрее, пишешь свою реализацию. В чем проблема?

Total votes 3: ↑2 and ↓1+1
Работа метода задокументирована.

1) Чтобы это играло роль, надо документацию прочитать. Здесь изначально необходимость этого совершенно не видна.


2) Когда документация прочитана, почти единственным правильным решением во всех случаях будет не использовать метод с таким странным поведением.

Total votes 3: ↑3 and ↓0+3

Я с вами согласен и со статьей в принципе тоже. Я с оценкой, данной в заголовке, не могу согласиться. Я сам ни разу не использовал этот метод, хотя кое-где необходимость в нем возникала. Меня как раз не устраивала реализация.
Это, кстати, не единственный пример. Кажется, метод AbstractMap.merge() тоже сделан неэффективно, и в TreeMap он не переопределен.(Могу быть не прав. Если наврал, поправьте меня, пожалуйста).

This comment wasn’t rated yet0

Прекрасная статья, спасибо! Век живи — век учись )

Total votes 1: ↑0 and ↓1-1

Вот ссылка на реализацию: HashSet.cs#L532


Нет, в C# соответствующий метод просто в цикле вызывает Remove без всяких хитрых эвристик, а потому работает за O(N) (точнее, O(M), где M — количество удаляемых элементов).

This comment wasn’t rated yet0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr