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

Ответ 1

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

Ответ 2

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

sorted(a) == sorted(b)

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

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True

Ответ 3

Если вы знаете, что элементы всегда хешируются, вы можете использовать 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)

Ответ 4

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

sorted(a) == sorted(b)

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

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

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

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

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

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

Ответ 5

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

from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")

Ответ 6

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

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

Ответ 7

https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual (первый, второй, msg = None)

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

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

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

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

Ответ 8

Пусть 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

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

Ответ 9

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

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

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

Для лучшего понимания см. мой ответ в этом вопросе