4

ここでソートされたリストについて同様の質問がされましたが、使用されたソリューションbisectは予約ソートされたリストでは機能しません。

逆順でソートされ、中央の要素をキーにしたリストがあるとします。

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]

最速の方法でそれを行う方法を提案していますか?

4

5 に答える 5

4

@ 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))
于 2012-07-06T21:42:21.767 に答える
1

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]

于 2012-07-06T22:01:43.170 に答える
0 
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)
于 2012-07-06T21:44:58.057 に答える
0

次のことを試してください。

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
于 2012-07-06T21:23:38.057 に答える
0

私はあなたが鍵を手に入れて逆にするべきだと思っています。それならバイセセは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]

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)
于 2012-07-06T21:25:36.747 に答える