Lex Kravetski (lex_kravetski) wrote,
Lex Kravetski
lex_kravetski

Category:

Remove vs Filter

Эта статья — о нюансах программирования на Java. Никаких смыслов, выходящих за рамки программирования, в статье нет. Не обессудьте.

Но посвящена она вопросу, который многих программистов беспокоит.


Предложим, у нас есть ArrayList, заполненный некими объектами. Ставится задача: удалить из этого контейнера все объекты, для которых не выполняется условие P(e) (под P(e) подразумевается некоторая функция, принимающая на вход ссылку на элемент контейнера и возвращающая booean).

Концептуально способы решения этой задачи распадаются на две группы:

1. Мы можем проитерировать по контейнеру, проверяя условие и вызывая у итератора remove для тех элементов, для которых условие не выполнилось.
2. Мы можем создать новый контейнер, а потом проитерировать по старому, добавляя в новый те элементы, для которых условие выполнилось. После этого ссылке на старый контейнер присвоить ссылку на новый.

Обобщённо эти подходы можно назвать «подход remove» и «подход filter». Или «remove» и «filter» для краткости.

Возникает вопрос: какой из подходов лучше всего использовать?

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

Поначалу возникает ощущение, что filter должен работать гораздо медленнее, чем remove. Ведь в случае с фильтром будет создан новый ArrayList, который будет расширяться по мере заполнения. Мы в общем случае даже не можем создать ArrayList с подсказкой размера — неизвестно ведь, сколько элементов в конечном счёте войдёт в результирующий контейнер. То есть, массив внутри ArrayList будет пересоздан несколько раз. Из этого вытекает, что подход remove использовать вроде бы выгоднее.

Однако многочисленные эксперименты показали: в идеальном случае remove работает быстрее фильтра примерно на 25%, в худших же случаях он может быть медленнее в десятки, а временами — в сотни раз.

Идеальный случай — это когда удаляется один-два элемента. В этом случае remove слегка опережает filter. При пяти-семи удаляемых элементах remove и filter работают с одинаковой скоростью. Дальше remove начинает катастрофически отставать.

Отчего это происходит? Рассмотрим происходящее.

Метод filter создаёт ArrayList. Внутри ArrayList-а находится массив, который создаётся «с запасом». То есть, когда добавляется новый элемент в конец ArrayList-а, для которого уже нет свободной ячейки в массиве, создаётся новый массив, большего размера, куда копируется старый. Копируется он не поэлементно, а сразу блоком памяти, что гораздо быстрее.

Новый массив не просто на одну ячейку больше старого. Он больше в полтора раза плюс одна ячейка. То есть, в следующий раз он пересоздастся не при добавлении следующего элемента, а при добавлении половины от того, что в нём на данный момент есть.

Иными словами, если мы добавим в пустой ArrayList тысячу элементов, то массив внутри него будет пересоздан не тысячу, а семнадцать раз. Причём, первые разы копироваться будет весьма небольшой блок памяти — в единицы или десятки элементов массива.

Во время работы filter мы однократно пройдём по исходной коллекции и однократно для каждого элемента вызовем P(e). Ровно так же будет и в методе remove, поэтому итерирование само по себе можно не рассматривать.

Но во время remove копирование ровно так же происходит. Причём, если мы итерируем с первого элемента массива, и этот элемент сразу же оказывается подлежащим удалению, то скопированы будут все последующие элементы. К счастью, ArrayList при удалении элементов никогда не пересоздаёт массив — это несколько улучшает производительность (хотя и расходует память), но одного только копирования уже за глаза хватит. Причём, память будет скопирована столько раз, сколько элементов мы удалим.

В среднем копироваться будет память, соответствующая половине размерности массива, поскольку в среднем подлежащий удалению элемент будет в середине. Каждый удалённый элемент будет снижать размерность на единицу, то есть, если исходная коллекция достаточно длинная, на первом десятке удаляемых элементов мы в среднем десять раз скопируем половину исходной коллекции. И даже если вдруг окажется, что удалению подлежат все элементы, всё равно память будет копироваться и копироваться, пока внутри ArrayList не останется абсолютно пустой массив.

При росте же новой коллекции в реализации метода filter, как было сказано выше, память будет копироваться не на каждой итерации и совершенно не в тех объёмах.

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

В случае filter:

0.        Создаётся новый ArrayList
1.        Создаётся массив внутри ArrayList, длинной в одну ячейку.
2.        Размер массива возрастает до двух. Первый массив (длиной в одну ячейку) копируется во второй.
3.        Размер возрастает до четырёх. Копируется массив из двух ячеек.
4.        Размера массива хватает. Копирования не происходит.
5.        Размер возрастает до семи. Копируются четыре ячейки.
6.        Нет копирования.
7.        Нет копирования.
8.        Размер возрастает до одиннадцати.
9.        Нет копирования.
10.        …
11.        …

17. Размер вырастает до семнадцати. Копируется одиннадцать ячеек.

Дальше будет рост размера массива, сопровождаемый копированием, при 26-и элементах, 40-а, 61-м и 92-х. Всего будет скопировано 169 ячеек массива.

Теперь рассмотрим remove.

1.        Удаляется 45-й элемент. Копируются 54 ячейки.
2.        Удаляется 46-й. Копируются 53 ячейки.
3.        …
4.        …

10.        Удаляется 54-й элемент. Копируются 45 ячеек.

Итого было скопировано 495 ячеек. А если бы нам не повезло, и удаляемые элементы стояли бы первыми, то скопировалось бы 855 ячеек. Против гарантированных 169 в случае с filter — в нём количество копирований от расположения элементов в исходной коллекции не зависит.

Конечно, создание массива в памяти тоже требует некоторых расходов, но отсутствие этих созданий не может компенсировать разницу в десятках тысяч копируемых ячеек. Тем более, копирование 100 ячеек десять раз и 1000 один раз — не одно и то же. Второе, конечно, быстрее.

В результате оказывается, что если нет чёткой уверенности в исчезающее малом количестве удаляемых элементов, гораздо более предпочтительно использовать именно filter. Remove при неблагоприятном раскладе может радикально снизить быстродействие. Причём, тем больше снизить, чем больше элементов нужно удалить. Например, при удалении пятисот элементов из тысячи remove оказывается медленнее filter примерно в шесть раз.

Если вместо ArrayList воспользоваться LinkedList, то результаты remove будут стабильно лучше, чем у filter. Примерно на 30%, причём это соотношение не так сильно зависит от количества удаляемых элементов, как в случае с ArrayList-ом.

Однако LinkedList имеет другой побочный эффект: он менее эффективен, чем ArrayList, при заполнении добавлением элементов в конец списка. Даже если не передавать в конструктор ArrayList подсказку о размере, всё равно LinkedList оказывается медленнее. Таким образом, его имеет смысл использовать только в тех случаях, когда элементы добавляются в начало или середину коллекции. В иных же случаях (которые, кстати, в основном и случаются) предпочтительнее ArrayList и, соответственно, filter как подход для удаления элементов.

Использовать remove имеет смысл только в двух случаях: когда гарантированно удаляются не более чем один-два элемента или когда по какой-то причине необходимо сохранять неизменную ссылку на коллекцию.

Наконец, следует отметить, что наихудший метод решения поставленной задачи: сначала найти те объекты, которые следует удалить, а потом вызвать у исходной коллекции removeAll с ними в качестве параметра.

Дело в том, что removeAll реализован чудовищно неэффективно. Сколько бы ему ни передали элементов для удаления и в каком бы контейнере они ни содержались, он всё равно будет вызывать у этого контейнера contains, что в случае с наследниками List-а означает линейный обход контейнера. То есть, при удалении 500 элементов контейнер с элементами для удаления будет обойдён 500 раз (в среднем до половины). И каждый раз, вдобавок, для сравнения элементов будет вызван equals.

Скажем, при удалении 500 элементов из 10000 реализация при помощи removeAll будет работать в тринадцать раз медленнее, чем реализация методом remove, и в шестьдесят раз медленнее, чем методом filter.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 68 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →