Как эффективно сравнить два неупорядоченных списка (не наборов) в Python?

150
a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]

a и b следует считать равными, потому что они имеют точно такие же элементы, только в разном порядке.

Дело в том, что мои фактические списки будут состоять из объектов (экземпляров моих классов), а не целых чисел.

Johndir
источник
7
Как сравниваются объекты?
Марсело Кантос,
2
каков ожидаемый размер реальных списков? Будут ли сравниваемые списки иметь сопоставимые размеры или сильно отличаться? Вы ожидаете, что большинство списков совпадут или нет?
Дмитрий Б.
len()Сначала можно проверить .
глиняный кувшин

Ответы:

264

O (n) : лучше всего подходит метод Counter () (если ваши объекты хешируются):

def compare(s, t):
    return Counter(s) == Counter(t)

O (n log n) : метод sorted () является следующим лучшим (если ваши объекты можно заказать):

def compare(s, t):
    return sorted(s) == sorted(t)

O (n * n) : если объекты нельзя ни хэшировать, ни упорядочивать, можно использовать равенство:

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t
Раймонд Хеттингер
источник
1
Спасибо. Я преобразовал каждый объект в строку, а затем использовал метод Counter ().
johndir
Привет, @Raymond, я недавно столкнулся с этим вопросом на интервью и использовал sorted(), по общему признанию, не зная об этом Counter. Интервьюер настаивал на том, что существует более эффективный метод, и я явно ничего не сделал. После обширного тестирования на Python 3 с timeitмодулем, сортировка последовательно выполняется быстрее в списках целых чисел. В списках из 1 тыс. Пунктов примерно на 1,5% медленнее, а в коротких списках - 10 элементов - на 7,5% медленнее. Мысли?
arctelix
4
Для коротких списков анализ большого числа обычно не имеет значения, потому что время определяется постоянными факторами. Что касается более длинных списков, я подозреваю, что что-то не так с вашим сравнительным тестированием. Для 100 int с 5 повторениями в каждом я получаю: 127 мкс для сортировки и 42 для счетчика (примерно в 3 раза быстрее). На 1000 интервалов с 5 повторениями Counter в 4 раза быстрее. python3.6 -m timeit -s 'from collections import Counter' -s 'from random import shuffle' -s 't=list(range(100)) * 5' -s 'shuffle(t)' -s 'u=t[:]' -s 'shuffle(u)' 'Counter(t)==Counter(u)'
Раймонд Хеттингер,
@Raymond Действительно, мы получаем разные результаты. Я разместил свои настройки в чате sorted vs counter... Мне очень любопытно, что здесь происходит.
arctelix
5
Нет, спасибо. Меня не очень интересует отладка ложных сценариев синхронизации. Здесь много чего происходит (чистый код Python против кода C, временная сортировка применяется к рандомизированным данным и полуупорядоченным данным, различные детали реализации в разных версиях, количество дубликатов в данных и т. Д.)
Раймонд Хеттингер,
17

Вы можете отсортировать оба:

sorted(a) == sorted(b)

Подсчета рода также может быть более эффективным (но это требует , чтобы объект быть hashable).

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True
Марк Байерс
источник
Счетчик действительно использует хеширование, но объекты сами по себе не являются нехешируемыми. Вам просто нужно реализовать разумное __hash__, но это может быть невозможно для коллекций.
Йохен Ритцель
2
sorted тоже не будет работать для всех, например для комплексных чиселsorted([0, 1j])
Джон Ла Рой
1
sorted () также не работает с наборами, в которых операторы сравнения были переопределены для тестов подмножества / надмножества.
Раймонд Хеттингер,
12

Если вы знаете, что элементы всегда могут быть хешированы, вы можете использовать a, равное Counter()O (n).
Если вы знаете, что элементы всегда можно сортировать, вы можете использовать значение sorted()O (n log n)

В общем случае вы не можете полагаться на возможность сортировки или наличие элементов, поэтому вам нужен такой запасной вариант, который, к сожалению, O (n ^ 2)

len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)
Джон Ла Рой
источник
5

Лучший способ сделать это - отсортировать списки и сравнить их. (Использование Counterне будет работать с объектами, которые не хешируются.) Это просто для целых чисел:

sorted(a) == sorted(b)

С произвольными объектами становится немного сложнее. Если вы заботитесь об идентичности объекта, то есть о том, находятся ли одни и те же объекты в обоих списках, вы можете использовать эту id()функцию в качестве ключа сортировки.

sorted(a, key=id) == sorted(b, key==id)

(В Python 2.x вам фактически не нужен key=параметр, потому что вы можете сравнивать любой объект с любым объектом. Порядок произвольный, но стабильный, поэтому он отлично подходит для этой цели; не имеет значения, в каком порядке находятся объекты in, только порядок одинаков для обоих списков. Однако в Python 3 сравнение объектов разных типов запрещено во многих случаях - например, вы не можете сравнивать строки с целыми числами - поэтому, если у вас будут объекты различных типов, лучше всего явно использовать идентификатор объекта.)

С другой стороны, если вы хотите сравнить объекты в списке по значению, сначала вам нужно определить, что означает «значение» для объектов. Затем вам понадобится какой-то способ предоставить это в качестве ключа (а для Python 3 - как согласованный тип). Один из возможных способов, который сработает для множества произвольных объектов, - это сортировка по их repr(). Конечно, это может привести к потере уймы лишнего времени и repr()строк построения памяти для больших списков и так далее.

sorted(a, key=repr) == sorted(b, key==repr)

Если все объекты относятся к вашим собственным типам, вы можете определить __lt__()их, чтобы объект знал, как сравнивать себя с другими. Тогда вы можете просто отсортировать их и не беспокоиться о key=параметре. Конечно, вы также можете определить __hash__()и использовать Counter, что будет быстрее.

любезный
источник
4

Если вам нужно сделать это в тестах: https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual(first, second, msg=None)

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

Повторяющиеся элементы не игнорируются при сравнении первого и второго. Он проверяет, имеет ли каждый элемент одинаковое количество в обеих последовательностях. Эквивалентно: assertEqual (Counter (list (first)), Counter (list (second))), но также работает с последовательностями нехэшируемых объектов.

Новое в версии 3.2.

или в 2.7: https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

Вне тестов я бы порекомендовал этот Counterметод.

умнее
источник
2
(Что это добавляет к ответу jarekwg ?)
greybeard
3

Если список содержит элементы, которые не могут быть хешированы (например, список объектов), вы можете использовать класс Counter и функцию id (), например:

from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")
Марс
источник
2

Я надеюсь, что приведенный ниже фрагмент кода может сработать в вашем случае: -

if ((len(a) == len(b)) and
   (all(i in a for i in b))):
    print 'True'
else:
    print 'False'

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

Для лучшего понимания обратитесь к моему ответу на этот вопрос

Пабитра Пати
источник
2

Если сравнение должно выполняться в контексте тестирования, используйте assertCountEqual(a, b)( py>=3.2) и assertItemsEqual(a, b)( 2.7<=py<3.2).

Также работает с последовательностями нехэшируемых объектов.

jarekwg
источник
1

Пусть a, b списки

def ass_equal(a,b):
try:
    map(lambda x: a.pop(a.index(x)), b) # try to remove all the elements of b from a, on fail, throw exception
    if len(a) == 0: # if a is empty, means that b has removed them all
        return True 
except:
    return False # b failed to remove some items from a

Нет необходимости делать их хэшируемыми или сортировать.

Умур Контачи
источник
1
Да, но это O (n ** 2), как указано в нескольких других плакатах, поэтому его следует использовать только в том случае, если другие методы не работают. Он также предполагает наличие aподдержки pop(изменяемый) и index(является последовательностью). Raymond не предполагает ни того, ни другого, в то время как gnibbler предполагает только последовательность.
agf
0

Использование unittestмодуля дает вам чистый и стандартный подход.

import unittest

test_object = unittest.TestCase()
test_object.assertCountEqual(a, b)
Мейсам Садеги
источник
Что это добавляет к ответу jarekwg 4 года назад?
Tomerikoo