python - 重複と並べ替えをサポートする Python で最も効率的なペア値データ構造?

Question

重複と並べ替えをサポートする、Python で最も効率的なペア値データ構造は何ですか?

辞書のような構造が必要ですが、重複をサポートする必要があります。各ペアの最初の値に基づいて高速にソートできるソリューションを探しています。

Answer 1

bisectモジュールを使用してソートされたリストを保持します。リストdataを使用して、新しいペアごとに、 によって返されるインデックスに、 で(a,b)始まるすべての既存のエントリの後に新しいエントリを追加します。リストは常にソートされた順序で維持されるため、「高速なソート」について心配する必要はありません。data.insertbisect(data,(a,LARGE_NUMBER))a

>>> from bisect import bisect
>>> from random import randint
>>> data = []
>>> for x in range(20):
...   a,b = randint(1,10),randint(1,100)
...   data.insert(bisect(data,(a,1000)),(a,b))
...
>>> for d in data: print (d)
...
(1, 67)
(1, 85)
(1, 38)
(2, 78)
(3, 57)
(3, 37)
(4, 76)
(4, 74)
(5, 47)
(5, 24)
(5, 59)
(5, 91)
(6, 85)
(6, 41)
(7, 18)
(7, 41)
(7, 24)
(9, 48)
(9, 77)
(9, 82)
(10, 80)