二分配列のバイナリ アルゴリズム

このモジュールは、要素の挿入後に並べ替えを維持するために並べ替えられたキュー リストを実装します。大量のデータを含むリストの場合、要素を挿入して並べ替えておくと、計算コストが非常に高くなります。このモジュールは、主にバイナリ アルゴリズムに基づいて実装される bisect アルゴリズムを実装します。

bisect.bisect_left(a, x, lo=0, hi=len(a))

要素 x を順序付きリスト a に挿入し、順序を変更せずに、挿入位置を返します。パラメータ lo と hi は判定リストの範囲を表し、デフォルトは全範囲です。挿入された要素 x がリスト a にすでに存在する場合、既存の要素の左側に挿入されます。

例:

#Python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_left (l, 0))

print(l)

print(bisect.bisect_left(l, 5))

print(bisect.bisect_left(l, 7))

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

[ 3, 5 , 6, 6, 8]

0

[3, 5, 6, 6, 8]

1

4

bisect.bisect_right(a, x, lo=0, hi= len(a ))

bisect.bisect(a, x, lo=0, hi=len(a))

順序付きキュー a 内で x を挿入できる位置を見つけ、キューを順序どおりに保ちます。挿入された値がキュー内の値と同じである場合、その値は同じ要素の右側に挿入され、この位置のインデックス値が返されます。

例:

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_right (l, 0))

print(l)

print(bisect.bisect(l, 5))

print(bisect.bisect(l, 7))

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

[ 3, 5 , 6, 6, 8]

0

[3, 5, 6, 6, 8]

2

4

bisect.insort_left(a, x, lo=0, hi= len(a ))

要素 x をキュー a に挿入し、キューをソートします。これは、a.insert(bisect.bisect_left(a, x, lo, hi), x) と同等である必要があります。

例:

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_left(l , 0)

print(l)

bisect.insort_left(l, 5)

print(l)

bisect.insort_left(l, 7)

print(l)

結果の出力は次のようになります。

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 8]

[0, 3, 5 , 5, 6, 6, 7, 8]

bisect.insort_right(a, x, lo=0, hi=len(a))

bisect.insort(a, x, lo=0 , hi= len(a))

要素 x をキュー a に挿入します。同じ要素が見つかった場合は、同じ要素の右側に挿入します。

例:

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_right(l , 0)

print(l)

bisect.insort(l, 5)

print(l)

bisect.insort(l, 7)

print(l)

結果の出力は次のようになります。

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 8]

[0, 3, 5 , 5, 6, 6, 7, 8]

上記の関数をいくつかの単純なカプセル化に使用します:

defindex(a, x):

'x と正確に等しい左端の値を見つけます'

i = bisect_left(a, x)

if i != len(a) and a[i] == x:

'x より小さい右端の値を検索'

i = bisect_left(a, x)

if i:

return a[i-1]

raise ValueError

def find_le(a, x):

'x 以下の右端の値を検索'

i = bisect_right(a, x )

if i:

return a[i-1]

raise ValueError

def find _gt(a, x):

'x より大きい左端の値を検索'

i = bisect_right(a, x)

if i != len(a):

a[i] を返す

be —((a, x),

_left(a, x)

if i ! = Len (a): re Return a [i]

raise valueerror

生徒のパフォーマンスを ABCDF レベルに変換するために使用します:

#python 3.4

IMPORT BISECT

Def Grade (score, Breakpoints =[60, 70, 80, 90], Grade= 'FDCBA'):

i = bisect.bisect(ブレークポイント, スコア)

成績を返します[i]

print([33, 99, 77, 70, 89, 90, 100])

print([成績] (score) for スコア in [33, 99, 77, 70, 89, 90, 100]])

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

[33, 99, 77 , 70, 89, 90, 100]

['F'、'A'、'C'、'C'、'B'、'A'、'A'】