Python/Numpy найти длину переменной длины

Question

Рассмотрим многоуровневую матрицу формы (n,), которая монотонно возрастает.

X = np.array([2,3,7,19,110,112,120,140,161]) 

Моя проблема заключается в извлечении эффективно каждый Span (i,j) таким образом, что:

X[i:j].sum() >= v and X[i:j-1].sum() < v 

Я не уверен в этом формализации. Другими словами, мне нужны «наименьшие возможные промежутки, которые суммируются выше v». Я предполагаю, что другой способ выразить это «все промежутки, которые суммируются выше v и которые не являются подмножествами другого диапазона».

До сих пор лучшее, что я сделал на основе двух вложенной для петель:

def variable_length_spans(X, v): 
    n, = X.shape 
    for i in xrange(0, n): 
     sum_ = 0 
     for j in xrange(i, n): 
      sum_ += X[j] 
      if sum_ >= v: 
       yield (i,j+1) 
       break 

Что дает:

list(variable_length_spans(X,10)) 
[(0, 3), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)] 

Это должно быть более эффективным/элегантный способ сделать это. Но я могу узнать, как это сделать. Любое предложение будет тепло оценено!

Ф.

Обновление # 1: тайминги

С помощью 20K случайных элементов (результаты в среднем более 10 трасс):

• variable_length_spans: 0,009332 сек
• davis_spans: 0.009259 sec
• spans_broadcast: 1.896222 sec

1М случайных элементов (результаты в среднем более 50 трасс):

• variable_length_spans: 0,528101 сек
• davis_broadcast: 0,534576 сек

Answer 1

В настоящее время это квадратичный алгоритм, и это можно сделать в линейном времени следующим образом:

def spans(X, v): 
    n, = X.shape 
    i = 0 
    total = 0 
    for j in xrange(0, n): 
     total += X[j] 
     while total >= v: 
      yield (i, j+1) 
      total -= X[i] 
      i += 1 

Answer 2

Векторизованное подход, основанный на broadcasting -

# Get cumulative summations 
cumsums = X.cumsum() 

# Elementwise subtractions between cumsums & its one place shifted version 
diffs = cumsums[:,None] - np.append(0,cumsums[:-1]) 

# Detect cumulative summation span check 
mask = diffs >= v 

# Get valid mask for later selection purpose 
valid = mask.any(0) 

# Get first trigger indices 
max_idx = np.argmax(mask,0)+1 

# Concatenate row indices alongwith trigger ones for final output 
out = np.column_stack((np.arange(max_idx.size),max_idx))[valid] 

вход образца, выход -

In [212]: X 
Out[212]: array([ 2, 3, 7, 19, 110, 112, 120, 140, 161]) 

In [213]: v 
Out[213]: 10 

In [214]: out 
Out[214]: 
array([[0, 3], 
     [1, 3], 
     [2, 4], 
     [3, 4], 
     [4, 5], 
     [5, 6], 
     [6, 7], 
     [7, 8], 
     [8, 9]])