42

ドキュメントには例がありません...bisect.insort_left)_キーに基づいてどのように使用しますか?

キーに基づいて挿入しようとしています。

bisect.insort_left(data, ('brown', 7))

に挿入を挿入しdata[0]ます。

ドキュメントから...

bisect.insort_left(a, x, lo=0, hi=len(a) aにxをソート順に)

    挿入します。これは、 aが既にソートされていると仮定するのと同じです。O(log n) 検索は、遅い O(n) 挿入ステップによって支配されることに注意してください。a.insert(bisect.bisect_left(a, x, lo, hi), x)

使用例:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)
>>>

を使用して、ソートされたリストの('brown', 7)後に入れたい。今のところ...キーを使用して挿入を行っていないため...ドキュメントには、キーを使用して挿入を行うことが示されていません。('red', 5)databisect.insort_leftbisect.insort_left(data, ('brown', 7))('brown', 7)data[0]

4

5 に答える 5

24

__getitem__およびを実装するクラスで iterable をラップできます__len__。これにより、 でキーを使用できるようになりますbisect_left。反復可能関数とキー関数を引数として取るようにクラスを設定した場合。

これを拡張して使用できるようにするには、メソッドinsort_leftを実装する必要があります。insertここでの問題は、それを行うとinsort_left、キーがメンバーであるオブジェクトを含むリストにキー引数を挿入しようとすることです。

例はより明確です

from bisect import bisect_left, insort_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

    def insert(self, index, item):
        print('asked to insert %s at index%d' % (item, index))
        self.it.insert(index, {"time":item})

timetable = [{"time": "0150"}, {"time": "0250"}, {"time": "0350"}, {"time": "0450"}, {"time": "0550"}, {"time": "0650"}, {"time": "0750"}]

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

islindex = insort_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

insert私の方法で、タイムテーブル辞書に固有のものにする必要があった方法を参照してください。そうしないと、挿入すべき場所にinsort_left挿入しようとしますか?"0359"{"time": "0359"}

これを回避する方法は、比較用のダミー オブジェクトを構築し、継承しKeyWrapperてオーバーライドinsertするか、何らかのファクトリ関数を渡してオブジェクトを作成することです。これらの方法はどれも、慣用的な python の観点から特に望ましいものではありません。

したがって、最も簡単な方法は、挿入インデックスを返し、自分で挿入を行うKeyWrapperwith を使用することです。bisect_leftこれを専用の関数で簡単にラップできます。

例えば

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")
timetable.insert(bslindex, {"time":"0359"})

この場合、 を実装していないことを確認してくださいinsert。そのため、誤って aKeyWrapperを変更関数に渡した場合insort_left、おそらく正しいことを行わない可能性があることにすぐに気付くでしょう。

サンプル データを使用するには

from bisect import bisect_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda c: c[1])

newcol = ('brown', 7)

bslindex = bisect_left(KeyWrapper(data, key=lambda c: c[1]), newcol[1])
data.insert(bslindex, newcol)

print(data)
于 2016-09-15T00:19:05.560 に答える
3

Python 3.10 以降、モジュール内のすべてのバイナリ検索ヘルパーが引数bisectを受け入れるようになりました。key

key各入力要素から比較キーを抽出するために使用される 1 つの引数のキー関数を指定します。デフォルト値はNone (要素を直接比較) です。

したがって、データの並べ替えに使用したのと同じ関数を渡すことができます。

>>> import bisect
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)]
>>> bisect.insort_left(data, ('brown', 7), key=lambda r: r[1])
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('brown', 7), ('yellow', 8)]
于 2021-10-20T13:57:54.130 に答える