Самый быстрый способ сделать вычитание набора
У меня есть два Набора. 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;
}
}
И я хочу найти алгоритм, не только относится к Наборам, также работы для Массива.
Править: Набором здесь не является JAVA API, это - структура данных. таким образом, я не забочусь, если Java, API имеет removeAll () метод, я хочу, находят общее решение для этой проблемы, я имею, встречаются с большим количеством проблем как это, когда я использую JavaScript и Actionscript.
7 ответов
Не думаю, что у вас получится намного быстрее, но ваш код будет выглядеть проще и не станет медленнее от a.removeAll(b);. removeAll() является частью Java-API.
Для анализа эффективности: Ваш приведенный пример кода - O(n^2), что не очень хорошо, но и не самая ужасная вещь на земле (экспоненциальная сложность - это то, чего вы не хотите). Пока вы не знаете внутреннюю организацию данных в коллекции, вы не получите лучшей производительности. removeAll() реализуется самим классом и знает о внутренней организации. Поэтому если данные организованы в Hash, вы можете получить лучшие результаты, если данные организованы в несортированный массив, сложность будет одинаковой. Набор должен эффективно искать, если новый элемент уже есть в наборе, поэтому я подозреваю, что в качестве внутреннего представления используется что-то вроде Hash, особенно если реализация называется HashSet. :-)
EDIT: ОП изменил свой вопрос, чтобы упомянуть, что это не только для Java. removeAll() - это Java-API, поэтому это (или что-то подобное) может быть недоступно в других языках. Как уже было сказано, если коллекции представляют собой несортированные массивы без каких-либо других ограничений, то два цикла for-loops уже являются самым быстрым решением. Но если данные организованы по-другому, у вас есть более быстрые варианты. Если в двух коллекциях данные отсортированы (в моем примере первым идет наименьший элемент), можно сделать следующее (снизив сложность до 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. Возможны и другие варианты организации данных.
Учитывая, что b является подмножеством a, я не уверен, почему ваш псевдокод имеет 2 цикла. Мой будет просто:
foreach b in B
remove b from A
На практике то, как время выполнения этого сравнивается со временем выполнения вашего, зависит, среди прочего, от того, как вы реализовали набор как структуру данных.
В конце концов, выбор невелик, кроме как сравнивать элементы один за другим и удалять те, которые есть в обоих.
Чтобы сделать это по-другому, вам придется сделать что-то причудливое, например, дать всем членам множества уникальный индекс значения и создать огромный массив булевых чисел, представляющих каждое множество, а затем вы сможете выполнять битовые операции для вычитания B из A. Я понятия не имею, будет ли это быстрее, учитывая накладные расходы на создание уникальных индексов значений и манипуляции с очень большими битовыми массивами.
Я знаю, что вас не интересует решение на Java, но поскольку другие люди рекомендовали removeAll(), я хотел бы отметить, что она все еще делает по сути то же самое под прикрытием. Проверьте источник для HashSet.
Я полагаю, что вы найдете java.util.HashSet.removeAll(Collection toRemove) для хорошей работы.
С другой стороны, если у вас не множества, а отсортированные коллекции, вы можете справиться гораздо лучше.
Если множества хранятся так, что элементы доступны в любой момент времени в отсортированном порядке, то вы можете выполнить один линейный проход над обоими множествами и создать разницу за время O(n). Опять же, это если вы можете получить упорядоченные списки элементов бесплатно - это означает, что обслуживание (т.е. операции добавления и удаления элементов) множеств окупает стоимость хранения элементов доступными в отсортированном порядке.
Любая операция типа "removeAll", которая полагается на выполнение поиска, обязательно будет хуже, чем O(n).
(Мне приходит в голову, что построение разностного множества - то есть, ответа, построенного из линейного прохода над двумя списками - может быть O(n log n), если вы не будете предельно осторожны.)
.Вы видели метод removeAll в интерфейсе Set?
Также ознакомьтесь с этим вопросом на stack overflow.
ну, правильная идея уже была указана: набор должен быть реализован с использованием хеша. хэши в идеале имеют стоимость доступа 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];
}