リストをスライスするPythonicの方法w.r.t.タプル

Question

の最初の要素私は、xは、新しいリスト内の特定の値（x、y）の全ての数字は、そのリストをスライスするフォーム

x = 
[(0,1), (0,2), (0,3), ... 
(1,1), (1,3), (1,4), ... 
... 
(n,0), (n,4), ... 
] 

の組のソートされたリストを持っていると注文は保持されます。今、これは明らかにうまくいくでしょう：

y = [(a,b) for (a,b) in x if a == n] 

しかし、それは本当に遅いです。バイナリ検索でこの条件を満たす最初と最後のインデックスを見つける方が早いでしょう。 indexは値の最初のインデックスを返し、逆リストのindexは最後のインデックスを返します。 [a for (a,b) in x]を実行してリスト全体をコピーすることなく、どのように適用しますか？

Answer 1

@Liongoldによるコメントで示唆されているように、bisectを使用することができます。あなたはt[0] == 1を持つすべてのタプルtをしたいと仮定：

from bisect import bisect_left 

x = [(0, 1), (0, 2), (1, 1), (1, 2), (2, 1), (2, 2)] 

start = bisect_left(x, (1, None)) # index of the very first (1, i) 
end = bisect_left(x, (2, None)) # index after the very last (1, i) 

y = x[start:end] 

# y: [(1, 1), (1, 2)] 

あなたはbisect docsで詳細を見つけることができます。