4
\$\begingroup\$

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

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

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.