我想编写一个函数，该函数返回的最小总和大于列表的其余部分。列表将只有值-1和1。列表可能包含一百万个元素。 例如
v = [1 1 -1 1 -1 1 -1 1]
此处答案应为2，因为
1) 1 > 1 is False
2) (1 + 1) 2 > 0 (-1 + 1 -1 +1 -1 +1)
另一个例子
v = [-1 -1 1 1]
answer 4
我已经尝试过的代码：
def cumsum_grt(v):
for i in range(1,len(v)):
k = i
if sum(v[:k]) > sum(v[k:]):
break
return k
此功能可以正常工作，但是有什么方法可以提高性能？由于无法在几秒钟内计算大型列表的结果，因此失败了。
def cumsum_grt(v):
total_sum = sum(v)
curr_sum = v[0]
for i in range(1,len(v)):
if curr_sum > (total_sum - abs(curr_sum)):
break
curr_sum += v[i]
return i
测试：
lst = [1,1,-1,1]
lst2 = [1,20,15,1]
lst3 = [-2,4,-1]
lst4 = [-1,-1]
print(cumsum_grt(lst)) # 2
print(cumsum_grt(lst2)) # 4
print(cumsum_grt(lst3)) # 3
print(cumsum_grt(lst4)) # 1
时间绩效测量：
In [101]: lst = [1,5,-2,40]
In [102]: %timeit cumsum_grt(lst)
70.3 µs ± 175 ns per loop (mean ± std. dev. of 7 runs,10000 loops each)
In [103]: %timeit cumsum_grt_lenik(lst)
8.23 µs ± 27.9 ns per loop (mean ± std. dev. of 7 runs,100000 loops each)
In [104]: %timeit cumsum_grt_roman(lst)
8.22 µs ± 30.4 ns per loop (mean ± std. dev. of 7 runs,100000 loops each)
这是线性的O（N），而您的版本是O（N * N）：
def cumsum_grt(v):
so_far = 0
the_rest = sum(v)
for i in range(len(v)):
if so_far > the_rest :
return i
so_far += v[i]
the_rest -= v[i]
return len(v)
您可以将next与itertools.accumulate一起使用，将当前的累积总和与总和减去累积总和进行比较，然后使用enumerate获得该头寸的索引。 chain，其中[0]是列表第一个元素之前的位置。
>>> from itertools import accumulate,chain
>>> v = [1,1]
>>> s = sum(v)
>>> next((i for i,a in enumerate(chain([0],accumulate(v))) if a > s - a),len(v))
2
当心：请勿在{{1}}条件内计算sum(v)，否则将为O（n²）。如果累积的总和不足以用于任何元素，则末尾的if是默认值。