Python：反向排序列表中小于阈值的第一个元素的索引

Question

这里对排序列表也提出了类似的问题，但所使用的解决方案对分不适用于保留排序列表。

假设我有一个列表，按相反的顺序排序，键入中间元素，

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 = [2, 2, 3, 6]

建议如何以最快的方式完成？

Answer 1

请尝试以下操作：

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

Answer 2

使用numpy，我认为它看起来比纯python实现更干净，并且几乎肯定会更快：

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]

Answer 3

根据@gnibbler的这个好答案，您可以自己重写bisect代码以满足您的需要

我稍微修改了@gnibbler中的代码，以便可以在您的案例中使用

一个优化是，由于您的阈值也被排序，我们不需要每次都搜索整个列表，而是从最后一个结果索引开始

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)

感谢@PhilCooper提供的宝贵建议。下面是他建议的使用生成器的代码：

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