How to efficiently check whether an element is within a range of a reference list and get the index reference list?

user_6446053 0
Viewed 40

The idea is to check whether each element in a list (i.e., data_list) is within a range of a reference list (i.e., range_list). If it is within the ref list, then extract at which index of the reference list (range_list) it occur.

The following code were drafted.

    lst=range(0,1000,1)
    n=6
    range_list=[lst [i:i + n] for i in range ( 0, len ( lst ), n )]

    data_list=[1,2,5,6,8,10,12,100, 102, 104, 105]
    idx_un=[]
    for x in data_list:
        for idx,y in enumerate(range_list):
            if min(y)<= x <= max ( y ):
                idx_un.append(idx)
                break

output:

[0, 0, 0, 1, 1, 1, 2, 16, 17, 17, 17]

But I am curious whether there exist much more compact and efficient approach.

list python performance
1 Answers

Since your ranges is basically a partition of the integers, you don't really need a list of ranges. You can just use a list of starting numbers of the ranges. Once you do that, you can can use the bisect module to get blazing fast binary search operations — both faster and simpler (assuming it fits your use case). That would leave you with something like:

import bisect

range_list = list(range(n,1000, n))
data_list=[1,2,5,6,8,10,12,100, 102, 104, 105]

[bisect.bisect_right(range_list, n) for n in data_list]
# [0, 0, 0, 1, 1, 1, 2, 16, 17, 17, 17]
user_38746230
Related