list's sublist opt

Question

(我鸡婆帮忙翻译了一下)

the problem is to find total number of sub-lists from a given list that doesn't contain numbers greater than a specified upper bound number say right and sub lists max number should be greater than a lower bound say left .Suppose my list is: x=[2, 0, 11, 3, 0] and upper bound for sub-list elements is 10 and lower bound is 1 then my sub-lists can be [[2],[2,0],[3],[3,0]] as sub lists are always continuous .My script runs well and produces correct output but needs some optimization

这个问题是这样子的: 给定一个 list, 找出符合以下规则的 sub lists 的 数量:

1. right 是个上限, sub list 中不可以含有任何超过 right 的数字

2. left 是个下限, sub list 中最大的数字必须得大於这个下限

举例来说, 给定 list [2, 0, 11, 3, 0], 上限值 10 和下限值 1, 则符合的 sub lists 有:

[2]
[2, 0]
[3]
[3, 0] 

注意, 在这里, sub list 的指是 sub sequence, 里面的元素在原 list 中也必须是连续的, 意思是说 [2, 3] 或是 [0, 2] 虽然也符合上下限的规则, 但是他们并非原 list 的 sub list, 他们的元素在原 list 中不连续。

以下的代码运行良好且能有正确的输出, 但在效能上还需要优化:

def query(sliced, left, right):
    end_index=0
    count=0
    leng=len(sliced)
    for i in range(leng):
        stack=[] 
        end_index=i
        
        while(end_index<leng and sliced[end_index]<=right):
            
            stack.append(sliced[end_index])
            if max(stack)>=left:
                count+=1
            end_index+=1

    print(count)

试运行:

origin=[2,0,11,3,0]
left=1
right=10
query(origin,left,right)

结果:

output:4

for a list say x=[2,0,0,1,11,14,3,5] valid sub-lists can be [[2],[2,0],[2,0,0],[2,0,0,1],[0,0,1],[0,1],[1],[3],[5],[3,5]] total being 10

There is another approach which is quite faster but for large queries it is a bit slow

对於 list [2, 0, 0, 1, 11, 14, 3, 5] 而言, 符合规则的 sub lists 有:

[2]
[2, 0]
[2, 0, 0]
[2, 0, 0, 1]
[0, 0, 1]
[0, 1]
[1]
[3]
[5]
[3, 5]

总共十个

这边还有另外一个方法可以比上面的方法快很多, 但对於大的输入数量级, 还是力有未逮:

def compute(sliced, lo, hi, left):
    num_invalid = 0
    start = 0
    search_for_start = True
    for end in range(lo, hi):
        if search_for_start and sliced[end] < left:
            start = end
            search_for_start = False
        elif not search_for_start and sliced[end] >= left:
            num_invalid += (end - start) * (end - start + 1) // 2
            search_for_start = True
    if not search_for_start:
        num_invalid += (hi - start) * (hi - start + 1) // 2
    return ((hi - lo) * (hi - lo + 1)) // 2 - num_invalid
    
def query(sliced, left, right):
    ans = 0
    start = 0
    search_for_start = True
    for end in range(len(sliced)):
        if search_for_start and sliced[end] <= right:
            start = end
            search_for_start = False
        elif not search_for_start and sliced[end] > right:
            ans += compute(sliced, start, end, left)
            search_for_start = True
    if not search_for_start:
        ans += compute(sliced, start, len(sliced), left)
    return ans

---

原出處: Optimization of list's sublist (stackoverflow)