# Optimization of list's sublist

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

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

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