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

What is your optimization target, and where is your current performance in relation to your target? Also, are additional modules acceptable? — andrew_reece
– andrew_reece, Commented Nov 5, 2017 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 — Demonking28
– Demonking28, Commented Nov 5, 2017 at 22:19

andrew_reece · Accepted Answer · 2017-11-05 22:53:30Z

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)

Stack Exchange Network

Optimization of list's sublist

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Optimization of list's sublist

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions