Определить, имеют ли 2 списка одинаковые элементы независимо от порядка?

python list equality python-2.x

99917 просмотра

4 ответа

Извините за простой вопрос, но мне трудно найти ответ.

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

Пример:

x = ['a', 'b']
y = ['b', 'a']

Я хочу x == yоценить True.

Автор: toofly Источник Размещён: 12.11.2019 09:13

Ответы (4)


146 плюса

Решение

Вы можете просто проверить, равны ли мультимножества с элементами x и y:

import collections
collections.Counter(x) == collections.Counter(y)

Это требует, чтобы элементы были хэшируемыми; будет время выполнения O(n), где nразмер списков.

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

set(x) == set(y)

Если элементы не являются хэшируемыми, но сортируемыми, другой альтернативой (время выполнения в O(n log n)) является

sorted(x) == sorted(y)

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

def equal_ignore_order(a, b):
    """ Use only when elements are neither hashable nor sortable! """
    unmatched = list(b)
    for element in a:
        try:
            unmatched.remove(element)
        except ValueError:
            return False
    return not unmatched
Автор: phihag Размещён: 15.01.2012 12:40

22 плюса

Определить, имеют ли 2 списка одинаковые элементы независимо от порядка?

Исходя из вашего примера:

x = ['a', 'b']
y = ['b', 'a']

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

set(x) == set(y) # prefer this if elements are hashable

В случае если элементы являются хэшируемыми, но не уникальными, collections.Counterсемантически также работает как мультимножество, но это намного медленнее :

from collections import Counter
Counter(x) == Counter(y)

Предпочитаю использовать sorted:

sorted(x) == sorted(y) 

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

Эмпирический Эксперимент

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

Первая настройка:

import timeit
import random
from collections import Counter

data = [str(random.randint(0, 100000)) for i in xrange(100)]
data2 = data[:]     # copy the list into a new one

def sets_equal(): 
    return set(data) == set(data2)

def counters_equal(): 
    return Counter(data) == Counter(data2)

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2)

И тестирование:

>>> min(timeit.repeat(sets_equal))
13.976069927215576
>>> min(timeit.repeat(counters_equal))
73.17287588119507
>>> min(timeit.repeat(sorted_lists_equal))
36.177085876464844

Итак, мы видим, что сравнение наборов - самое быстрое решение, а сравнение отсортированных списков - второе по быстродействию.

Автор: Aaron Hall Размещён: 02.10.2014 03:26

1 плюс

Это, кажется, работает, хотя возможно громоздко для больших списков.

>>> A = [0, 1]
>>> B = [1, 0]
>>> C = [0, 2]
>>> not sum([not i in A for i in B])
True
>>> not sum([not i in A for i in C])
False
>>> 

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

>>> A = [0, 1, 2]
>>> not sum([not i in A for i in B])
True

Проблема возникает, когда len(A) != len(B)и, в этом примере len(A) > len(B),. Чтобы избежать этого, вы можете добавить еще одно утверждение.

>>> not sum([not i in A for i in B]) if len(A) == len(B) else False
False

Еще одна вещь, я сравнил свое решение с timeit.repeat при тех же условиях, которые использовал Аарон Холл в своем посте. Как и предполагалось, результаты разочаровывают. Мой метод последний. set(x) == set(y)это.

>>> def foocomprehend(): return not sum([not i in data for i in data2])
>>> min(timeit.repeat('fooset()', 'from __main__ import fooset, foocount, foocomprehend'))
25.2893661496
>>> min(timeit.repeat('foosort()', 'from __main__ import fooset, foocount, foocomprehend'))
94.3974742993
>>> min(timeit.repeat('foocomprehend()', 'from __main__ import fooset, foocount, foocomprehend'))
187.224562545
Автор: blahreport Размещён: 19.01.2015 02:40

0 плюса

Как упомянуто в комментариях выше, общий случай - боль. Это довольно легко, если все элементы можно хэшировать или все элементы можно сортировать. Однако недавно мне пришлось попытаться раскрыть общий случай. Вот мое решение. После публикации я понял, что это дубликат вышеупомянутого решения, которое я пропустил при первом проходе. В любом случае, если вы используете слайсы, а не list.remove (), вы можете сравнить неизменяемые последовательности.

def sequences_contain_same_items(a, b):
    for item in a:
        try:
            i = b.index(item)
        except ValueError:
            return False
        b = b[:i] + b[i+1:]
    return not b
Автор: Grahame Размещён: 12.12.2015 02:23
Вопросы из категории :
32x32