Python: Самый быстрый способ сравнить массивы elementwise

Question

Я ищу самый быстрый способ вывода индекса первой разности двух массивов в Python. Например, давайте рассмотрим следующие два массива:

test1 = [1, 3, 5, 8] 
test2 = [1] 
test3 = [1, 3] 

Сравнение test1 и test2, я хотел бы выход 1, в то время как сравнение test1 и test3 Выведите 2.

Другими словами, я ищу эквивалент заявления:

import numpy as np 
np.where(np.where(test1 == test2, test1, 0) == '0')[0][0] 

с различной длиной массива.

Любая помощь приветствуется.

Answer 1

Для списков это работает:

from itertools import zip_longest 

def find_first_diff(list1, list2): 
    for index, (x, y) in enumerate(zip_longest(list1, list2, 
               fillvalue=object())): 
     if x != y: 
      return index 

zip_longest колодки более короткий список с None или с значением параметра заполнения. Стандарт zip не работает, если разность вызвана разными списками, а не фактическими разными значениями в списках.

На Python 2 используйте izip_longest.

Обновлено: создано уникальное значение заполнения, чтобы избежать потенциальных проблем с None в качестве значения списка. object() уникален:

>>> o1 = object() 
>>> o2 = object() 
>>> o1 == o2 
False 

Это чистый Python подход может быть быстрее, чем решение NumPy. Это зависит от фактических данных и других обстоятельств.

1. Преобразование списка в массив NumPy также требует времени. Это может привести к тому, что займет больше времени, чем поиск индекса с помощью указанной выше функции. Если вы не используете для использования массива NumPy для других вычислений, преобразование может привести к значительным накладным расходам.

2. NumPy всегда ищет полный массив. Если разница наступает раньше, вы делаете намного больше работы, чем вам нужно.

3. NumPy создает пучок промежуточных массивов. Это стоит памяти и времени.

4. NumPy необходимо построить промежуточные массивы с максимальной длиной. Сравнивая многие небольшие с очень большими массивами, здесь неблагоприятно.

В общем, NumPy во многих случаях быстрее, чем чистое решение Python. Но каждый случай немного отличается, и есть ситуации, когда чистый Python быстрее.

Answer 2

Самый быстрый алгоритм будет сравнивать каждый элемент до первой разницы и не более.Так переборе двух списков попарно, как это даст вам следующее:

def findFirstDifference(list1, list2): 
    minLength = min(len(list1), len(list2)) 
    for index in xrange(minLength): 
    if list1[index] != list2[index]: 
     return index 
    return minLength # the two lists agree where they both have values, so return the next index 

Что дает вывод, который вы хотите:

print findFirstDifference(test1, test3) 
> 2 

Answer 3

с Numpy массивами (что будет быстрее для больших массивов), то вы могли бы проверить длину списков затем (также) проверить перекрывающих друг друга ЧАСТЕЙ что-то вроде следующего (очевидно нарезка дольше длине короче):

import numpy as np 

n = min(len(test1), len(test2)) 
x = np.where(test1[:n] != test2[:n])[0] 
if len(x) > 0: 
    ans = x[0] 
elif len(test1) != len(test2): 
    ans = n 
else: 
    ans = None 

EDIT - несмотря на т его проголосовали, я оставлю свой ответ здесь, если кому-то еще нужно сделать что-то подобное.

Если стартовые массивы большие и числовые, то это самый быстрый способ. Также мне пришлось изменить код Энди, чтобы заставить его работать. В порядке: 1. мое предложение, 2. Paidric (теперь удалено, но самый изящный), 3. принятый ответ Энди, 4. zip - non numpy, 5. vanilla python без почтового индекса в соответствии с @leekaiinthesky

0.1 мс, 9.6ms, 0.6ms, 2.8ms, 2.3ms

, если преобразование в ndarray включена в timeit то не-NumPy метод NOP-молния является самым быстрым

7.1ms, 17.1ms, 7,7 мс, 2,8 мс, 2,3 мс

и даже больше, если разница между этими двумя списками есть около индекса 1000, а не 10000

7.1ms, 17.1ms, 7.7ms, 0.3ms, 0,2 мс

import timeit 

setup = """ 
import numpy as np 
from itertools import zip_longest 
list1 = [1 for i in range(10000)] + [4, 5, 7] 
list2 = [1 for i in range(10000)] + [4, 4] 
test1 = np.array(list1) 
test2 = np.array(list2) 

def find_first_diff(l1, l2): 
    for index, (x, y) in enumerate(zip_longest(l1, l2, fillvalue=object())): 
     if x != y: 
      return index 

def findFirstDifference(list1, list2): 
    minLength = min(len(list1), len(list2)) 
    for index in range(minLength): 
    if list1[index] != list2[index]: 
     return index 
    return minLength 
""" 

fn = [""" 
n = min(len(test1), len(test2)) 
x = np.where(test1[:n] != test2[:n])[0] 
if len(x) > 0: 
    ans = x[0] 
elif len(test1) != len(test2): 
    ans = n 
else: 
    ans = None""", 
""" 
x = np.where(np.in1d(list1, list2) == False)[0] 
if len(x) > 0: 
    ans = x[0] 
else: 
    ans = None""", 
""" 
x = test1 
y = np.resize(test2, x.shape) 
x = np.where(np.where(x == y, x, 0) == 0)[0] 
if len(x) > 0: 
    ans = x[0] 
else: 
    ans = None""", 
""" 
ans = find_first_diff(list1, list2)""", 
""" 
ans = findFirstDifference(list1, list2)"""] 

for f in fn: 
    print(timeit.timeit(f, setup, number = 1000)) 

Answer 4

Вот так сделать это:

from itertools import izip 
def compare_lists(lista, listb): 
    """ 
    Compare two lists and return the first index where they differ. if 
    they are equal, return the list len 
    """ 
    for position, (a, b) in enumerate(zip(lista, listb)): 
     if a != b: 
      return position 
    return min([len(lista), len(listb)]) 

• алгоритм прост: zip (или в данном случае, более эффективным izip) два списка, а затем сравнить m элемент за элементом.
• eumerate функция дает индекс позиции, которую мы можем вернуться, если несоответствие обнаружено

• Если мы выходим из for петли без каких-либо возвратов, одна из двух возможностей может произойти:

  1. Два списки идентичны. В этом случае мы хотим вернуть длину обоих списков.
  2. Списки различной длины и равны с длине более короткого списка. В этом случае мы хотим вернуть длину более короткого списка

  В эфирных случаях выражение min(...) - это то, что мы хотим.

• Эта функция имеет ошибку: если вы сравниваете два пустых списка, она возвращает 0, что кажется неправильным. Я оставлю это вам, чтобы исправить это как упражнение.

Answer 5

Спасибо за все ваши предложения, я нашел гораздо более простой способ для моей проблемы, которая:

x = numpy.array(test1) 
y = np.resize(numpy.array(test2), x.shape) 
np.where(np.where(x == y, x, 0) == '0')[0][0] 

Answer 6

Вот правда, не очень вещий, NumPy-свободный удар:

b = zip (test1, test2) 
c = 0 
while b:   
    b = b[1:] 
    if not b or b[0][0] != b[0][1]: 
     break 
    else: 
     c = c + 1 
print c 

Answer 7

для Python 3.x:

def first_diff_index(ls1, ls2): 
    l = min(len(ls1), len(ls2)) 
    return next((i for i in range(l) if ls1[i] != ls2[i]), l) 

(для Python 2.7 onwa rds заменить range на xrange)