Numpy: быстро найти первый индекс стоимости

Question

Как найти индекс первого появления числа в массиве Numpy? Скорость важна для меня. Меня не интересуют следующие ответы, потому что они сканируют весь массив и не останавливаются, когда обнаруживают первое вхождение:

itemindex = numpy.where(array==item)[0][0]
nonzero(array == item)[0][0]

Примечание 1: ни один из ответов на этот вопрос не представляется актуальным Существует ли функция Numpy, которая возвращает первый индекс чего-либо в массиве?

Примечание 2: использование скомпилированного метода предпочтительнее цикла Python.

Answer 1

Для Numpy 2.0.0 запланирован запрос функции: https://github.com/numpy/numpy/issues/2269

Answer 2

Хотя это слишком поздно для вас, но для справки в будущем: использование numba ( 1 ) - самый простой способ, пока numpy не реализует его.Если вы используете дистрибутив Python anaconda, он должен быть уже установлен.Код будет скомпилирован, поэтому он будет быстрым.

@jit(nopython=True)
def find_first(item, vec):
    """return the index of the first occurence of item in vec"""
    for i in xrange(len(vec)):
        if item == vec[i]:
            return i
    return -1

, а затем:

>>> a = array([1,7,8,32])
>>> find_first(8,a)
2

Answer 3

Я сделал тест для нескольких методов:

• argwhere
• nonzero как в вопросе
• .tostring() как в ответе @Rob Reilink
• цикл питона
• петля Фортрана

Доступны Python и Fortran . Я пропустил бесперспективные, такие как преобразование в список.

Результаты в логарифмическом масштабе. Ось X - это положение стрелки (требуется больше времени, чтобы определить, находится ли она дальше вниз по массиву); Последнее значение - это игла, которой нет в массиве. Ось Y - это время, чтобы найти его.

Массив содержал 1 миллион элементов, и тесты проводились 100 раз. Результаты все еще немного колеблются, но качественная тенденция ясна: Python и f2py выходят из первого элемента, поэтому они масштабируются по-разному. Python становится слишком медленным, если стрелка находится не в первых 1%, тогда как f2py быстр (но вам нужно его скомпилировать).

Подводя итог, f2py - самое быстрое решение , особенно если игла появляется довольно рано.

Он не встроен, что раздражает, но на самом деле это всего 2 минуты работы. Добавьте this в файл с именем search.f90:

subroutine find_first(needle, haystack, haystack_length, index)
    implicit none
    integer, intent(in) :: needle
    integer, intent(in) :: haystack_length
    integer, intent(in), dimension(haystack_length) :: haystack
!f2py intent(inplace) haystack
    integer, intent(out) :: index
    integer :: k
    index = -1
    do k = 1, haystack_length
        if (haystack(k)==needle) then
            index = k - 1
            exit
        endif
    enddo
end

Если вы ищете что-то отличное от integer, просто измените тип. Затем скомпилируйте, используя:

f2py -c -m search search.f90

после чего вы можете сделать (из Python):

import search
print(search.find_first.__doc__)
a = search.find_first(your_int_needle, your_int_array)

Answer 4

Вы можете преобразовать логический массив в строку Python, используя array.tostring(), а затем используя метод find ():

(array==item).tostring().find('\x01')

Однако это включает в себя копирование данных, поскольку строки Python должны быть неизменяемыми. Преимущество состоит в том, что вы также можете искать, например, передний край, найдя \x00\x01

Answer 5

В случае отсортированных массивов np.searchsorted работает.

Answer 6

Я думаю, что вы столкнулись с проблемой, когда другой метод и некоторое априорное знание массива действительно помогло бы. То, где у вас есть вероятность X найти ваш ответ в первых Y процентах данных. Разделить проблему с надеждой на то, что вам повезет, и затем сделать это на python с пониманием вложенного списка или чем-то еще.

Написание функции C для этой грубой силы тоже не сложно, используя ctypes .

Код C, который я взломал вместе (index.c):

long index(long val, long *data, long length){
    long ans, i;
    for(i=0;i<length;i++){
        if (data[i] == val)
            return(i);
    }
    return(-999);
}

и питон:

# to compile (mac)
# gcc -shared index.c -o index.dylib
import ctypes
lib = ctypes.CDLL('index.dylib')
lib.index.restype = ctypes.c_long
lib.index.argtypes = (ctypes.c_long, ctypes.POINTER(ctypes.c_long), ctypes.c_long)

import numpy as np
np.random.seed(8675309)
a = np.random.random_integers(0, 100, 10000)
print lib.index(57, a.ctypes.data_as(ctypes.POINTER(ctypes.c_long)), len(a))

и я получаю 92.

Заверните питона в нужную функцию, и все.

Версия C намного (в 20 раз) быстрее для этого семени (предупреждение, что я не очень хорошо с этим)

import timeit
t = timeit.Timer('np.where(a==57)[0][0]', 'import numpy as np; np.random.seed(1); a = np.random.random_integers(0, 1000000, 10000000)')
t.timeit(100)/100
# 0.09761879920959472
t2 = timeit.Timer('lib.index(57, a.ctypes.data_as(ctypes.POINTER(ctypes.c_long)), len(a))', 'import numpy as np; np.random.seed(1); a = np.random.random_integers(0, 1000000, 10000000); import ctypes; lib = ctypes.CDLL("index.dylib"); lib.index.restype = ctypes.c_long; lib.index.argtypes = (ctypes.c_long, ctypes.POINTER(ctypes.c_long), ctypes.c_long) ')
t2.timeit(100)/100
# 0.005288000106811523

Answer 7

@ tal уже представил функцию numba для поиска первого индекса, но она работает только для одномерных массивов. С np.ndenumerate вы также можете найти первый индекс в массиве произвольной размерности:

from numba import njit
import numpy as np

@njit
def index(array, item):
    for idx, val in np.ndenumerate(array):
        if val == item:
            return idx
    return None

Пример дела:

>>> arr = np.arange(9).reshape(3,3)
>>> index(arr, 3)
(1, 0)

Время показывает, что по производительности оно похоже на решение tals :

arr = np.arange(100000)
%timeit index(arr, 5)           # 1000000 loops, best of 3: 1.88 µs per loop
%timeit find_first(5, arr)      # 1000000 loops, best of 3: 1.7 µs per loop

%timeit index(arr, 99999)       # 10000 loops, best of 3: 118 µs per loop
%timeit find_first(99999, arr)  # 10000 loops, best of 3: 96 µs per loop

Answer 8

Если ваш список отсортирован , вы можете очень быстро выполнить поиск по индексу с помощью пакета 'bisect'.Это O (log (n)) вместо O (n).

bisect.bisect(a, x)

находит x в массиве a, определенно быстрее в отсортированном случае, чем любая подпрограмма C, проходящая через все первые элементы (длядостаточно длинные списки).

Приятно знать иногда.

Answer 9

Как давний пользователь Matlab, я довольно долго искал эффективное решение этой проблемы.Наконец, мотивировано обсуждением предложений в этой теме . Я попытался найти решение, которое реализует API, аналогичный тому, который был предложен здесь , на данный момент поддерживая только одномерные массивы.,

Вы могли бы использовать его следующим образом

import numpy as np
import utils_find_1st as utf1st
array = np.arange(100000)
item = 1000
ind = utf1st.find_1st(array, item, utf1st.cmp_larger_eq)

Поддерживаемые операторы условия: cmp_equal, cmp_not_equal, cmp_larger, cmp_smaller, cmp_larger_eq, cmp_smaller_eq.Для эффективности расширение написано в c.

Вы найдете источник, тесты и другие детали здесь:

https://pypi.python.org/pypi?name=py_find_1st&:action=display

для использования в нашей команде (anaconda onLinux и MacOS) Я сделал установщик Anaconda, который упрощает установку, вы можете использовать его, как описано здесь

https://anaconda.org/roebel/py_find_1st

Answer 10

Мне это нужно было для моей работы, поэтому я изучил интерфейс Python и C Numpy и написал свой собственный.http://pastebin.com/GtcXuLyd Это только для одномерных массивов, но работает для большинства типов данных (int, float или strings), и тестирование показало, что он снова примерно в 20 раз быстрее, чем ожидаемый подход в чистом Python-numpy.