Подтвердить что ты не робот

Почему функция удаления Java ArrayList, кажется, стоит так мало?

У меня есть функция, которая управляет очень большим списком, превышающим около 250 000 элементов. Для большинства этих элементов он просто заменяет элемент в позиции x. Однако около 5% из них должны удалить их из списка.

Использование LinkedList, казалось, было наиболее очевидным решением, чтобы избежать дорогостоящих изъятий. Однако, естественно, доступ к LinkedList по индексу становится все медленнее с течением времени. Стоимость здесь - минуты (и многие из них).

Использование Iterator над этим LinkedList также дорого, поскольку мне кажется, что требуется отдельная копия, чтобы избежать проблем с Iterator concurrency при редактировании этого списка. Стоимость здесь минут.

Однако здесь, где мой ум немного взорван. Если я перехожу в ArrayList, он запускается почти мгновенно.

Для списка с 297515 элементами удаление 11958 элементов и изменение всего остального занимает 909 мс. Я подтвердил, что получившийся список действительно имеет размер 285557, как и ожидалось, и содержит обновленную информацию, которая мне нужна.

Почему это так быстро? Я посмотрел на источник для ArrayList в JDK6, и он, похоже, использует функцию arraycopy, как ожидалось. Я хотел бы понять, почему ArrayList работает так хорошо, когда здравый смысл, похоже, указывает на то, что массив для этой задачи - ужасная идея, требующая смещения нескольких сотен тысяч элементов.

4b9b3361

ОТВЕТЫ

Ответ 1

Я проверил контрольный показатель, пробовав каждую из следующих стратегий фильтрации элементов списка:

  • Скопируйте нужные элементы в новый список
  • Используйте Iterator.remove() для удаления нежелательных элементов из ArrayList
  • Используйте Iterator.remove() для удаления нежелательных элементов из LinkedList
  • Компактный список на месте (перемещение желаемых элементов в нижние позиции)
  • Удалить по индексу (List.remove(int)) на ArrayList
  • Удалить по индексу (List.remove(int)) на LinkedList

Каждый раз, когда я заполнял список 100000 случайными экземплярами Point и использовал условие фильтра (на основе хэш-кода), которое принимало бы 95% элементов и отклоняло оставшиеся 5% (та же доля, указанная в вопросе, но с меньшим списком, потому что у меня не было времени на запуск теста на 250000 элементов.)

И среднее время (на моем старом MacBook Pro: Core 2 Duo, 2,2 ГГц, 3Gb RAM):

CopyIntoNewListWithIterator   :      4.24ms
CopyIntoNewListWithoutIterator:      3.57ms
FilterLinkedListInPlace       :      4.21ms
RandomRemoveByIndex           :    312.50ms
SequentialRemoveByIndex       :  33632.28ms
ShiftDown                     :      3.75ms

Таким образом, удаление элементов по индексу из LinkedList было более чем в 300 раз дороже, чем удаление их из ArrayList, и, вероятно, где-то между 6000-10000 раз дороже других методов (которые избегают линейного поиска и arraycopy)

Здесь нет большой разницы между четырьмя более быстрыми методами, но я снова побежал с этими четырьмя с 500000-элементным списком со следующими результатами:

CopyIntoNewListWithIterator   :     92.49ms
CopyIntoNewListWithoutIterator:     71.77ms
FilterLinkedListInPlace       :     15.73ms
ShiftDown                     :     11.86ms

Я предполагаю, что с большим объемом кеш-памяти становится ограничивающим фактором, поэтому стоимость создания второй копии списка становится значительной.

Здесь код:

import java.awt.Point;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

public class ListBenchmark {

    public static void main(String[] args) {
        Random rnd = new SecureRandom();
        Map<String, Long> timings = new TreeMap<String, Long>();
        for (int outerPass = 0; outerPass < 10; ++ outerPass) {
            List<FilterStrategy> strategies =
                Arrays.asList(new CopyIntoNewListWithIterator(),
                              new CopyIntoNewListWithoutIterator(),
                              new FilterLinkedListInPlace(),
                              new RandomRemoveByIndex(),
                              new SequentialRemoveByIndex(),
                              new ShiftDown());
            for (FilterStrategy strategy: strategies) {
                String strategyName = strategy.getClass().getSimpleName();
                for (int innerPass = 0; innerPass < 10; ++ innerPass) {
                    strategy.populate(rnd);
                    if (outerPass >= 5 && innerPass >= 5) {
                        Long totalTime = timings.get(strategyName);
                        if (totalTime == null) totalTime = 0L;
                        timings.put(strategyName, totalTime - System.currentTimeMillis());
                    }
                    Collection<Point> filtered = strategy.filter();
                    if (outerPass >= 5 && innerPass >= 5) {
                        Long totalTime = timings.get(strategyName);
                        timings.put(strategy.getClass().getSimpleName(), totalTime + System.currentTimeMillis());
                    }
                    CHECKSUM += filtered.hashCode();
                    System.err.printf("%-30s %d %d %d%n", strategy.getClass().getSimpleName(), outerPass, innerPass, filtered.size());
                    strategy.clear();
                }
            }
        }
        for (Map.Entry<String, Long> e: timings.entrySet()) {
            System.err.printf("%-30s: %9.2fms%n", e.getKey(), e.getValue() * (1.0/25.0));
        }
    }

    public static volatile int CHECKSUM = 0;

    static void populate(Collection<Point> dst, Random rnd) {
        for (int i = 0; i < INITIAL_SIZE; ++ i) {
            dst.add(new Point(rnd.nextInt(), rnd.nextInt()));
        }
    }

    static boolean wanted(Point p) {
        return p.hashCode() % 20 != 0;
    }

    static abstract class FilterStrategy {
        abstract void clear();
        abstract Collection<Point> filter();
        abstract void populate(Random rnd);
    }

    static final int INITIAL_SIZE = 100000;

    private static class CopyIntoNewListWithIterator extends FilterStrategy {
        public CopyIntoNewListWithIterator() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            ArrayList<Point> dst = new ArrayList<Point>(list.size());
            for (Point p: list) {
                if (wanted(p)) dst.add(p);
            }
            return dst;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class CopyIntoNewListWithoutIterator extends FilterStrategy {
        public CopyIntoNewListWithoutIterator() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            int inputSize = list.size();
            ArrayList<Point> dst = new ArrayList<Point>(inputSize);
            for (int i = 0; i < inputSize; ++ i) {
                Point p = list.get(i);
                if (wanted(p)) dst.add(p);
            }
            return dst;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class FilterLinkedListInPlace extends FilterStrategy {
        public String toString() {
            return getClass().getSimpleName();
        }
        FilterLinkedListInPlace() {
            list = new LinkedList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (Iterator<Point> it = list.iterator();
                 it.hasNext();
                 ) {
                Point p = it.next();
                if (! wanted(p)) it.remove();
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final LinkedList<Point> list;
    }

    private static class RandomRemoveByIndex extends FilterStrategy {
        public RandomRemoveByIndex() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (int i = 0; i < list.size();) {
                if (wanted(list.get(i))) {
                    ++ i;
                } else {
                    list.remove(i);
                }
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class SequentialRemoveByIndex extends FilterStrategy {
        public SequentialRemoveByIndex() {
            list = new LinkedList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (int i = 0; i < list.size();) {
                if (wanted(list.get(i))) {
                    ++ i;
                } else {
                    list.remove(i);
                }
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final LinkedList<Point> list;
    }

    private static class ShiftDown extends FilterStrategy {
        public ShiftDown() {
            list = new ArrayList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            int inputSize = list.size();
            int outputSize = 0;
            for (int i = 0; i < inputSize; ++ i) {
                Point p = list.get(i);
                if (wanted(p)) {
                    list.set(outputSize++, p);
                }
            }
            list.subList(outputSize, inputSize).clear();
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

}

Ответ 2

Копирование массива - довольно невысокая операция. Это делается на очень базовом уровне (свой собственный статический метод Java), и вы еще не достигли диапазона, когда производительность становится действительно важной.

В вашем примере вы копируете примерно 12000 раз массив размером 150000 (в среднем). Это не займет много времени. Я протестировал его здесь, на своем ноутбуке, и потребовалось менее 500 мс.

Обновление. Я использовал следующий код для измерения на моем ноутбуке (Intel P8400).

import java.util.Random;

public class PerformanceArrayCopy {

    public static void main(String[] args) {

        int[] lengths = new int[] { 10000, 50000, 125000, 250000 };
        int[] loops = new int[] { 1000, 5000, 10000, 20000 };

        for (int length : lengths) {
            for (int loop : loops) {

                Object[] list1 = new Object[length];
                Object[] list2 = new Object[length];

                for (int k = 0; k < 100; k++) {
                    System.arraycopy(list1, 0, list2, 0, list1.length);
                }

                int[] len = new int[loop];
                int[] ofs = new int[loop];

                Random rnd = new Random();
                for (int k = 0; k < loop; k++) {
                    len[k] = rnd.nextInt(length);
                    ofs[k] = rnd.nextInt(length - len[k]);
                }

                long n = System.nanoTime();
                for (int k = 0; k < loop; k++) {
                    System.arraycopy(list1, ofs[k], list2, ofs[k], len[k]);
                }
                n = System.nanoTime() - n;
                System.out.print("length: " + length);
                System.out.print("\tloop: " + loop);
                System.out.print("\truntime [ms]: " + n / 1000000);
                System.out.println();
            }
        }
    }
}

Некоторые результаты:

length: 10000   loop: 10000 runtime [ms]: 47
length: 50000   loop: 10000 runtime [ms]: 228
length: 125000  loop: 10000 runtime [ms]: 575
length: 250000  loop: 10000 runtime [ms]: 1198

Ответ 3

Я думаю, что разница в производительности, вероятно, сводится к различию в том, что ArrayList поддерживает произвольный доступ, если LinkedList не делает.

Если я хочу получить (1000) ArrayList, я указываю конкретный индекс для доступа к нему, однако LinkedList не поддерживает это, поскольку он организован с помощью ссылок Node.

Если я вызову get (1000) LinkedList, он будет перебирать весь список до тех пор, пока не найдет индекс 1000, и это может быть чрезмерно дорогостоящим, если у вас есть большое количество элементов в LinkedList.

Ответ 4

Интересные и неожиданные результаты. Это всего лишь гипотеза, но...

В среднем один из элементов вашего удаления элементов массива потребует переместить половину вашего списка (все после него) обратно на один элемент. Если каждый элемент является 64-битным указателем на объект (8 байтов), то это означает, что вы копируете 125000 элементов x 8 байтов на указатель = 1 МБ.

Современный процессор может быстро копировать смежный блок с объемом памяти 1 МБ в оперативную память.

По сравнению с циклом по связанному списку для каждого доступа, для которого требуются сравнения и ветвления и другие недружественные действия ЦП, копия ОЗУ выполняется быстро.

Вы должны действительно попробовать провести сравнительный анализ различных операций самостоятельно и посмотреть, насколько они эффективны с различными реализациями списков. Поделитесь своими результатами здесь, если вы это сделаете!

Ответ 5

Я пропущу некоторые детали реализации цели здесь, просто чтобы объяснить фундаментальное различие.

Чтобы удалить N-й элемент из списка элементов M, реализация LinkedList будет перемещаться до этого элемента, а затем просто удалить его и обновить указатели элементов N-1 и N + 1 соответственно. Эта вторая операция очень проста, но она подходит к этому элементу, который стоит вам времени.

Однако для ArrayList время доступа мгновенно, поскольку оно поддерживается массивом, что означает смежные пространства памяти. Вы можете перейти прямо к нужному адресу памяти, чтобы, в общем говоря, выполнить следующее:

  • перераспределить новый массив элементов M - 1
  • поместите все от 0 до N - 1 с индексом 0 в новый массив массивов
  • поместите все N + 1 в M по индексу N в массив массивов.

Размышляя об этом, вы заметите, что можете даже повторно использовать тот же массив, что и Java, который может использовать ArrayList с предустановленными размерами, поэтому, если вы удалите элементы, вы также можете пропустить шаги 1 и 2 и непосредственно сделать шаг 3 и обновить ваш размер.

Доступ к памяти выполняется быстро, и копирование блока памяти, вероятно, достаточно быстро на современном оборудовании, что переход на N-позицию слишком трудоемкий.

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

Но ясно, что в длинном списке выполнение простого удаления (i) будет дорогостоящим.

Чтобы добавить в него соль соли и пряностей: