Pythonのライブラリ(bisect)を使用した場合の処理速度の違い
解決したいこと
競技プログラミングをやっていて、ライブラリと同じ処理を書いているはずなのに処理速度が違ったため、なぜなのか知りたい。
実際のソースコードと実行時間
- ライブラリ使用
import array
import bisect
L,Q = map(int,input().split())
tree = array.array('I',[0, L])
for _ in range(Q):
inC,inX = map(int,input().split())
place = bisect.bisect_left(tree,inX)
if inC == 1:
tree.insert(place,inX)
else:
print(tree[place]-tree[place-1])
- ライブラリ未使用(ライブラリと同じ関数をソースの中に記述)
import array
L,Q = map(int,input().split())
tree = array.array('I',[0, L])
def bisect_left(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
for _ in range(Q):
inC,inX = map(int,input().split())
place = bisect_left(tree,inX)
if inC == 1:
tree.insert(place,inX)
else:
print(tree[place]-tree[place-1])
0