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

Question

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

я сделать это таким образом:

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

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

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

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

Я разработать приложение для Android

Answer 1

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

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

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

Так над всем это

O (N^2)

операции в removeAll

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

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

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

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

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

этап 4: список результатов является вашим окончательным ответом

затраты варианты 3:

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

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

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

**

поэтому в целом O (NlogN) времени и О (п) пространство

**