Как я могу быстрее вычитать эти списки?

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

Я делаю так:

removeIDs=(ArrayList<Integer>) storedIDs.clone();
removeIDs.removeAll(downloadedIDs);

downloadIDs=(ArrayList<Integer>) downloadedIDs.clone();
downloadIDs.removeAll(storedIDs);

Проблема в том, что оба списка содержат 5000childs, и это занимает почти 4 секунды на моем Android-телефоне.

Есть ли быстрый способ сделать это? Является ли использование наборов более быстрым? (У меня нет повторяющихся значений в списках)

Я разрабатываю приложение для Android.

Ответ 1

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

Удаление элемента требует проверки полных реализаций списка для списка, сравнение HashSet - это просто вычисление хеш-кода, а затем идентификация целевого ведра.

Ответ 2

Установки должны быть быстрее. Прямо сейчас, он в основном выполняет цикл n ^ 2. Он перебирает каждый элемент removeID и проверяет, находится ли этот идентификатор в downloadID, что требует поиска всего списка. Если бы загруженные идентификаторы были сохранены в чем-то быстрее для поиска, например HashSet, это было бы намного быстрее и вместо O (n ^ 2) было бы O (n). В API Collections также может быть что-то более быстрое, но я этого не знаю.

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

Ответ 3

Я согласен с рекомендацией HashSet, если идентификаторы Integer не подходят в относительно небольшом диапазоне. В этом случае я бы оценил использование каждого из HashSet и BitSet и фактически использовал бы то, что быстрее для ваших данных в вашей среде.

Ответ 4

Прежде всего, я извиняюсь за длинный ответ. Если я ошибаюсь в любой момент, вы всегда можете исправить меня. Здесь я сравниваю некоторые варианты решения решения

ВАРИАНТ 1 <ArrayList> :

В коде, который вы использовали, метод ArrayList.removeAll позволяет посмотреть код removeAll

исходный код removeAll

public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }

поэтому вам нужно знать, что находится в методе batchRemove. Здесь ссылка . Ключевая часть здесь, если вы можете видеть

for (; r < size; r++)
         if (c.contains(elementData[r]) == complement)
                 elementData[w++] = elementData[r];

теперь рассмотрим метод contains, который является только оболочкой метода indexOf. ссылка. В методе indexOf выполняется операция O (n). (отметив здесь только часть)

 for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                    return i;

Таким образом, над всем это

О (п ^ 2)

в removeAll

ВАРИАНТ 2 <HashSet> : ранее я написал что-то здесь, но, похоже, я ошибся в какой-то момент, поэтому удалив это. Лучше возьмите предложение от эксперта по Hashset. Я не уверен в вашем случае, будет ли hashmap лучшим решением. Поэтому я предлагаю другое решение

ВАРИАНТ 3 < Мое предложение Вы можете попробовать > :

шаг 1:, если ваши данные отсортированы, тогда нет необходимости в этом шаге. Сортируйте список, который вы вычтите (второй список)

шаг 2: для каждого элемента несортированного списка выполните двоичный поиск во втором списке

шаг 3:, если совпадение не найдено, а затем сохранить в другом списке результатов, но если совпадение найдено, не добавляйте

шаг 4: список результатов - ваш окончательный ответ

Стоимость варианта 3:

шаг 1:, если не отсортировано O(nlogn) время

шаг 2: O(nlogn) время

шаг 3: O(n) пространство

, поэтому общее время O (nlogn) и O (n) пространство

Ответ 5

Если список необходим, вы можете выбрать LinkedList. В вашем случае, как сказал @Chris, реализация ArrayList будет перемещать все элементы при каждом удалении.

С LinkedList вы получите гораздо лучшую производительность для случайного добавления/удаления. См. Этот пост.