Geek Answers Handbook

Python: fist item index less than threshold in reverse sorted list

A similar question was asked for the sorted list here , but the solution used bisect , which does not work in the sorted list of backups.

Say I have a list sorted in reverse order superimposed on the middle element,

 my_list = [[3,0.99,1], [2,0.98,54], [10,.85,4], [1,0.7,10], [12,0.69,31], [12,0.65,43], [1.56,0] ....]

and I want to apply a series of threshold values ​​for the middle element that is in a separate sorted list, for example

 threshold = [0.97, 0.90, 0.83, 0.6]

I am trying to find out the index of the first element is less than the threshold value. In the above example, it should return,

 index_list = [2, 2, 3, 6]

A suggestion on how this can be done in the fastest way?

+4
source share
5 answers

According to this comment from @ gnibbler, you can rewrite the bisect code yourself according to your needs

I am slightly modifying the code from @ gnibbler so that it can be used in your case

The optimization is that since your thresholds are also sorted, we don’t need to search the whole list every time, but start with the last index result

 def reverse_binary_search(a, x, lo=0, hi=None): if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) while lo < hi: mid = (lo+hi)/2 if x > a[mid][4]: hi = mid else: lo = mid+1 return lo my_list = [[3,0.99,1], [2,0.98,54], [10,.85,4], [1,0.7,10], [12,0.69,31], [12,0.65,43], [1.56,0]] threshold = [0.97, 0.90, 0.83, 0.6] index_list = [] last_index = 0 for t in threshold: last_index = reverse_binary_search(my_list, t, last_index) # next time start search from last_index index_list.append(last_index)

Thanks @ PhilCooper for valuable suggestions. Here is the code using the generator that he suggested:

 def reverse_binary_search(a, threshold): lo = 0 for t in threshold: if lo < 0: raise ValueError('lo must be non-negative') hi = len(a) while lo < hi: mid = (lo+hi)/2 if t > a[mid][6]: hi = mid else: lo = mid+1 yield lo my_list = [[3,0.99,1], [2,0.98,54], [10,.85,4], [1,0.7,10], [12,0.69,31], [12,0.65,43], [1.56,0]] threshold = [0.97, 0.90, 0.83, 0.6] index_list = list(reverse_binary_search(my_list, threshold))
+3
source

Using numpy, which I think looks a little cleaner than pure python implementations, and will almost certainly be faster:

 import numpy as np arr = np.array([[3,0.99,1], [2,0.98,54], [10,.85,4], [1,0.7,10], [12,0.69,31], [12,0.65,43], [10,0.50, 24]]) thresholds = [0.97, 0.90, 0.83, 0.60] idx = [np.min(np.where(arr[:,1] < i)) for i in thresholds if np.where(arr[:,1] < i)[0].size > 0] print idx [2, 2, 3, 6]
+1
source

Try the following:

 threshold = [0.97, 0.90, 0.83, 0.6] my_list = [[3,0.99,1], [2,0.98,54], [10,.85,4], [1,0.7,10], [12,0.69,31], [12,0.65,43], [1,.56,0]] threshold = [0.97, 0.90, 0.83, 0.6] index_list = [] ti = 0 for i, item in enumerate(my_list): if item[1] >= threshold[ti]: continue while ti < len(threshold) and item[1] < threshold[ti]: index_list.append(i) ti += 1
0
source

I think you should get the keys and reverse. Then bisecet ok

 from bisect import bisect_left keys = [vals[1] for vals in my_list] keys.reverse() mylen = len(my_list) [mylen-bisect_left(keys,t) for t in threshold]

If you already have numpy:

 my_array = np.array([[3,0.99,1], [2,0.98,54], [10,.85,4], [1,0.7,10], [12,0.69,31], [12,0.65,43], [10,0.50, 24]]) thresholds = [0.97, 0.90, 0.83, 0.60] my_array.shape[0]-arr[::-1,1].searchsorted(threshold)
0
source 
 import bisect my_list_2 = sorted(my_list, key=lambda x:x[1]) for x in threshold: len(my_list) - bisect.bisect([z[1] for z in my_list_2], x)
0
source

More articles:


All Articles