Как эффективно (производительность) удалить много элементов из списка в Java?

Question

У меня довольно большой список именованных элементов (> = 1 000 000 элементов) и некоторое условие, обозначенное , которое выбирает элементы для удаления, и верно для многих (возможно, половины) элементов в моем списке.

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

Вот мой код тестирования:

    System.out.println("preparing items");
    List<Integer> items = new ArrayList<Integer>(); // Integer is for demo
    for (int i = 0; i < 1000000; i++) {
        items.add(i * 3); // just for demo
    }

    System.out.println("deleting items");
    long startMillis = System.currentTimeMillis();
    items = removeMany(items);
    long endMillis = System.currentTimeMillis();

    System.out.println("after remove: items.size=" + items.size() + 
            " and it took " + (endMillis - startMillis) + " milli(s)");

и наивная реализация:

public static <T> List<T> removeMany(List<T> items) {
    int i = 0;
    Iterator<T> iter = items.iterator();
    while (iter.hasNext()) {
        T item = iter.next();
        // <cond> goes here
        if (/*<cond>: */i % 2 == 0) {
            iter.remove();
        }
        i++;
    }
    return items;
}

Как видите, я использовал индекс предмета по модулю 2 == 0 в качестве условия удаления () - только для целей демонтажа.

Какая лучшая версия removeMany может быть предоставлена ​​и почему эта лучшая версия на самом деле лучше?

Answer 1

Может быть, список не является оптимальной структурой данных для вас? Вы можете изменить это? Возможно, вы можете использовать дерево, в котором элементы отсортированы таким образом, что удаление одного узла удаляет все элементы, которые соответствуют условию? Или это хотя бы ускорит ваши операции?

В вашем упрощенном примере использование двух списков (один с элементами, где i% 2! = 0 - истина, а другой с элементами, где i% 2! = 0 - ложь) может быть полезным. Но это, конечно, очень зависит от домена.

Answer 2

Попробуйте реализовать рекурсию в вашем алгоритме.