首页 文章

Numpy:快速找到第一个 Value 指数

提问于
浏览
88

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

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

注1:该问题的答案似乎都没有相关Is there a Numpy function to return the first index of something in an array?

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

14 回答

  • 2

    此计划为Numpy 2.0.0提供了一项功能请求:https://github.com/numpy/numpy/issues/2269

  • 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
    
  • 9

    我已经为几种方法制定了基准:

    • argwhere

    • nonzero 在问题中

    • .tostring() ,如@Rob Reilink的回答

    • python循环

    • Fortran循环

    PythonFortran代码可用 . 我跳过了没有希望的人,比如转换成一个列表 .

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

    benchmark results

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

    总而言之, f2py is the fastest solution ,特别是如果针出现得相当早 .

    它真的只需要2分钟的工作时间.2563699_将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)
    
  • 7

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

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

    但这确实涉及复制数据,因为Python字符串需要是不可变的 . 一个优点是你也可以搜索例如找到 \x00\x01 的上升趋势

  • 11

    如果是排序数组 np.searchsorted 有效 .

  • 1

    我认为你遇到了一个问题,其中一个不同的方法和一些先验的数组知识真的会有所帮助 . 在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
    
  • 25

    如果您的列表是 sorted ,则可以使用'bisect'包实现 very quick 索引搜索 . 它是O(log(n))而不是O(n) .

    bisect.bisect(a, x)
    

    在数组a中找到x,在排序的情况下肯定比通过所有第一个元素的任何C例程(对于足够长的列表)更快 .

    有时候知道这很好 .

  • 0

    @tal已经提供了一个 numba 函数来查找第一个索引,但这只适用于1D数组 . 使用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)
    

    Timings表明它的性能与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
    
  • -1

    据我所知,只有布尔数组上的np.any和np.all被短路 .

    在你的情况下,numpy必须遍历整个数组两次,一次创建布尔条件,第二次查找索引 .

    在这种情况下我的建议是使用cython . 我认为在这种情况下调整示例应该很容易,特别是如果您不需要为不同的dtypes和形状提供太多灵活性 .

  • 1

    我需要这个来完成我的工作所以我自学了Python和Numpy的C界面并编写了我自己的 . http://pastebin.com/GtcXuLyd它仅适用于1-D数组,但适用于大多数数据类型(int,float或字符串),测试表明它再次比纯Python-numpy中的预期方法快20倍 .

  • 47

    请注意,如果你正在做一个如果搜索维度不够大,搜索序列,从做一些聪明的事情(如转换为字符串)中获得的性能提升可能会在外部循环中丢失 . 看看迭代find1的性能如何使用上面提出的字符串转换技巧和find2沿内轴使用argmax(加上调整以确保不匹配返回为-1)

    import numpy,time
    def find1(arr,value):
        return (arr==value).tostring().find('\x01')
    
    def find2(arr,value): #find value over inner most axis, and return array of indices to the match
        b = arr==value
        return b.argmax(axis=-1) - ~(b.any())
    
    
    for size in [(1,100000000),(10000,10000),(1000000,100),(10000000,10)]:
        print(size)
        values = numpy.random.choice([0,0,0,0,0,0,0,1],size=size)
        v = values>0
    
        t=time.time()
        numpy.apply_along_axis(find1,-1,v,1)
        print('find1',time.time()-t)
    
        t=time.time()
        find2(v,1)
        print('find2',time.time()-t)
    

    输出

    (1, 100000000)
    ('find1', 0.25300002098083496)
    ('find2', 0.2780001163482666)
    (10000, 10000)
    ('find1', 0.46200013160705566)
    ('find2', 0.27300000190734863)
    (1000000, 100)
    ('find1', 20.98099994659424)
    ('find2', 0.3040001392364502)
    (10000000, 10)
    ('find1', 206.7590000629425)
    ('find2', 0.4830000400543213)
    

    也就是说,用C语言编写的查找至少比这些方法中的任何一种快一点

  • 0

    这个怎么样

    import numpy as np
    np.amin(np.where(array==item))
    
  • 0

    作为一个长期的matlab用户,我一直在寻找有效解决这个问题的方法 . 最后,通过讨论讨论了这个问题,我试图提出一个解决方案,即实现类似于建议的here的API,目前仅支持1D阵列 . 为了提高效率,扩展名用C语言编写,因此应该相当有效 .

    您可以在此处找到来源,基准和其他详细信息:

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

    在我们的团队中使用(在linux和macos上使用anaconda)我已经制作了一个简化安装的anaconda安装程序,你可以按照此处的描述使用它

    https://anaconda.org/roebel/py_find_1st

  • 16

    您可以将数组转换为 list 并使用它的 index() 方法:

    i = list(array).index(item)
    

    据我所知,这是一个C编译方法 .

相关问题