Python で bisect を使用する方法

この記事の例では、比較的一般的な実践的なスキルである Python での bisect の使用法について説明します。皆さんの参考に共有してください。具体的な分析は次のとおりです。

一般に、Python の bisect は、並べ替えられた配列を操作するために使用されます。たとえば、配列にデータを挿入しながら並べ替えることができます。以下のコードは、これを行う方法を示しています:

import bisect
import random
random.seed(1)
print('New pos contents')
print('-----------------')
l=[]
 
for i in range(1,15):
  r=random.randint(1,100)
  position=bisect.bisect(l,r)
  bisect.insort(l,r)
  print '%3d %3d'%(r,position),l

出力結果は次のとおりです:

New pos contents
-----------------
 14  0 [14]
 85  1 [14, 85]
 77  1 [14, 77, 85]
 26  1 [14, 26, 77, 85]
 50  2 [14, 26, 50, 77, 85]
 45  2 [14, 26, 45, 50, 77, 85]
 66  4 [14, 26, 45, 50, 66, 77, 85]
 79  6 [14, 26, 45, 50, 66, 77, 79, 85]
 10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77  9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

ご覧のとおり、これらの乱数を挿入すると同時に配列がソートされます。ただし、上記の 77,77 のように、いくつかの繰り返し要素があります。これらの繰り返し要素の順序を同じ要素の左側に設定するには、bisect_left を使用します。それ以外の場合は、insort_left と insort_right を使用します。たとえば、次のコードでは、要素インデックスの変更が繰り返されていることがわかります。

import bisect
import random
random.seed(1)
print('New pos contents')
print('-----------------')
l=[]
 
for i in range(1,15):
  r=random.randint(1,100)
  position=bisect.bisect_left(l,r)
  bisect.insort_left(l,r)
  print '%3d %3d'%(r,position),l

出力結果は次のとおりです:

New pos contents
-----------------
 14  0 [14]
 85  1 [14, 85]
 77  1 [14, 77, 85]
 26  1 [14, 26, 77, 85]
 50  2 [14, 26, 50, 77, 85]
 45  2 [14, 26, 45, 50, 77, 85]
 66  4 [14, 26, 45, 50, 66, 77, 85]
 79  6 [14, 26, 45, 50, 66, 77, 79, 85]
 10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77  8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

この関数 bisect.bisect(list,key) は、Java の TreeMap の tailMap(fromkey) に似ています。

この記事が皆さんの Python プログラミングに役立つことを願っています。