Фильтрация списка: воссоздать из пустого списка или скопировать и удалить элементы?

Question

У меня есть ArrayList, и мне нужно отфильтровать его (только до удалить некоторых элементов).

Я не могу изменить исходный список .

Какой мой лучший вариант в отношении выступлений :

• Воссоздать другой список из исходного и удалить из него элементы:

код:

List<Foo> newList = new ArrayList<Foo>(initialList);
for (Foo item : initialList) {
    if (...) {
        newList.remove(item);
    }
}

• Создайте пустой список и добавьте элементы:

код:

List<Foo> newList = new ArrayList<Foo>(initialList.size());
for (Foo item : initialList) {
    if (...) {
        newList.add(item);
    }
}

Какой из этих вариантов лучше? Должен ли я использовать что-то еще, кроме ArrayList? (Хотя я не могу изменить тип исходного списка)

Как примечание, примерно 80% предметов будут сохранены в списке. Список содержит от 1 до около 20 элементов.

Answer 1

Лучший вариант - использовать то, что проще всего написать и поддерживать.

Если производительность является проблемой, вам следует профилировать приложение впоследствии, а не оптимизировать преждевременно.

Кроме того, я бы использовал фильтрацию из библиотек, таких как google-collection или commons collection, чтобы сделать код более читабельным:

Collection<T> newCollection = Collections2.filter(new Predicate<T>() {
    public boolean apply(T item) {
        return (...); // apply your test here
    }
});

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

String[] arr = new String[initialList.size()];
String[] src = initialList.toArray(new String[initialList.size()]);
int dstIndex = 0, blockStartIdx=0, blockSize=0;
for (int currIdx=0; currIdx < initialList.size(); currIdx++) {
    String item = src[currIdx];
    if (item.length() <= 4) {
        if (blockSize > 0)
            System.arraycopy(src, blockStartIdx, arr, dstIndex, blockSize);
            dstIndex += blockSize;
            blockSize = 0;
        } else {
            if (blockSize == 0)
                blockStartIdx = currIdx;
            blockSize++;
        }
    }
    ArrayList newList = new ArrayList(arr.length + 1);
    newList.addAll(Arrays.asList(arr));
}

Кажется, он примерно на 20% быстрее, чем ваш вариант 3. Тем более (40%), если вы можете пропустить новое создание ArrayList в конце.

См .: http://pastebin.com/sDhV8BUL

Answer 2

Как говорит @Sanjay, «если сомневаешься, измеряй».Но создание пустого ArrayList с последующим добавлением к нему элементов является наиболее естественной реализацией, и вашей первой целью должно быть написание ясного, понятного кода.И я на 99,9% уверен, что он будет быстрее.

Обновление: копируя старый список в новый, а затем вычеркивая ненужные элементы, вы несете стоимость элементаудаление.Метод ArrayList.remove () должен выполнять итерацию до конца массива при каждом удалении, копируя каждую ссылку вниз на позицию в списке.Это почти наверняка будет дороже, чем просто создать новый ArrayList и добавить к нему элементы.

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

Answer 3

Возможно, вы захотите создать новый список из исходного и удалить его. Таким образом, это будет меньше вызовов метода, поскольку вы сохраняете ~ 80% исходных элементов.

Кроме этого, я не знаю, как фильтровать предметы.

Редактировать: Очевидно, что в Google Collections есть что-то , что может вас заинтересовать?

Answer 4

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

Вот выводы (с ArrayList из String).

• Решение 1, удалить элементы из копии: 2400 мс .

• Решение 2, создайте пустой список и заполните его: 1600 мс . newList = new ArrayList<Foo>();

• Решение 3, такое же, как 2, за исключением того, что вы устанавливаете начальный размер списка: 1530 мс . newList = new ArrayList<Foo>(initialList.size());

• Решение 4, такое же, как 2, за исключением того, что вы установили начальный размер списка + 1: 1500 мс . newList = new ArrayList<Foo>(initialList.size() + 1); (как объяснил @Soronthar)

Источник: http://pastebin.com/c2C5c9Ha

Answer 5

второй быстрее (итерируйте и добавляйте ко второму при необходимости), и код для первого выдает исключение ConcurrentModificationException при удалении любых элементов

, и в зависимости от того, какой тип результата будет зависеть от того, кем вы являетесьпонадобится отфильтрованный список для

Answer 6

Сначала я бы последовал старому совету;если сомневаетесь, измерьте.

Должен ли я использовать что-то еще, кроме ArrayList?

Это зависит от того, какие операции вы будете выполнять в отфильтрованном списке, но ArrayListОбычно это хорошая ставка, если вы не делаете что-то, что на самом деле не должно поддерживаться непрерывным списком элементов (т.е. массивов).

List newList = new ArrayList (initialList.size ());

Я не хочу придираться, но если ваш новый список не будет превышать 80% от первоначального размера, почему бы не настроить тонкую начальную емкость на ((int)(initialList.size() * .8) + 1)