Numpy:快速找到第一个价值指数

Question

如何找到Numpy数组中第一次出现数字的索引？速度对我很重要.我对以下答案不感兴趣,因为他们扫描整个数组并且在第一次出现时不停止:

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

注1:该问题的答案似乎没有任何问题是否有Numpy函数返回数组中某些内容的第一个索引？

注2:使用C编译方法比Python循环更受欢迎.

Answer 1

Numpy 2.0.0有一个功能请求:https://github.com/numpy/numpy/issues/2269

Answer 2

虽然对你来说太晚了,但是为了将来的参考:使用numba(1)是numpy实现它之前最简单的方法.如果你使用anaconda python发行版,它应该已经安装.代码将被编译,因此速度很快.

@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循环

在Python中和的Fortran代码是可用的.我跳过了没有希望的人,比如转换成一个列表.

对数比例的结果.X轴是针的位置(如果它在阵列的下方,则需要更长的时间); 最后一个值是一个不在数组中的针.Y轴是找到它的时间.

阵列有100万个元素,测试运行100次.结果仍然有点波动,但定性趋势很明显:Python和f2py退出第一个元素,因此它们的扩展方式不同.如果针不在前1%中,Python变得太慢,而f2py快速(但是你需要编译它).

总而言之,f2py是最快的解决方案,特别是如果针很早出现.

它不是内置的烦人,但它只是2分钟的工作.添加这个到一个名为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

您可以使用array.tostring()然后使用find()方法将布尔数组转换为Python字符串:

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

但这确实涉及复制数据,因为Python字符串需要是不可变的.一个优点是您还可以通过查找来搜索例如上升沿\x00\x01

Answer 5

在排序数组的情况下np.searchsorted工作.

Answer 6

如果您正在寻找第一个非零元素，您可以使用以下技巧：

idx = x.view(bool).argmax() // x.itemsize
idx = idx if x[idx] else -1

这是一个非常快速的“numpy-pure”解决方案，但在下面讨论的某些情况下它失败了。

该解决方案利用了几乎所有数字类型的零表示都由0字节组成的事实。它也适用于 numpy 的bool。在 numpy 的最新版本中，argmax()函数在处理bool类型时使用短路逻辑。的大小bool为 1 个字节。

所以一个人需要：

• 创建数组的视图为bool。没有创建副本
• 用于argmax()使用短路逻辑查找第一个非零字节
• 将此字节的偏移量重新计算为第一个非零元素的索引，通过//偏移量的整数除法（运算符）除以以字节（x.itemsize）表示的单个元素的大小
• 检查是否x[idx]实际上是非零以识别不存在非零的情况

我已经针对 numba 解决方案做了一些基准测试并构建它np.nonzero。

import numpy as np
from numba import jit
from timeit import timeit

def find_first(x):
    idx = x.view(bool).argmax() // x.itemsize
    return idx if x[idx] else -1

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


SIZE = 10_000_000
# First only
x = np.empty(SIZE)

find_first_numba(x[:10])

print('---- FIRST ----')
x[:] = 0
x[0] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=1000), 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=1000), 'ms')

print('---- LAST ----')
x[:] = 0
x[-1] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- NONE ----')
x[:] = 0
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- ALL ----')
x[:] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

我机器上的结果是：

---- FIRST ----
ndarray.nonzero 57.63976670001284 ms
find_first 0.0010841979965334758 ms
find_first_numba 0.0002308919938514009 ms
---- LAST ----
ndarray.nonzero 58.96685277999495 ms
find_first 5.923203580023255 ms
find_first_numba 8.762269750004634 ms
---- NONE ----
ndarray.nonzero 25.13398071998381 ms
find_first 5.924289370013867 ms
find_first_numba 8.810063839919167 ms
---- ALL ----
ndarray.nonzero 55.181210660084616 ms
find_first 0.001246920000994578 ms
find_first_numba 0.00028766007744707167 ms

该解决方案比 numba快33%，并且它是“numpy-pure”。

缺点：

• 不适用于 numpy 可接受的类型，例如 object
• 偶尔出现在float或double计算中的负零失败

Answer 7

我认为你遇到了一个问题,其中一个不同的方法和一些先验的数组知识真的会有所帮助.在Y%的数据中你有X概率找到答案的事情.分解问题的希望是幸运,然后在python中使用嵌套列表理解或其他东西.

使用ctypes写一个C函数来做这个暴力也不是太难.

我一起攻击的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);
}

和python:

# 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

把python包装成一个合适的函数然后你就去了.

对于这个种子,C版本的速度要快很多(约20倍)(警告我对timeit不好)

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 8

@tal 已经提供了一个numba函数来查找第一个索引，但仅适用于一维数组。随着np.ndenumerate你也可以找到在arbitarly维数组的第一个索引：

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 9

这个问题可以在纯 numpy 中通过分块处理数组来有效解决：

def find_first(x):
    idx, step = 0, 32
    while idx < x.size:
        nz, = x[idx: idx + step].nonzero()
        if len(nz): # found non-zero, return it
            return nz[0] + idx
        # move to the next chunk, increase step
        idx += step
        step = min(9600, step + step // 2)
    return -1

该数组以 size 的块进行处理step。step步骤越长，归零数组的处理速度越快（最坏情况）。它越小，处理开头非零的数组的速度越快。诀窍是从小处开始step，然后以指数方式增加。此外，由于好处有限，没有必要将其增加到某个阈值以上。

我将该解决方案与纯 ndarary.nonzero 和 numba 解决方案与 1000 万个浮点数组进行了比较。

import numpy as np
from numba import jit
from timeit import timeit

def find_first(x):
    idx, step = 0, 32
    while idx < x.size:
        nz, = x[idx: idx + step].nonzero()
        if len(nz):
            return nz[0] + idx
        idx += step
        step = min(9600, step + step // 2)
    return -1

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


SIZE = 10_000_000
# First only
x = np.empty(SIZE)

find_first_numba(x[:10])

print('---- FIRST ----')
x[:] = 0
x[0] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=1000), 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=1000), 'ms')

print('---- LAST ----')
x[:] = 0
x[-1] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- NONE ----')
x[:] = 0
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- ALL ----')
x[:] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

我的机器上的结果：

---- FIRST ----
ndarray.nonzero 54.733994480002366 ms
find_first 0.0013148509997336078 ms
find_first_numba 0.0002839310000126716 ms
---- LAST ----
ndarray.nonzero 54.56336712999928 ms
find_first 25.38929685000312 ms
find_first_numba 8.022820680002951 ms
---- NONE ----
ndarray.nonzero 24.13432420999925 ms
find_first 25.345200140000088 ms
find_first_numba 8.154927100003988 ms
---- ALL ----
ndarray.nonzero 55.753537260002304 ms
find_first 0.0014760300018679118 ms
find_first_numba 0.0004358099977253005 ms

纯粹ndarray.nonzero肯定是更宽松。在最佳情况下，numba 解决方案的速度大约快 5 倍。在最坏的情况下，速度大约快 3 倍。