¿Determinar si 2 listas tienen los mismos elementos, independientemente del orden? [duplicar]
Perdón por la pregunta simple, pero me cuesta encontrar la respuesta.
Cuando comparo 2 listas, quiero saber si son "iguales" en el sentido de que tienen el mismo contenido, pero en diferente orden.
Ex:
x = ['a', 'b']
y = ['b', 'a']
Quiero x == yevaluar a True.
Simplemente puedes comprobar si los conjuntos múltiples con los elementos de xey son iguales:
import collections
collections.Counter(x) == collections.Counter(y)
Esto requiere que los elementos sean hash; El tiempo de ejecución estará en O(n), donde nestá el tamaño de las listas.
Si los elementos también son únicos, también puedes convertirlos en conjuntos (el mismo tiempo de ejecución asintótico, puede ser un poco más rápido en la práctica):
set(x) == set(y)
Si los elementos no son hash, sino ordenables, otra alternativa (tiempo de ejecución en O(n log n)) es
sorted(x) == sorted(y)
Si los elementos no se pueden ordenar ni ordenar, puede utilizar la siguiente función auxiliar. Tenga en cuenta que será bastante lento ( O(n²)) y generalmente no debería usarse fuera del caso esotérico de elementos que no se pueden dividir ni clasificar.
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
¿Determinar si 2 listas tienen los mismos elementos, independientemente del orden?
Infiriendo de su ejemplo:
x = ['a', 'b']
y = ['b', 'a']
que los elementos de las listas no se repetirán (son únicos) ni serán hash (qué cadenas y otros ciertos objetos inmutables de Python son), la respuesta más directa y computacionalmente eficiente utiliza los conjuntos integrados de Python (que son semánticamente como matemáticos conjuntos que quizá hayas aprendido en la escuela).
set(x) == set(y) # prefer this if elements are hashable
En el caso de que los elementos sean hash, pero no únicos, collections.Countertambién funciona semánticamente como un conjunto múltiple, pero es mucho más lento :
from collections import Counter
Counter(x) == Counter(y)
Prefiero usar sorted:
sorted(x) == sorted(y)
si los elementos son ordenables. Esto daría cuenta de circunstancias no únicas o no hashables, pero podría ser mucho más lento que usar conjuntos.
Experimento empírico
setUn experimento empírico concluye que , entonces, se debería preferir sorted. Opte por esta opción solo Countersi necesita otras cosas como recuentos o un uso adicional como conjunto múltiple.
Primera configuración:
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)
Y probando:
>>> min(timeit.repeat(sets_equal))
13.976069927215576
>>> min(timeit.repeat(counters_equal))
73.17287588119507
>>> min(timeit.repeat(sorted_lists_equal))
36.177085876464844
Entonces vemos que comparar conjuntos es la solución más rápida y comparar listas ordenadas es la segunda más rápida.
