Почему python `in` намного быстрее, чем` np.isin`

Question

Я реализую некоторый алгоритм поиска, используя numpy, где один шаг - проверить, находится ли вектор в матрице (в виде строки).Раньше я использовал np.isin, но мне вдруг стало интересно, сработает ли ключевое слово python in.Поэтому я протестировал его и обнаружил, что он работает.

Поскольку я не нашел ни одного интерфейса Python для in (например, __add__ для + или __abs__ для abs), я считаю,in встроен в python с использованием стандартной логики итераторов, поэтому он должен быть медленнее по сравнению с numpy -обеспеченным np.isin.Но после того, как я провел некоторое тестирование, невероятно:

>>> a = np.int8(1)
>>> A = np.zeros(2**24, 'b')
>>> %timeit a in A
>>> %timeit np.isin(a, A)
21.7 ms ± 1.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
310 ms ± 20.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

, то есть np.isin в 10+ раз медленнее, чем python in для небольших типов данных.Я также провел тест для большого типа данных

>>> a = np.ones(1, 'V256')
>>> A = np.zeros(2**22, 'V256')
>>> %timeit a in A
>>> %timeit np.isin(a, A)
129 ms ± 12.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
10.5 s ± 184 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

, который говорит, что np.isin примерно в 100 раз медленнее.

Мне интересно, что может быть причиной этого.Обратите внимание, что с a=1, а A=[0,0,...], сопоставление должно быть выполнено для всего массива.На стороне питона нет такого понятия, как «ранний выход».

EDIT О, на самом деле есть интерфейс Python для in, называемый __contains__.Но все же, почему np.isin будет намного медленнее, чем np.ndarray.__contains__?

Answer 1

numpy.ndarray.__contains__ в основном просто (elem == arr).any() (даже если это не имеет смысла).Вы можете взглянуть на источник , который очень короткий и простой для подпрограммы NumPy C.

numpy.isin передает по левому операнду, и он оптимизирован для эффективности вещаниядело.Для небольшого левого операнда он будет использовать подход, основанный на сортировке , что является избыточным для скаляра.В настоящее время нет быстрого пути для левого операнда, являющегося скаляром, или для левой руки, являющейся массивом, достаточно маленьким, чтобы сортировка была более дорогой, чем наивный подход.

Answer 2

Мой ответ не такой, как просили.Может быть, дать вам некоторую идею.Как правило, главная идея получения хороших результатов от NumPy заключается в том, чтобы амортизировать стоимость переводчика по многим элементам одновременно.Другими словами, переместите циклы из кода Python (медленно) в циклы C / Fortran где-нибудь в numpy / BLAS / LAPACK / и т.д.внутренние органы (быстро).Если вы преуспеете в этой операции (так называемой векторизации), производительность, как правило, будет довольно хорошей.

Конечно, вы, безусловно, можете добиться еще большей производительности, выгрузив интерпретатор python и используя вместо этого, скажем, C ++.Будет ли этот подход успешным или нет, зависит от того, насколько вы хороши в высокопроизводительном программировании на C ++, а не от numpy, и от того, какую именно операцию вы пытаетесь выполнить.