Optimization of list's sublist

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

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

• andrew_reece: What is your optimization target, and where is your current performance in relation to your target? Also, are additional modules acceptable?
• Demonking28: @andrew_reece my script execution time is at least 1.5 times then the ideal execution time,Any builtin module would do

Answer 1

You can streamline by dropping the use of append, and ignoring values in your for-loop that are automatically disqualified. Benchmarking shows these steps reduce execution time by about 2x.

Original:

%%timeit
origin=[2,0,11,3,0]
left=1
right=10
query(origin,left,right) 
# 3.6 μs ± 950 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

New version:

def query2(sliced,left,right):
 count = 0
 leng = len(sliced)
 for i in range(leng):
 if sliced[i] <= right:
 stack_ct = 0
 end_index = i
 found_max = False
 while(end_index < leng and sliced[end_index] <= right):
 if not found_max:
 found_max = sliced[end_index] >= left
 end_index += 1
 stack_ct += 1
 if found_max:
 count += stack_ct
 return count

Benchmarking:

%%timeit
origin=[2,0,11,3,0]
left=1
right=10
query2(origin,left,right)
# 1.83 μs ± 41.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)