Python/Numpy 查找长度变量跨度

Question

考虑一个单调递增的 (n,) 形状的 numpy 数组。

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

我的问题是有效地提取每个跨度 (i,j) 这样:

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

我不确定这种形式化。换句话说，我需要“总和高于 v 的最小可能跨度”。我想另一种表达方式是“总和高于 v 且不属于另一个跨度的所有跨度”。

到目前为止，我所做的最好的工作是基于两个嵌套的 for 循环:

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)]

它一定是一种更有效/更优雅的方式来做到这一点。然而，我可以找到方法。任何建议都将受到热烈欢迎!

F.

更新 #1:时间安排

使用 20K 个随机元素(结果取 10 次运行的平均值):

• 可变长度跨度:0.009332 秒
• davis_spans:0.009259 秒
• spans_broadcast:1.896222 秒

使用 1M 随机元素(结果取 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