Удаление объектов в Java ArrayList - потребление времени
Я пытаюсь удалить 140 000 объектов из ArrayList размером 7,140,000. Я ожидал, что это займет несколько секунд (если это произойдет), но вместо этого Java занимает несколько секунд на тысячу объектов. Вот мой код:
for (int i = list.size(); i > P; i--)
{
int size = list.size();
int index = (int) (Math.random() * size);
list.remove(index);
}
Примечание: P - это константа, которую я ранее установил в 7 000 000.
Цель цикла - случайное удаление объектов из списка, пока его размер не достигнет 7 000 000.
Является ли Java таким долгое время, потому что я начинаю с более чем 7 миллионов объектов? Я никогда не замечал этой проблемы эффективности с удалением из ArrayLists в прошлом. Если это помогает, я использую IDE DrJava Beta.
Ответы
Ответ 1
ArrayList поддерживается массивом, поэтому модификации должны действительно перемещать элементы в сторону, а в некоторых случаях даже создавать целый новый массив.
Некоторые возможные решения:
-
Вместо этого рассмотрите возможность использования LinkedList или реализации списка пропуска. Обратите внимание, что здесь, чтобы удалить элемент, он по-прежнему принимает O (N) (или O (logN) в skip-list), потому что он должен его найти. Однако вы можете перемещать элементы со случайностью, исходя из количества удаленных элементов.
-
Вы можете случайно взять элементы из ввода в новый ArrayList, пока не получите количество элементов, которые вы хотите. Вы должны знать, какие элементы вы добавили, так что перемещайтесь линейным способом и имеете случайный выбор, чтобы иметь шанс, сколько шагов нужно выполнить, исходя из количества перемещенных элементов.
-
Самое простое решение: перетасовать весь массив ввода, а затем выбрать первые M элементов.
Здесь возможный код для решения № 3:
public static List<String> pickNRandom(List<String> lst, int m) {
Collections.shuffle(lst);
return lst.subList(0, n);
}
Недостатком здесь является то, что он разрушает порядок элементов. Вы можете преодолеть это, создав копию списка в качестве входа, но это займет больше памяти (временно)...
Ответ 2
Каждый раз, когда вы удаляете элемент из массива ArrayList, он должен перетасовывать все элементы с большими индексами вниз на один слот. Предположим, вы удалили первый элемент списка 7M-элементов - вам также нужно было перемещать 6999,999 элементов.
Если вы делаете это в цикле, это займет время O(n^2)
, где n
- размер списка. Для списка 7M-элементов это будет довольно медленным.
Вместо этого, если вы знаете, какие элементы вы хотите удалить заранее, вы можете переместить все элементы за один проход:
int dst = 0;
for (int src = 0; src < list.size(); ++src) {
if (!toRemove(src)) {
list.set(dst++, list.get(src));
}
}
list.subList(dst, list.size()).clear();
где toRemove(src)
- некоторая функция, которая говорит, хотите ли вы удалить элемент src
-th.
Например, вы можете создать BitSet
со всеми, кроме P
элементами:
BitSet toRemove = new BitSet(list.size());
for (int i = list.size(); i > P; i--) {
int rand;
do {
rand = Math.random() * list.size();
} while (toRemove.get(rand));
toRemove.set(rand, true);
}
Вам все равно придется переместить все 6999,999 элементов вправо, если вы просто удалите нулевой элемент из списка элементов 7M; но любые другие удаления не требуют больше сдвигов сверху. Этот алгоритм O(n)
, где n - размер списка.
Изменить: вы можете выбрать элементы P
из списка (где P <= list.size()
) следующим образом:
int dst = 0;
Random rand = new Random();
for (int src = 0; dst < P; ++src) {
if (rand.nextInt(list.size() - src) < (P-dst)) {
list.set(dst++, list.get(src));
}
}
list.subList(dst, list.size()).clear();
Эта стратегия будет выбирать элементы из списка с равной вероятностью (*) и хорошо работает для любого значения P
; он также сохраняет первоначальный порядок.
Если вы хотите отбирать элементы K
из списка с помощью элементов n
без рисования одного и того же элемента дважды, существует способ choose(N, K) = N! / (K! * (N-K)!)
. Если вы хотите выбрать все элементы из списка с равной вероятностью, вы должны выбрать любую из этих c(n,k)
различных конфигураций.
Когда есть элементы K
, оставшиеся для выбора из элементов n
, вы будете либо:
- выберите первый элемент; а затем выберите
k-1
элементы из оставшихся элементов n-1
; или
- не выберите первый элемент; а затем выберите
K
элементы из остальных элементов n-1
.
Чтобы обеспечить равную вероятность выбора элементов K
в целом, вам нужно выбрать один из двух вариантов в соответствии с количеством комбинаций для выбора из элементов n-1
:
#(combinations after taking first item)
P(take first item) = ------------------------------------------------------------------
#(combinations after taking) + #(combinations after not taking)
= C(n-1,k-1) / (C(n-1, k-1) + C(n-1, k))
= ... working omitted ...
= k / n
Итак, когда у вас есть K
элементы, оставшиеся от n
, вы должны взять первый элемент k/n
того времени.
Два интересных случая для обозначения:
- Когда
k == n
, k/n = 1
, вы всегда берете элемент. Интуитивно, если вам нужно выбрать n
элементы из n
, вам нужно взять их все.
- Когда
k == 0
, k/n = 0
, вы никогда не берете элемент. Интуитивно, если вы уже выбрали все K
своих товаров, вам больше не нужно брать.
Чтобы реализовать это, вы можете просто создать равномерно распределенное случайное число r
в диапазоне [0..n)
и "взять" элемент из списка, если r < k
.
В терминах реализации выше, k = P - dst
и n = list.size() - src
.