的Python/numpy的 - 快速查找索引数组中的最近的某个值

我有值，T的阵列，即总是递增次序（但不总是均匀间隔的）。我还有另一个值x。我需要在t中找到索引，使得t [index]最接近x。该函数必须为x < t.min（）返回零，并为x> t.max（）返回最大索引（或-1）。的Python/numpy的 - 快速查找索引数组中的最近的某个值

我已经写了两个函数来做到这一点。第一个，f1，在这个简单的时间测试中更快。但我喜欢第二个只是一条线。这个计算将在一个大阵列上完成，可能每秒多次。

任何人都可以拿出来与可比的时机一些其他的功能，第一，但与清洁寻找代码？第一个速度怎么样（速度是最重要的）？

谢谢！

代码：

import numpy as np 
import timeit 

t = np.arange(10,100000)   # Not always uniform, but in increasing order 
x = np.random.uniform(10,100000) # Some value to find within t 

def f1(t, x): 
    ind = np.searchsorted(t, x) # Get index to preserve order 
    ind = min(len(t)-1, ind)  # In case x > max(t) 
    ind = max(1, ind)    # In case x < min(t) 
    if x < (t[ind-1] + t[ind])/2.0: # Closer to the smaller number 
     ind = ind-1 
    return ind 

def f2(t, x): 
    return np.abs(t-x).argmin() 

print t,   '\n', x,   '\n' 
print f1(t, x), '\n', f2(t, x), '\n' 
print t[f1(t, x)], '\n', t[f2(t, x)], '\n' 

runs = 1000 
time = timeit.Timer('f1(t, x)', 'from __main__ import f1, t, x') 
print round(time.timeit(runs), 6) 

time = timeit.Timer('f2(t, x)', 'from __main__ import f2, t, x') 
print round(time.timeit(runs), 6)

来源

2011-05-19 Scott B

由于您的数组进行排序，尝试二进制搜索。看到这个问题的答案︰http://stackoverflow.com/questions/212358/binary-search-in-python – payne 2011-05-19 23:04:38

我只是离开工作，但想看看这个稍后。我认为，一旦你测试了x max（t），你可能会通过短路改善你的第一个功能，但我还没有机会测试它。 – 2011-05-19 23:05:51

这似乎更快（对我来说，Python的3.2-win32的，numpy的1.6.0慢）：

from bisect import bisect_left 
def f3(t, x): 
    i = bisect_left(t, x) 
    if t[i] - x > 0.5: 
     i-=1 
    return i

输出：

[ 10 11 12 ..., 99997 99998 99999] 
37854.22200356027 
37844 
37844 
37844 
37854 
37854 
37854 
f1 0.332725 
f2 1.387974 
f3 0.085864

来源

2011-05-19 23:57:37 Kabie

雅，快得多。但是，它需要稍微调整，以考虑x t.max的特殊情况 – 2011-05-20 17:42:16

使用searchsorted：

t = np.arange(10,100000)   # Not always uniform, but in increasing order 
x = np.random.uniform(10,100000) 

print t.searchsorted(x)

编辑：

是啊，我看这是你在F1做什么。也许下面的f3比f1更容易阅读。

def f3(t, x): 
    ind = t.searchsorted(x) 
    if ind == len(t): 
     return ind - 1 # x > max(t) 
    elif ind == 0: 
     return 0 
    before = ind-1 
    if x-t[before] < t[ind]-x: 
     ind -= 1 
    return ind

来源

2011-05-19 23:15:41

这只是给出了插入数字的索引，并不一定是最接近的索引。这就是为什么他的F1功能需要额外的步骤。 – Dan 2011-05-19 23:18:45

啊，是的，我没有看到在f1搜索排序。抱歉。 – 2011-05-19 23:29:02

np.searchsorted是二元搜索（每次将数组拆分成一半）。所以你必须以一种方式实现它，它返回的最后一个值小于x而不是返回零。

看看这个算法（从here）：

def binary_search(a, x): 
    lo=0 
    hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     midval = a[mid] 
     if midval < x: 
      lo = mid+1 
     elif midval > x: 
      hi = mid 
     else: 
      return mid 
    return lo-1 if lo > 0 else 0

刚刚更换的最后一行（是return -1）。也改变了论据。

由于回路用Python编写的，它可以是比第一个...（不基准）

来源

2011-05-19 23:42:07 JBernardo

又见[平分模块（http://docs.python.org/library/bisect.html） – RecursivelyIronic 2011-05-19 23:52:12

的Python/numpy的 - 快速查找索引数组中的最近的某个值

回答

相关问题