Самый эффективный способ печати различий двух массивов?

Question

Недавно мой коллега спросил меня, как он может проверить равенство двух массивов. У него было два источника Address и он хотел утверждать, что оба источника содержат точно такие же элементы, хотя порядок не имеет значения. Оба использования Array или как List в Java, или IList было бы в порядке, но так как может быть два равных Address объектов, вещи, такие как Set s не могут быть использованы.

В большинстве языков программирования List уже имеет метод equals, выполняющий сравнение (при условии, что коллекция была заказана до его выполнения), но нет информации о фактических различиях; только, что есть некоторые, или нет.

Результат должен содержать информацию об элементах, находящихся в одной коллекции, но не в другом, и наоборот.

Очевидным подходом было бы перебрать одну из коллекций (если один из них), и просто вызвать contains(element) на другом, а затем сделать это наоборот. Предполагая сложность O(n) для contains, это приведет к O(2n²), если я прав.

Есть ли более эффективный способ получения информации «А1 и А2 нет в списке1, А3 и А4 нет в списке2»? Существуют ли структуры данных, лучше подходящие для выполнения этой работы, чем списки? Стоит ли сортировать коллекции раньше и использовать пользовательский бинарный поиск?

Answer 1

Первое, что приходит на ум использует множество различий

В псевдо-питона

addr1 = set(originalAddr1) 
addr2 = set(originalAddr2) 
in1notin2 = addr1 - addr2 
in2notin1 = addr2 - addr1 
allDifferences = in1notin2 + in2notin1 

Из here вы можете видеть, что множество различий является O(len(set)) и объединение O(len(set1) + len(set2)) дает вам решение за линейное время с этой реализацией python set, а не квадратичной, как вы предлагаете.

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

Answer 2

Стоит ли сортировать коллекцию [...]?

Сравните наивный подход O(n²) для сортировки два списков в O(n logn), а затем сравнивая их в O(n) - или сортировки одного списка в O(n logn) и итерации других в O(n)