Wie finde ich das längste Sub-Array innerhalb eines Schwellenwerts?

Question

Angenommen, Sie haben ein sortiertes Zahlenfeld sorted_array und einen Schwellenwert threshold. Was ist der schnellste Weg, das längste Unterfeld zu finden, in dem alle Werte innerhalb des Grenzwerts liegen? Mit anderen Worten, finden Indizes i und j, so dass:

1. sorted_array[j] - sorted_array[i] <= threshold
2. j - i maximal ist

Im Falle eines Unentschiedens, bringen Sie das Paar mit dem kleinsten i.

Ich habe bereits eine Schleife-basierte Lösung, die ich als Antwort posten werde, aber ich bin gespannt, ob es einen besseren Weg gibt, oder eine Möglichkeit, die Schleife mit einer Vektor-fähigen Sprache oder Bibliothek zu vermeiden wie zum Beispiel NumPy.

Beispiel Ein- und Ausgang:

>>> sorted_array = [0, 0.7, 1, 2, 2.5] 
>>> longest_subarray_within_threshold(sorted_array, 0.2) 
(0, 0) 
>>> longest_subarray_within_threshold(sorted_array, 0.4) 
(1, 2) 
>>> longest_subarray_within_threshold(sorted_array, 0.8) 
(0, 1) 
>>> longest_subarray_within_threshold(sorted_array, 1) 
(0, 2) 
>>> longest_subarray_within_threshold(sorted_array, 1.9) 
(1, 4) 
>>> longest_subarray_within_threshold(sorted_array, 2) 
(0, 3) 
>>> longest_subarray_within_threshold(sorted_array, 2.6) 
(0, 4) 

Answer 1

Höchstwahrscheinlich ist die eigene Antwort des OP der bestmögliche Algorithmus, da es O (n) ist. Der pure-python-Overhead macht es jedoch sehr langsam. Dieser Overhead kann jedoch leicht reduziert werden, indem der Algorithmus unter Verwendung von numba kompiliert wird, mit der aktuellen Version (0.28.1 zu diesem Schreiben), gibt es keine Notwendigkeit für eine manuelle Eingabe, einfach dekorieren Sie Ihre Funktion mit @numba.njit() ist genug.

Allerdings, wenn Sie es verlassen wollen, ist nicht auf numba, ein numpy Algorithmus in O (n log n):

def algo_burnpanck(sorted_array,thresh): 
    limit = np.searchsorted(sorted_array,sorted_array+thresh,'right') 
    distance = limit - np.arange(limit.size) 
    best = np.argmax(distance) 
    return best, limit[best]-1 

ich eine schnelle Profilierung auf meinem eigenen Rechner der beiden vorherigen lief Antworten (OPs und Divakars), sowie mein numpiger Algorithmus und die numba-Version des OP-Algorithmus.

thresh = 1 
for n in [100, 10000]: 
    sorted_array = np.sort(np.random.randn(n,)) 
    for f in [algo_user1475412,algo_Divakar,algo_burnpanck,algo_user1475412_numba]: 
     a,b = f(sorted_array, thresh) 
     d = b-a 
     diff = sorted_array[b]-sorted_array[a] 
     closestlonger = np.min(sorted_array[d+1:]-sorted_array[:-d-1]) 
     assert sorted_array[b]-sorted_array[a]<=thresh 
     assert closestlonger>thresh 
     print('f=%s, n=%d thresh=%s:'%(f.__name__,n,thresh))#,d,a,b,diff,closestlonger) 
     %timeit f(sorted_array, thresh) 

Hier sind die Ergebnisse:

f=algo_user1475412, n=100 thresh=1: 
10000 loops, best of 3: 111 µs per loop 
f=algo_Divakar, n=100 thresh=1: 
10000 loops, best of 3: 74.6 µs per loop 
f=algo_burnpanck, n=100 thresh=1: 
100000 loops, best of 3: 9.38 µs per loop 
f=algo_user1475412_numba, n=100 thresh=1: 
1000000 loops, best of 3: 764 ns per loop 
f=algo_user1475412, n=10000 thresh=1: 
100 loops, best of 3: 12.1 ms per loop 
f=algo_Divakar, n=10000 thresh=1: 
1 loop, best of 3: 1.76 s per loop 
f=algo_burnpanck, n=10000 thresh=1: 
1000 loops, best of 3: 308 µs per loop 
f=algo_user1475412_numba, n=10000 thresh=1: 
10000 loops, best of 3: 82.9 µs per loop 

Bei 100 Zahlen, O (n^2) Lösung gerade noch schlägt das O mit numpy (n) Python-Lösung, aber schnell nach, macht die Skalierung dieser Algorithmus nutzlos. Das O (n log n) hält sogar bei 10000 Zahlen an, aber der Ansatz von numba ist überall ungeschlagen.

Answer 2

Hier ist eine einfache Loop-basierte Lösung in Python:

def longest_subarray_within_threshold(sorted_array, threshold): 
    result = (0, 0) 
    longest = 0 
    i = j = 0 
    end = len(sorted_array) 
    while i < end: 
     if j < end and sorted_array[j] - sorted_array[i] <= threshold: 
      current_distance = j - i 
      if current_distance > longest: 
       longest = current_distance 
       result = (i, j) 
      j += 1 
     else: 
      i += 1 
    return result 

Answer 3

Hier ist ein vektorisiert Ansatz broadcasting mit -

def longest_thresh_subarray(sorted_array,thresh): 
    diffs = (sorted_array[:,None] - sorted_array) 
    r = np.arange(sorted_array.size) 
    valid_mask = r[:,None] > r 
    mask = (diffs <= thresh) & valid_mask 
    bestcolID = (mask).sum(0).argmax() 
    idx = np.nonzero(mask[:,bestcolID])[0] 
    if len(idx)==0: 
     out = (0,0) 
    else: 
     out = idx[0]-1, idx[-1] 
    return out 

Probe läuft -

In [137]: sorted_array = np.array([0, 0.7, 1, 2, 2.5]) 

In [138]: longest_thresh_subarray(sorted_array,0.2) 
Out[138]: (0, 0) 

In [139]: longest_thresh_subarray(sorted_array,0.4) 
Out[139]: (1, 2) 

In [140]: longest_thresh_subarray(sorted_array,0.8) 
Out[140]: (0, 1) 

In [141]: longest_thresh_subarray(sorted_array,1) 
Out[141]: (0, 2) 

In [142]: longest_thresh_subarray(sorted_array,1.9) 
Out[142]: (1, 4) 

In [143]: longest_thresh_subarray(sorted_array,2) 
Out[143]: (0, 3) 

In [144]: longest_thresh_subarray(sorted_array,2.6) 
Out[144]: (0, 4)