Удаление объектов в Java ArrayList - потребление времени

Ответ 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.