Проверка того, содержит ли массив Numpy заданную строку

Существует ли Pythonic и эффективный способ проверить, содержит ли массив Numpy хотя бы один экземпляр данной строки? "Эффективным" я подразумеваю, что он заканчивает поиск первой совпадающей строки, а не итерации по всему массиву, даже если результат уже найден.

С массивами Python это можно выполнить очень чисто с помощью if row in array:, но это не работает так, как я ожидал бы для массивов Numpy, как показано ниже.

С массивами Python:

>>> a = [[1,2],[10,20],[100,200]]
>>> [1,2] in a
True
>>> [1,20] in a
False

но массивы Numpy дают разные и довольно странные результаты. (Метод __contains__ ndarray кажется недокументированным.)

>>> a = np.array([[1,2],[10,20],[100,200]])
>>> np.array([1,2]) in a
True
>>> np.array([1,20]) in a
True
>>> np.array([1,42]) in a
True
>>> np.array([42,1]) in a
False

Ответ 1

Numpys __contains__ есть на момент написания этого (a == b).any(), который, возможно, справедлив только в том случае, если b является скалярный (немного волосатый, но я считаю, что это работает только в 1.7 или более позднем - это будет правильный общий метод (a == b).all(np.arange(a.ndim - b.ndim, a.ndim)).any(), что имеет смысл для всех комбинаций размерности a и b)...

EDIT: просто чтобы быть ясным, это не обязательно ожидаемый результат при трансляции. Также кто-то может утверждать, что он должен обрабатывать элементы в a отдельно, как это делает np.in1d. Я не уверен, что есть один четкий способ, которым он должен работать.

Теперь вы хотите, чтобы numpy остановился, когда обнаружил первое вхождение. В настоящее время этого AFAIK не существует. Это сложно, потому что numpy основан в основном на ufuncs, которые делают то же самое по всему массиву. Numpy оптимизирует эти сокращения, но эффективно работает только тогда, когда уменьшенный массив уже является булевым массивом (т.е. np.ones(10, dtype=bool).any()).

В противном случае для __contains__, которая не существует, потребуется специальная функция. Это может показаться странным, но вы должны помнить, что numpy поддерживает многие типы данных и имеет более крупный механизм для выбора правильных и выбора правильной функции для работы над ним. Другими словами, механизм ufunc не может этого сделать, и реализация __contains__ или такая особенность на самом деле не является тривиальной из-за типов данных.

Вы можете, конечно, написать его в python, или, поскольку вы, вероятно, знаете свой тип данных, писать его сами в Cython/C очень просто.

Это сказало. Часто гораздо лучше использовать подход, основанный на сортировке для этих вещей. Это немного утомительно, так как нет searchsorted для lexsort, но он работает (вы также можете злоупотреблять scipy.spatial.cKDTree, если хотите). Предполагается, что вы хотите сравнить только по последней оси:

# Unfortunatly you need to use structured arrays:
sorted = np.ascontiguousarray(a).view([('', a.dtype)] * a.shape[-1]).ravel()

# Actually at this point, you can also use np.in1d, if you already have many b
# then that is even better.

sorted.sort()

b_comp = np.ascontiguousarray(b).view(sorted.dtype)
ind = sorted.searchsorted(b_comp)

result = sorted[ind] == b_comp

Это также работает для массива b, и если вы сохраняете отсортированный массив вокруг, также намного лучше, если вы делаете это для одного значения (строки) в b за раз, когда a остается то же самое (иначе я бы просто np.in1d после просмотра его как повторения). Важно: вы должны сделать np.ascontiguousarray для обеспечения безопасности. Обычно он ничего не делает, но если это произойдет, это будет большой потенциальной ошибкой в противном случае.

Ответ 2

Вы можете использовать .tolist()

>>> a = np.array([[1,2],[10,20],[100,200]])
>>> [1,2] in a.tolist()
True
>>> [1,20] in a.tolist()
False
>>> [1,20] in a.tolist()
False
>>> [1,42] in a.tolist()
False
>>> [42,1] in a.tolist()
False

Или используйте представление:

>>> any((a[:]==[1,2]).all(1))
True
>>> any((a[:]==[1,20]).all(1))
False

Или сгенерируйте список numpy (возможно, ОЧЕНЬ МЕДЛЕННО):

any(([1,2] == x).all() for x in a)     # stops on first occurrence

Или используйте логические функции numpy:

any(np.equal(a,[1,2]).all(1))

Если у вас есть время:

import numpy as np
import time

n=300000
a=np.arange(n*3).reshape(n,3)
b=a.tolist()

t1,t2,t3=a[n//100][0],a[n//2][0],a[-10][0]

tests=[ ('early hit',[t1, t1+1, t1+2]),
        ('middle hit',[t2,t2+1,t2+2]),
        ('late hit', [t3,t3+1,t3+2]),
        ('miss',[0,2,0])]

fmt='\t{:20}{:.5f} seconds and is {}'     

for test, tgt in tests:
    print('\n{}: {} in {:,} elements:'.format(test,tgt,n))

    name='view'
    t1=time.time()
    result=(a[...]==tgt).all(1).any()
    t2=time.time()
    print(fmt.format(name,t2-t1,result))

    name='python list'
    t1=time.time()
    result = True if tgt in b else False
    t2=time.time()
    print(fmt.format(name,t2-t1,result))

    name='gen over numpy'
    t1=time.time()
    result=any((tgt == x).all() for x in a)
    t2=time.time()
    print(fmt.format(name,t2-t1,result))

    name='logic equal'
    t1=time.time()
    np.equal(a,tgt).all(1).any()
    t2=time.time()
    print(fmt.format(name,t2-t1,result))

Вы можете видеть, что ударить или пропустить, процедуры numpy имеют одинаковую скорость поиска массива. Оператор Python in потенциально намного быстрее для раннего попадания, а генератор - просто плохая новость, если вам нужно пройти весь путь через массив.

Ниже приведены результаты для массива элементов размером 300 000 x 3:

early hit: [9000, 9001, 9002] in 300,000 elements:
    view                0.01002 seconds and is True
    python list         0.00305 seconds and is True
    gen over numpy      0.06470 seconds and is True
    logic equal         0.00909 seconds and is True

middle hit: [450000, 450001, 450002] in 300,000 elements:
    view                0.00915 seconds and is True
    python list         0.15458 seconds and is True
    gen over numpy      3.24386 seconds and is True
    logic equal         0.00937 seconds and is True

late hit: [899970, 899971, 899972] in 300,000 elements:
    view                0.00936 seconds and is True
    python list         0.30604 seconds and is True
    gen over numpy      6.47660 seconds and is True
    logic equal         0.00965 seconds and is True

miss: [0, 2, 0] in 300,000 elements:
    view                0.00936 seconds and is False
    python list         0.01287 seconds and is False
    gen over numpy      6.49190 seconds and is False
    logic equal         0.00965 seconds and is False

И для массива 3 000 000 x 3:

early hit: [90000, 90001, 90002] in 3,000,000 elements:
    view                0.10128 seconds and is True
    python list         0.02982 seconds and is True
    gen over numpy      0.66057 seconds and is True
    logic equal         0.09128 seconds and is True

middle hit: [4500000, 4500001, 4500002] in 3,000,000 elements:
    view                0.09331 seconds and is True
    python list         1.48180 seconds and is True
    gen over numpy      32.69874 seconds and is True
    logic equal         0.09438 seconds and is True

late hit: [8999970, 8999971, 8999972] in 3,000,000 elements:
    view                0.09868 seconds and is True
    python list         3.01236 seconds and is True
    gen over numpy      65.15087 seconds and is True
    logic equal         0.09591 seconds and is True

miss: [0, 2, 0] in 3,000,000 elements:
    view                0.09588 seconds and is False
    python list         0.12904 seconds and is False
    gen over numpy      64.46789 seconds and is False
    logic equal         0.09671 seconds and is False

Что, по-видимому, указывает, что np.equal является самым быстрым способом с чистым numpy для этого...

Ответ 3

Я думаю,

equal([1,2], a).all(axis=1)   # also,  ([1,2]==a).all(axis=1)
# array([ True, False, False], dtype=bool)

отобразит строки, которые соответствуют. Как указывает Джейми, чтобы узнать, существует ли хотя бы одна такая строка, используйте any:

equal([1,2], a).all(axis=1).any()
# True

Помимо этого:
Я подозреваю, что in (и __contains__) как указано выше, но использует any вместо all.

Ответ 4

Если вы действительно хотите остановиться в первом вхождении, вы можете написать цикл, например:

import numpy as np

needle = np.array([10, 20])
haystack = np.array([[1,2],[10,20],[100,200]])
found = False
for row in haystack:
    if np.all(row == needle):
        found = True
        break
print("Found: ", found)

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