Есть ли более быстрый способ проверить, имеют ли два списка те же самые элементы, что и Pythons, встроенные в оператор ==?

Question

Если у меня есть два списка, каждый из 800 элементов длинный и заполняется целыми числами. Есть ли более быстрый способ сравнить, что у них есть те же самые элементы (и короткое замыкание, если они этого не делают), чем с помощью встроенного оператора ==?

a = [6,2,3,88,54,-486] 
b = [6,2,3,88,54,-486] 
a == b 
>>> True 

Что-нибудь лучше этого?

Мне любопытно только потому, что у меня есть список гигант Список списков для сравнения.

Answer 1

Давайте не будем предполагать, но запустить некоторые тесты!

Абонентских вверх:

>>> import time 
>>> def timeit(l1, l2, n): 
     start = time.time() 
     for i in xrange(n): 
       l1 == l2 
     end = time.time() 
     print "%d took %.2fs" % (n, end - start) 

Два гигантского равноправный список:

>>> hugeequal1 = [10]*30000 
>>> hugeequal2 = [10]*30000 
>>> timeit(hugeequal1, hugeequal2, 10000) 
10000 took 3.07s 

Два гигантских списки, где первый элемент не равен:

>>> easydiff1 = [10]*30000 
>>> easydiff2 = [10]*30000 
>>> easydiff2[0] = 0 
>>> timeit(easydiff1, easydiff2, 10000) 
10000 took 0.00s 
>>> timeit(easydiff1, easydiff2, 1000000) 
1000000 took 0.14s 

Так оно кажется встроенный оператор равенства в списке действительно выполняет короткое замыкание.

EDIT: Интересно, что с помощью array.array модуль не делает его быстрее:

>>> import array 
>>> timeit(hugeequal1, hugeequal2, 1000) 
1000 took 0.30s 
>>> timeit(array.array('l', hugeequal1), array.array('l', hugeequal2), 1000) 
1000 took 1.11s 

numpy действительно получает вам хорошее ускорение, хотя:

>>> import numpy 
>>> timeit(hugeequal1, hugeequal2, 10000) 
10000 took 3.01s 
>>> timeit(numpy.array(hugeequal1), numpy.array(hugeequal2), 10000) 
10000 took 1.11s 

Answer 2

Встроенные функции CPython (которые, как я полагаю, вы используете), должны быть написаны на C. Таким образом, вы не получите гораздо быстрее, чем если бы вы не написали код C/C++, который использует какой-либо аспект вашего контекста ,

Answer 3

Numpy может ускорить это до 10 раз и особенно актуально, так как ваши списки имеют фиксированный (целочисленный) тип.

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

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

import numpy as np 
from timeit import timeit 

N = 10**7 

p0 = list(range(N)) 
p1 = list(range(N)) 

n0 = np.arange(N) 
n1 = np.arange(N) 

number = 500 
t = timeit("p0==p1", setup="from __main__ import p0, p1", number=number) 
print "pure python time =", t/number 

number = 500 
t = timeit("(n0==n1).all()", setup="from __main__ import n0, n1", number=number) 
print "numpy time =", t/number 

И результат в 10 раз быстрее, используя NumPy:

pure python time = 0.256077399254 
numpy time = 0.0286148643494 

Answer 4

Там нет никакого способа. Единственный способ узнать, равны ли два элемента, это сравнить их, и вам нужно сравнить все пары, чтобы узнать, равны ли они.

Тем не менее, вы все равно сможете получить ускорение. Если вы правильно используете NumPy ndarrays, NumPy может ускорить не только ваши сравнения, но и многое другое, что вы делаете с вашими данными. В качестве альтернативы, если есть какая-то внешняя информация, которую вы можете использовать, или какая-либо связь между тем, сравнивается ли одна пара списков и какая другая пара делает, вы можете использовать эту информацию, чтобы избежать некоторой работы по сравнению.

Answer 5

Другой вариант заключается в использовании pypy:

$ python -mtimeit -s 'a=[10]*30000;b=[10]*30000;print(a==b)' 
100000000 loops, best of 3: 0.0104 usec per loop 

$ pypy -mtimeit -s 'a=[10]*30000;b=[10]*30000;print(a==b)' 
1000000000 loops, best of 3: 0.00102 usec per loop 

И PyPy выполняет 10x быстрее для этого входа.

Answer 6

В зависимости от вашего использования вы можете переключиться на использование кортежей (которые не изменяются) и поместить списки в набор.

Другой вариант - отслеживать сходство (или нет) при создании списков.

Answer 7

Нет, нет возможности сделать сравнение, если два списка быстрее. Но вы говорите, что у вас есть гигантский список списков. И это звучит так, будто вы задаете неправильный вопрос. И если мы предположим, что вы хотите, чтобы выяснить, какие перечислены в списке списков, которые являются одинаковыми, то да, есть более быстрый способ сделать это:

>>> list_of_lists = [[1,2,3,4,5,6,7], [1,3,3,4,5,6,7], [1,2,3,4,5,6,6], [1,2,3,4,5,6,7]] 
>>> list_of_hashes = [hash(tuple(x)) for x in list_of_lists] 
>>> list_of_hashes 
[1738718158840515323, -9068250430673137562, 1738718158842010488, 1738718158840515323] 

Как вы видите здесь, я делаю хэш из каждого списка (я должен сначала сделать их в кортежи, потому что списки не хешируются). Тогда сравнение тривиально, так как теперь у вас есть список целых чисел, а не список списков. Если вы не заботитесь о порядке пунктов в списке, используйте вместо этого hash(set(x)).

>>> list_of_hashes[0] == list_of_hashes[1] 
False 
>>> list_of_hashes[0] == list_of_hashes[2] 
False 
>>> list_of_hashes[0] == list_of_hashes[3] 
True 

Это намного быстрее, если у вас много длинных списков, и вы сравниваете все списки со всеми другими списками.