快速找到最接近某个值的数组中的索引 [英] Quickly Find the Index in an Array Closest to Some Value

问题描述

我有一个值数组t，该值始终按升序排列(但不总是均匀间隔).我还有另一个值x.我需要在t中找到索引，以使t [index]最接近x.对于x ＜，该函数必须返回零. t.min()和x> t.max()的最大索引(或-1).

I have an array of values, t, that is always in increasing order (but not always uniformly spaced). I have another single value, x. I need to find the index in t such that t[index] is closest to x. The function must return zero for x < t.min() and the max index (or -1) for x > t.max().

我已经写了两个函数来做到这一点.在这个简单的时序测试中，第一个f1更快.但是我喜欢第二个只是一行.此计算将在大型阵列上进行，每秒可能多次.

I've written two functions to do this. The first one, f1, is MUCH quicker in this simple timing test. But I like how the second one is just one line. This calculation will be done on a large array, potentially many times per second.

任何人都可以提出其他功能，但时序与第一个功能相近，但代码看起来更简洁吗?比第一个更快(速度是最重要的)怎么样?

Can anyone come up with some other function with comparable timing to the first but with cleaner looking code? How about something quicker then the first (speed is most important)?

谢谢！

代码:

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)

推荐答案

这似乎要快得多(对我来说，Python 3.2-win32，numpy 1.6.0):

This seems much quicker (for me, 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

---

输出:

---

Output:

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

这篇关于快速找到最接近某个值的数组中的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！