月: 2019年6月

前の記事のフィボナッチ数列の実装の中で、関数が呼び出された回数を数えるために少し仕掛けをいれました。
参考:pythonの関数をメモ化する

で、その中で globalと言うのを使っているのでその解説です。

ドキュメントはこちら。
global文

pythonでは、関数の中でグローバル変数を”参照”することができます。
しかし、そのままではグローバル変数に”代入”はできません。

やってみましょう。
まずは、”参照”ができることの確認。

a = 1


def sample1():
    # グローバル変数aの値を参照できるためaの値1を戻す。
    return a


sample1()  # 1

次に、代入を試してみます。ちょっとわかりにくいですが、グローバル変数bを用意し、
関数中でbに代入していますがこのbが実はローカルの変数で、
関数の外でもともと宣言されていたbに影響していないことがわかります。

b = 2


def sample2():
    # グローバル変数bへの代入はできないので、このbはローカル変数
    b = 3
    print(b)


sample2()  # 3
# 変数bは変更されていない
print(b)  # 2

これが、global文を使うと、グローバル変数への代入が可能になります。

c = 10


def sample3():
    global c
    c = 20
    print(c)


sample3()  # 20
# 関数中の変更が反映されている
print(c)  # 20

プログラムを書いていると再帰呼び出しする関数や整数値を引数にとる関数など、同じ値を渡して何度も実行される関数があります。
そのような場合、メモリーが十分あるのであれば毎回毎回処理を実行するより結果を保存しておく方が効率的です。

それを、メモ化(Memoization)と言うそうです。
メモ化 – Wikipedia

自分で実装するのも難しくないですが、pythonでメモ化を行うには、
@functools.lru_cache
と言う便利なデコレーターが用意されています。

ちなみに、lruは、Least Recently Usedの略です。
キャッシュアルゴリズム – Wikipedia

フィボナッチ数列で実際に使ってみましょう。
また、実際に効率化できている(関数中の処理の実行回数が減っている)ことを確認するために、
その関数が何回呼び出されたのかを記録し、表示します。
また、実行時間も測りましょう。

まず、メモ化をしない例。(jupyter notebookで動作させることを前提としたコードです。)

%%time
fib_count = 0  # 関数が呼び出された回数記録用


def fib(n):
    global fib_count
    fib_count = fib_count + 1
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)


print("F(100)=", fib(30))
print("実行回数:", fib_count)

# 以下出力
F(100)= 832040
実行回数: 2692537
CPU times: user 449 ms, sys: 3.35 ms, total: 453 ms
Wall time: 456 ms

fibが何度も繰り返し実行され、非常に無駄の多い実装になっていることがわかります。

続いて、lru_cacheでメモ化した例です。

%%time
from functools import lru_cache
fib_memo_count = 0  # 関数が呼び出された回数記録用


@lru_cache(maxsize=None)
def fib_memo(n):
    global fib_memo_count
    fib_memo_count = fib_memo_count + 1
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_memo(n-1) + fib_memo(n-2)


print("F(100)=", fib_memo(30))
print("実行回数:", fib_memo_count)

# 以下出力
F(100)= 832040
実行回数: 31
CPU times: user 229 µs, sys: 120 µs, total: 349 µs
Wall time: 311 µs

こんどのfib_memoは31回しか実行されませんでした。
n=0,...,30 でそれぞれ1回ずつですね。
処理時間も桁違いに早くなっています。

実は最近まで知らなかったのですが、pythonの集合(set)同士の包含関係を不等号で確認することができます。

ドキュメントはこちら
組み込み型 set（集合）型

念のため軽く用語の説明をしておくと、
集合Aと集合Bに対して、
Aの任意の要素xがBの要素でもある時、AはBの部分集合(subset)であるといいます。
それを記号で、 $A\subseteq B$ と書きます。
左右反転して、 $B\supseteq A$ と書くこともできます。
また、さらに集合Aと集合Bが等しくない時は、真部分集合(もしくは狭義の部分集合)といい、
$A\subset B$ もしくは $B\supset A$と書きます。

これをpythonではそれぞれ、 <=, >=, <, >, で計算できます。
戻り値はTrueかFalseです。
いくつかやってみましょう。

{1, 3, 5} <= {1, 2, 3, 4, 5}
# True

{1, 3, 5, 7} <= {1, 2, 3, 4, 5}
# False

{1, 3, 5} >= {1, 3, 5}
# True

{1, 3, 5} > {1, 3, 5}
# Flase

二つの文字列がどのくらい異なるかを表す距離関数として、以前レーベンシュタイン距離と言うのを紹介しました。
参考:pythonで編集距離(レーベンシュタイン距離)を求める

これよりももっとシンプルな関数として、ハミング距離(Hamming distance)と言うのがあるのでその紹介です。
これは文字数が同じ二つの文字列に対して、単純に異なる文字を数えたものです。
ハミング距離 – Wikipedia

自分の場合、文字数が同じ時しか定義できないなどの理由により、レーベンシュタイン距離に比べて使う頻度は低いです。
ただ、文字数が同じでさえあれば高速に計算できます。

pythonでの実装ですが、レーベンシュタイン距離の時に使った、
python-Levenshtein に含まれています。

試しにやってみましょう。

import Levenshtein
print(Levenshtein.hamming("toned", "roses"))
# 3

この例の toned と roses では、ハミング距離もレーベンシュタイン距離もどちらも3ですが、
文字数が同じであってもこの２種類の距離の値が異なる例はあります。

例えば次のようなケースです。

text1 = 'abcdefg'
text2 = 'bcdefga'
print(Levenshtein.distance(text1, text2))
# 2
print(Levenshtein.hamming(text1, text2))
# 7

前回の記事がmap関数の話だったので、今回は使い方のよく似たfilter関数です。

ドキュメントはこちら。
組み込み関数

基本的な構文は以下の形で、iterable の各要素に functionを適用して、
結果が新なものだけを取り出せます。
filter(function, iterable)

map関数と同様に、戻り値はリストではなくイテレーターになるので最初は少し戸惑いました。
試しに、整数のうち偶数だけ抽出するフィルターを書いてみます。

def f(n):
    return n % 2 == 0


m = filter(f, range(10))
print(m)
# <filter object at 0x114d178d0>
print(list(m))
# [0, 2, 4, 6, 8]
print(list(m))
# []

細かい説明は mapの記事に書いた通りなのですが、
イテレーターを使うために、リストに変換するなり、nextで取り出すなりする必要があり、
一度取り出すともう一回listに変換しようとしても空のリストしか返ってこなくなります。

なお、内包表記でもほぼ同じ処理が実装でき、自分はこちらを使うことが多いです。

[x for x in range(10) if f(x)]
[0, 2, 4, 6, 8]