Поиск элементов, которые присутствуют в одном наборе, а не в другом - PullRequest
1 голос
/ 02 декабря 2009

У меня есть два набора A и B.

A
--
1
2
6

B
--
1
2
3
4

Когда я сравниваю набор A с B, мне нужно получить значение 6 в качестве выхода и значение 4 в качестве выхода, когда набор B сравнивается с A.

Мне интересно, каков наилучший алгоритм для этого? Я написал один, но он имеет квадратичную сложность. Это в основном итерация одного набора, а внутри цикла итерация второго набора для проверки существования значения. Мне это показалось неэффективным.

Context

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

Итак, я передаю первый набор, в котором будут элементы, которые были добавлены и уже существуют. Я загружаю другой набор, который будет иметь все элементы из базы данных. Теперь, если я применю приведенный выше алгоритм для сравнения Set A (новый список) с Set B (список базы данных) и возьму элементы, которые существуют в SetA, а не в SetB, я получу все вновь добавленные элементы. Затем SetB будет сравниваться с SetA, и все элементы, которые существуют в setB и не существуют в SetA, будут удалены. Я открыт для предложений по лучшему алгоритму.

Любая помощь будет отличной.

Ответы [ 6 ]

3 голосов
/ 02 декабря 2009

В Python

>>> A=set((1,2,6))
>>> B=set((1,2,3,4))
>>> A-B
set([6])
>>> B-A
set([3, 4])

Если у вас нет встроенного типа набора
Psudocode:

# This computes the items of B that are not in A
a=hash(A)   # Hopefully you at least have some sort of hash type
result=[]   #empty list
for item in B:
    if item not in a:
        result.append(item)
2 голосов
/ 02 декабря 2009

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

Для несортированных наборов, сначала сортируя их по времени O (n log (n)), а затем сравнивая их по линейному времени, получаем общую сложность времени O (n log (n)). В зависимости от деталей вашего приложения может быть также возможно постоянно сохранять отсортированные наборы, что позволяет легко сравнивать их при необходимости.

0 голосов
/ 25 марта 2012

Проверьте Apache CollectionUtils, где вы найдете множество операций, таких как объединение, пересечение или вычитание (что вам нужно)

0 голосов
/ 02 декабря 2009

Если у вас есть доступ к реализации хеш-наборов (я думаю, что у Java, C # и Python все они есть), вы можете просто создать два набора, A и B, и принять разницу между наборами. Если разность наборов не определена, вы можете просто перебрать элементы A и проверить, есть ли в B каждый из них или нет. Хеш-набор реализован с помощью хеш-таблицы, поэтому он может быть построен за линейное время, а членство может быть проверено за постоянное время. Это означает, что общее время будет линейным в сумме установленных размеров.

0 голосов
/ 02 декабря 2009

Вы можете поместить оба набора в сбалансированные бинарные деревья. Поиск элемента в одном наборе против другого набора O(log n). Таким образом, поиск n' элементов в одном наборе против другого набора будет O(n' log n) или просто O(n log n).

Если оба набора преобразованы в отсортированные массивы, вы можете выполнять пошаговую обработку обоих массивов в O(n + n') или O(n) раз, чтобы определить, отсутствует ли элемент в любом наборе.

0 голосов
/ 02 декабря 2009

Здесь - ответ от Microsoft. Выглядит O (n 2 ) мне, хотя

class CompareLists
{        
    static void Main()
    {
        // Create the IEnumerable data sources.
        string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
        string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");

        // Create the query. Note that method syntax must be used here.
        IEnumerable<string> differenceQuery =
          names1.Except(names2);

        // Execute the query.
        Console.WriteLine("The following lines are in names1.txt but not names2.txt");
        foreach (string s in differenceQuery)
            Console.WriteLine(s);

        // Keep the console window open in debug mode.
        Console.WriteLine("Press any key to exit");
        Console.ReadKey();
    }
}
/* Output:
     The following lines are in names1.txt but not names2.txt
    Potra, Cristina
    Noriega, Fabricio
    Aw, Kam Foo
    Toyoshima, Tim
    Guy, Wey Yuan
    Garcia, Debra
     */
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...