向量中元素之間的最小距離

Question

我需要數組元素之間的最小距離。

我所做的：

numpy.min(numpy.ediff1d(numpy.sort(x))) 

是否有更好/更高效/更優雅/快這樣的方式？

Answer 1

如果你是純粹的速度之後，這裏有一些計時：

In [13]: a = np.random.rand(1000) 

In [14]: %timeit np.sort(a) 
10000 loops, best of 3: 31.9 us per loop 

In [15]: %timeit np.ediff1d(a) 
100000 loops, best of 3: 15.2 us per loop 

In [16]: %timeit np.diff(a) 
100000 loops, best of 3: 7.76 us per loop 

In [17]: %timeit np.min(a) 
100000 loops, best of 3: 3.19 us per loop 

In [18]: %timeit np.unique(a) 
10000 loops, best of 3: 53.8 us per loop 

的unique的時機，希望它會比較快到sort，並且如果獨特陣列的長度沒有調用diff和min，您可能會提前中斷比陣列本身短（因爲這意味着你的答案是0）。但unique的開銷超過了任何收益。

所以看起來我能夠提供的唯一潛在的改進與diff更換ediff1d：

In [19]: %timeit np.min(np.diff(np.sort(a))) 
10000 loops, best of 3: 47.7 us per loop 

In [20]: %timeit np.min(np.ediff1d(np.sort(a))) 
10000 loops, best of 3: 57.1 us per loop 

Answer 2

您目前的做法絕對是最佳的。通過首先排序，可以減少每個元素之間的空間，並且ediff1d將返回差異數組。以下是一個建議：

由於我們知道差別必須是正數，因爲我們有升序排序，所以我們可以手動執行ediff1d並在差異爲零時包含中斷。這樣一來，如果你有數組排序x：

[1, 1, 2, 3, 4, 5, 6, 7, ... , n]

而不是通過n個元素去，你ediff1d功能早期斷裂和僅覆蓋了前兩個元素，返回[0]。這也減小了差異數組的大小，從而減少了您的min調用所需的迭代次數。

這裏是無需使用numpy的示例：

x = [1, 12, 3, 8, 4, 1, 4, 9, 1, 29, 210, 313, 12] 

def ediff1d_custom(x): 
    darr = [] 

    for i in xrange(len(x)): 
     if i != len(x) - 1: 
      diff = x[i + 1] - x[i] 
      darr.append(diff) 

      if diff == 0: 
       break 

    return darr 

print min(ediff1d_custom(sorted(x))) # prints 0 

Answer 3

try: 
    min(x[i+1]-x[i] for i in xrange(0, len(x)-1)) 
except ValueError: 
    print 'Array contains less than two values.'