kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

5.5 標準ライブラリによる検索

イテレータ

イテレータってforとかで使ってるくらいで素では使ったことないな
たぶん普通は素で使うことはないんだろう

C++と見比べてみると

C++ではend()と比較して、PythonではStopIteration例外を補足する
これは前も見た

サンプルのprint()をできるだけ直訳するとこんな感じだろうか

def print_it(v):
    it = iter(v)
    while True:
        try:
            print(next(it), end="")
        except StopIteration:
            break
    print()

あと、Pythonではイテレータの指す場所の値を更新することはできないのかな
イミュータブルっぽく使えってことだと理解しておく

しかしサンプルをpython化しようとするとこんな

it = iter(v)
v2 = []
next(it)
v2.append(3)
v2.append(next(it) + 1)
v2.append(next(it))
v2.append(next(it))

とかこんな

it = iter(v)
v3 = []
for i, x in enumerate(v):
    if i == 0:
        v3.append(3)
    elif i == 1:
        v3.append(x + 1)
    else:
        v3.append(x)

でちょっとブサイクな気もする

二分探索

pythonではbisectというライブラリが使えそう
二分探索とはいうものの、値をみつけるというよりもソートされた状態を
保ったまま新しい要素を挿入するための場所を探すというのが目的な模様
これを使えば高速な挿入ソートができるというわけかな

C++ではイテレータを返すけどPythonでは単にリストのインデックスを返すので
使い方はこんな感じ

A = [1, 1, 2, 2, 2, 4, 5, 5, 6, 8, 8, 8, 10, 15]
pos = bisect.bisect_left(A, 3)
print("A[%s] = %d" % (pos, A[pos]))
pos = bisect.bisect_left(A, 2)
print("A[%s] = %d" % (pos, A[pos]))

普通に値を見つけたいときの使い方も書いてあった
8.6.1. Searching Sorted Lists

ALDS1_4_Bのsearchがこうなる

def search(S, y):
    pos = bisect_left(S, y)
    return S[pos] == y

#10 が 00.09s秒
元のソースだと00.25sだから速くなってる