Самый быстрый способ сделать вычитание коллекции

Question

У меня есть два комплекта. Set b является подмножеством Set a. они оба очень большие наборы. Я хочу вычесть b из a, как лучше всего выполнять эту обычную операцию? Я написал много таких кодов, и я не думаю, что это эффективно. какая у тебя идея ?

псевдокод: (это не Java API).

for(int i = 0 ; i < a.size(); i++) {
          for (int j=0 ; j < b.size() ;j++) {
              // do comparison , if found equals ,remove from a
              break;
          }
 }

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

РЕДАКТИРОВАТЬ: Set здесь это не JAVA API, это структура данных. поэтому мне все равно, если в Java API есть метод removeAll (), я хочу найти общее решение этой проблемы, я сталкиваюсь с множеством подобных проблем при использовании Javascript и Actionscript.

Answer 1

Не думаю, что вы получите это намного быстрее, но ваш код будет выглядеть проще и не станет медленнее a.removeAll(b);. removeAll () является частью Java-API.

Для анализа эффективности: Ваш пример кода O (n ^ 2), который масштабируется не очень хорошо, но также не является самой ужасной вещью на земле (экспоненциальная сложность - вещь, которую вы не хотите). Пока вы не знаете внутреннюю организацию данных в Коллекции, вы не получите более высокую производительность. removeAll () реализуется самим классом и знает о внутренней организации. Таким образом, если данные организованы в Hash, вы можете получить лучшие результаты, если данные организованы в несортированный массив, сложность будет той же. Набор должен эффективно искать, если новый элемент уже находится в наборе, поэтому я подозреваю, что какой-то Hash является внутренним представлением, особенно если реализация называется HashSet. : -)

РЕДАКТИРОВАТЬ: ОП изменил вопрос, чтобы упомянуть, что это не только для Java. removeAll () - это Java-API, так что это (или что-то подобное) может быть недоступно на других языках. Как было сказано ранее, если коллекции являются несортированными массивами без каких-либо других ограничений, два цикла for уже являются самым быстрым решением. Но если данные организованы иначе, у вас есть более быстрые варианты. Если две коллекции являются отсортированными данными (в моем примере сначала идет наименьший элемент), вы можете сделать следующее (уменьшив сложность до O (n)):

int bIndex = 0;
for(int i = 0 ; i < a.size(); i++) {
          while (a[i] < b[bIndex]) {bIndex++;}
          if (a[i] == b[bIndex]) {markForRemoval(a[i]);} // I mark this only for removal, as the actual removal would make your index incorrect
}

Если данные организованы в виде хэша в обеих коллекциях, вам также нужен только один цикл for, который напрямую обращается к элементу в b. Возможны другие возможные организации данных.

Answer 2

Учитывая, что b является подмножеством a, я не уверен, почему ваш псевдокод имеет 2 цикла. Мой просто будет:

foreach b in B
    remove b from A

На практике, как это время выполнения сравнивается с вашим временем выполнения, зависит, среди прочего, от того, как вы реализовали набор как структуру данных.

Answer 3

хорошо, правильная идея уже была указана: множество должно быть реализовано с использованием хеша. хеши в идеале имеют O(1) стоимость доступа, поэтому вы можете получить O(min(m,n)) стоимость всей операции, если вы можете определить, какой набор больше (например, поддержание счетчика во время операций вставки / удаления).

в ActionScript 3, вы бы использовали Словарь . просто используйте элементы в качестве ключей и значений.

удаление выглядит так:

for each (var key:* in set2) {//a simple for-in loop will also do the trick, since keys and values are equal, but for-each-in loops perform faster
    delete set1[key];
}

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

удаление выглядит так:

for (var key in set2) {
    delete set1[key];
}

Answer 4

Если наборы поддерживаются так, что элементы доступны в любой момент времени в отсортированном порядке, то вы можете выполнить один линейный проход для обоих наборов и создать разницу во времени O (n). Опять же, это , если , то вы можете бесплатно получить список упорядоченных списков элементов & mdash; это означает, что поддержание (т.е. операции добавления-элемента и удаления-элемента) наборов оплачивает стоимость сохранения элементов в отсортированном порядке.

Любая операция по удалению, которая зависит от выполнения поиска, обязательно будет хуже, чем O (n).

(Мне приходит в голову, что построение набора разностей - то есть ответ, составленный из линейного прохода по двум спискам - может быть O (n log n), если вы не очень осторожны.)

Answer 5

В конце концов, нет другого выбора, кроме как один за другим сравнить элементы и удалить те, которые есть в обоих.

Чтобы сделать это по-другому, вам нужно сделать что-то необычное, например, дать всем членам набора уникальный индекс значения и создать огромный массив логических значений, представляющих каждый набор, а затем вы можете выполнить битовые операции, чтобы вычесть B из A Я понятия не имею, будет ли это быстрее, учитывая накладные расходы на создание уникальных индексов значений и манипулирование очень большими битовыми масками.

Я знаю, что вы не заботитесь о Java-решении, но, поскольку другие люди рекомендовали removeAll (), я хотел бы отметить, что он по-прежнему делает то же самое под покровом. Проверьте источник для HashSet.

Answer 6

Операция, которую вы пишете, это O (N ^ 2), но если наборы велики, вы можете использовать хеш.

// A is some kind of array, O(1) iteration
// B is a hash containing elements to remove, O(1) contains(elt)
List<T> removeAll(List<T> A, Set<T> B) {
  List<T> result; // empty, could preallocate at |A|
  for (elt : A) { // for each 'elt' belonging to A, hence O(|A|)
    if (! B.contains(elt) ) { // O(1) thanks to hash
      C.add(elt) ; // ensure this is O(1) with preallocation or linked list
    }
  }
  return result;
}

Это требует индексации множества B, поэтому вам нужна хеш-функция. В Java вы можете использовать Set<T> Bh = new HashSet<T>(B);, что равно O (| B |) во времени и памяти. Таким образом, в целом мы получаем O (| A | + | B |) во времени и примерно O (2 | A | +2 | B |)) в памяти. Конечно, превосходит квадратичное значение removeAll, вы почувствуете разницу (TM).

Вероятно, лучше скопировать элементы в новый массив (как это сделано в псевдокоде), поскольку непосредственное удаление элементов из A может привести к накладным расходам, если вы будете держать элементы в порядке (смещение элементов влево в A обходится дорого). 1007 *

Answer 7

Я полагаю, вы найдете java.util.HashSet.removeAll(Collection toRemove), чтобы хорошо работать. С другой стороны, если у вас нет наборов , но отсортированы коллекции, возможно, вы сможете сделать намного лучше.

Answer 8

Вы видели метод removeAll в интерфейсе Set?

Также проверьте этот вопрос переполнения стека .