Определить, имеют ли 2 списка одинаковые элементы независимо от порядка?
99917 просмотра
4 ответа
Извините за простой вопрос, но мне трудно найти ответ.
Когда я сравниваю 2 списка, я хочу знать, равны ли они в том, что они имеют одинаковое содержание, но в другом порядке.
Пример:
x = ['a', 'b']
y = ['b', 'a']
Я хочу x == y
оценить True
.
Ответы (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:261 плюс
Это, кажется, работает, хотя возможно громоздко для больших списков.
>>> 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
Вопросы из категории :
- python Обработка XML в Python
- python Как я могу использовать Python itertools.groupby ()?
- python Python: На какой ОС я работаю?
- python Как я могу создать непосредственно исполняемое кроссплатформенное приложение с графическим интерфейсом на Python?
- python Вызов функции модуля с использованием его имени (строки)
- list Функция транспонирования / распаковки (обратная сторона zip)?
- list How would you make a comma-separated string from a list of strings?
- list Удалить дубликаты из списка <T> в C #
- list Console.WriteLine и общий список
- list Как проверить, если список пуст?
- equality Comparing two collections for equality irrespective of the order of items in them
- equality Чем отличаются операторы сравнения PHP (== double equals) и тождества (=== triple equals)?
- equality Что такое «Лучшая практика» для сравнения двух экземпляров ссылочного типа?
- equality Есть ли разница между "==" и "есть"?
- equality Какой оператор равенства (== vs ===) следует использовать в сравнениях JavaScript?
- python-2.x В чем разница между функциями range и xrange в Python 2.X?
- python-2.x Нет модуля с именем MySQLdb
- python-2.x Setting the correct encoding when piping stdout in Python
- python-2.x Каков наилучший способ удалить акценты в строке Unicode Python?
- python-2.x Python 2 CSV Writer создает неверный терминатор строки в Windows