FP:無限を扱いたい願望が遅延評価を生んだ
このワークシートはMath by Codeの一部です。
無限を扱いたい願望が遅延評価を生んだ。
「遅延評価」というとむずかしそうだが、
「生真面目とさぼりを両立させる。さぼれるところは徹底してさぼる。」
ということです。
計算するには式を評価しなければできません。
評価を遅らせる、つまり、さぼることは
計算もあえてスルーするということです。
このことが、無限を扱ったり、超大量データ処理の高速処理につながるのです。
これはPythonの発明ではなく、
初期の関数型言語、Haskellなどの大御所の「遅延評価」という発想を、
Pythonも取り入れたという歴史があります。
歴史はともかく、その発想と効果をもっとくわしくみていこう。
その名もitertools.
iter, イテレーションといえば、左から順に生真面目にやる代名詞。
それが、なぜ、さぼりの道具をもっている？？？
面白そうだ。
１、generatorが効率的な理由をさぐろう
generatorが効率的な理由をさぐろう
＜さぼり屋と言えばAndとOr＞
遅延評価と言わなくても
さぼり屋がいる。
それはAndとOrだ。
たとえば,
it=１＋２＋３＋４＋５
itを計算するには、1，2，3，4，5を全部評価して、左からたし算してitは10となる。
it=True or A or B or C
itを計算するには、先頭を見てすぐに、Trueとわかるから、A,B,Cの中身は見なくてもOK。
Orだから。
同じことが、it=False and A and B and C は一瞬でFalseと言える。
これは、PCのプログラムでなくてもわかることだ。
これが、評価をさぼる、遅くする。
lazy,deferのイメージだ。
この例は、遅らせるどころか、スルーしてますけどね。
では、完璧なスルーはしないまでも、遅らせる。
これをみてみよう。
＜要求のあるときだけ働くgenerator＞
次のフィボナッチ数列という定義は一見恐ろしく見えます。
真である間はずっと数列の計算をするみたいだからです。
無限数列生成プログラムに見えます。
でも、next(generator)というセリフで
yield が5回呼ばれるだけだから、数列は5個で終了することが保証されています。
def fibonacci_seq():
a, b = 1,1
while True:
yield a
a, b = b, a + b
# Generating the first five Fibonacci numbers
generator = fibonacci_seq()
for _ in range(5):
print(next(generator))
[OUT]
1
1
2
3
5
なぜそうなるのか？
fibonacci_seqにはreturn文がありません。
だから、１回次は？呼ばれたらyieldはしぶしぶ1回返す。
yieldには「(圧力に負けて)明け渡す、(要求されて)(…に)許す」という訳語がある通り、
ただ生み出すということではありません。
「は~い、わかりましたよ。」としぶしぶ仕事をする。
できるだけ仕事を遅らせる。
言われたことだけやる最低の社員lazy。
いわれたこと以上のことをやる熱心なモーレツ社員eagerではありません。
＜レイジー関数をレンジに使う＞
レイジー関数はgenerator に入れて、nextを呼ばなくても使えます。
レイジー関数をレンジ関数にすれば、普通のレンジの書き方もできます。
def lazy_range(limit):
current = 0
while current < limit:
yield current
current += 1
for number in lazy_range(5):
print(number)
＜レイジー関数をつなぐと効率的＞
さぼり部品をバケツリレーすると効率がいいです。
def read_file(file_path):
with open(file_path, 'r') as file:
for line in file:
yield line.rstrip('\n')
def filter_comments(lines, comment_char='#'):
for line in lines:
if not line.startswith(comment_char):
yield line
def transform_lines(lines):
for line in lines:
# Example transformation: convert the line to uppercase
yield line.upper()
#文字列sのファイルを直下に作る。
s = '##New line 1\n#New line 2\nNew line 3'
with open('data.txt', mode='w') as f:
f.write(s)
#読み取ったファイルをパイプラインで読みとって出力する。
lines = read_file('data.txt')
filtered_lines = filter_comments(lines)
processed_lines = transform_lines(filtered_lines)
for line in processed_lines:
print(line)[OUT]
NEW LINE 3
processed_lines はレイジー関数を連結してレイジー関数です。
ファイルの小文字を大文字に変えるtransform_linesが働くのは、
filter_commentsが♯から始まる行を削った残りです。だから、仕事は一瞬で終わりますね。
それぞれの関数はyield が呼ばれるまで、メモリという仕事場を汚さないクリーンで効率的です。
＜itertools.isliceで切って回す＞
レイジー関数のバケツリレーをitertools.isliceに渡すと、さらに効率があがります。
999999の倍数の平方数を計算するのに、もともとは流している数は１から順に増える
自然数のはずですが、filter999999mulitでフィルタリングして、平方数にします。
itertools.isliceで切り取って渡すので、無駄がありません。
ちなみに、isliceはスライスの指定と結果は以下の通り。
# islice('ABCDEFG', 2) → A B
# islice('ABCDEFG', 2, 4) → C D
# islice('ABCDEFG', 2, None) → C D E F G
# islice('ABCDEFG', 0, None, 2) → A C E G次の例では10個表示しますが、10000000個とかにしても同じようなスピード感で淡々と表示が
進みます。最初に無限の自然数を読み取るなどという無謀なことをしてませんから、
メモリ効率が抜群なのです。
def infinite_numbers():
num = 0
while True:
yield num
num += 1
def filter999999mulit(numbers):
for num in numbers:
if num % 999999 == 0:
yield num
def square_numbers(numbers):
for num in numbers:
yield num * num
# 無限パイプライン
numbers = infinite_numbers()
multi_numbers = filter999999mulit(numbers)
squared_numbers = square_numbers(multi_numbers)
import itertools
for num in itertools.islice(squared_numbers, 10):
print(num)
[OUT]
0
999998000001
3999992000004
8999982000009
15999968000016
24999950000025
35999928000036
48999902000049
63999872000064
80999838000081
２．無限のためのitertools
無限のためのitertools
＜countは無限小にも役立つ無限等差数列＞
無限のためのものといえば、itertools.countがあります。
for文のrange関数はゴール指定で回しますが,countはステート指定で回します。stepの指定もできます。
だから、count(start,step)は
ほっとくと、初項start,公差stepの等差数列を無限に作ってくれます。
実際は、zip,mapと組み合わせることで、有限のものにナンバリングすることができます。
from itertools import count
enumerate = lambda x, start=0: zip(count(start), x)
これで、enumerateというおなじみの番号つき切り取り関数と同等なものが作れます。
だから、次の２つの出力は同じです。
print(list(zip(count(), iter('WordCount'))))
print(list(enumerate(iter('WordCount'))))
[OUT]
[(0, 'W'), (1, 'o'), (2, 'r'), (3, 'd'), (4, 'C'), (5, 'o'), (6, 'u'), (7, 'n'), (8, 't')]
enumerateはstart=0,step=1のcountラベルを作りますが、countには自由度があります。
list(zip(count(-9, 0.5), iter('WordCount')))
[OUT]
[(-9, 'W'),
(-8.5, 'o'),
(-8.0, 'r'),
(-7.5, 'd'),
(-7.0, 'C'),
(-6.5, 'o'),
(-6.0, 'u'),
(-5.5, 'n'),
(-5.0, 't')]
countという枠組みのあとに有限データiter('WordCount')を渡すことで、有限の出力をしてくれます。
小数でカウントするなんて何のやくにたつのだろうと思われるかもしれない。
しかし、近似値を求めるときに、
ｘの値をstart=0.1, step=0.001で刻みながら、yとの差の絶対値を求めるレイジー関数を作る。
その差が希望の範囲d未満になるときのxの値を返すレイジー関数を作る。
それをバケツリレーをすると、級数の和や数列の収束で希望の範囲になるときの値を求める
数学の問題で役立つでしょう。
＜cycleは無限大にも役立つ無限ロールスタンプ＞
無限のためのものといえば、itertools.cycleがあります。
cycle('ABC') → A B C A B C A B C D ...
これも延々と出力しそう（でも、実際はしない。）だから、zipなどで有限にして使えます。
counter = 0
for item in itertools.cycle(['A','B','C']):
print(item)
counter+= 1
if counter > 6: # To avoid infinite loop
break
[OUT]
A
B
C
A
B
C
A
これだけ見ると、「だからどうした。」となるでしょう。
これが10億個とかの超大量データ処理になると本領発揮します。
10億を1個ずつ区切るレイジー関数に、たとえば、step=10000で、
データにナンバリングして、それを抽出するレイジー関数をかませ、最後に
データ処理をするというバケツリレーを作ることがありえるでしょう。
レイジー関数ですから、途中をすっ飛ばして、抽出したデータだけを処理するので、
全件読み取るメモリーも不要、時間も不要です。読んだデータだけを処理するので、
10000倍以上のスピードで実行できるでしょう。
＜振り返り＞
genenator関数のときもそうでしたが、itertoolsの関数でもパイプラインの共通点があります。
レイジー関数のパイプラインは
・呼び出された瞬間は、何ひとつ仕事をしない。
・メモリを汚さず、ただ「パイプ（構造）」だけを綺麗につなぎ合わせる。
・最後の最後に、要求した分でパイプラインの中を通るものだけを通してメモリ空間で物質化させる。
つまり、itertoolsは、
遅延評価パイプラインが「生真面目なループ」構造の圧力を極小化して
「極限までサボる yield」を働かせる
というメモリ効率化パラダイムで爆発的な力を発揮するのですね。
最後に、有限リストでもお役立ちの機能があるitertoolsの関数群を紹介します。
３．有限のitartools
有限は有限でitertoolsは役立ちます。
組み合わせ論、データ集計などいろいろありますが、まずは
組み合わせ論の
permutations、 combinationsです。
＜permutations、 combinations＞
これは値としての順列、組み合わせではなく、文字列の組み合わせとして作ってくれるのです。
たとえば、
# permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) → 012 021 102 120 201 210
# combinations('ABCD', 2) → AB AC AD BC BD CD
# combinations(range(4), 3) → 012 013 023 123
のように、もとの文字列から切り出して部分集合としての文字列を作ってくれます。
そうすると、文字を使ったパズルの解法に使えたりします。
forループを文字数だけ回すと煩雑になることを防ぐことができめますね。
覆面算
read + write + talk = skill
from itertools import permutations
# 0から9までの使用可能な数字の敷地を新築
usable = list(range(10))
setU = set(usable)
cnt = 0
def check(a, e, t, r, k, d, l, i, w, s):
global cnt
# 各単語を数理ロジックに復元
A = r * 1000 + e * 100 + a * 10 + d # READ
B = w * 10000 + r * 1000 + i * 100 + t * 10 + e # WRITE
C = t * 1000 + a * 100 + l * 10 + k # TALK
D = s * 10000 + k * 1000 + i * 100 + l * 11 # SKILL (L*10 + L = L*11)
if A + B + C == D:
cnt += 1
print(f"{A} + {B} + {C} = {D}")
# 10文字一気に回すと「10! = 3,628,800通り」になる。
# まずは最初の6文字 (a, e, t, r, k, d) の順列だけをサボりながら回す（10P6 = 151,200通り）
for v in permutations(usable, 6):
a, e, t, r, k, d = v
# 頭文字（最上位の桁）が 0 になる偽物の世界を事前に除外
if t != 0 and r != 0:
# 一の位の計算 (D + E + K) から、L の値を一意に確定させる！
l = (d + e + k) % 10
# 確定した L が、すでに使った6文字と重複していない場合のみ、奥へ進む
if l not in {a, e, t, r, k, d}:
# 全体集合から、現在ロックされている7文字をサッと引き算
diffs = setU - {a, e, t, r, k, d, l}
# 残った3文字 (i, w, s) の全順列（3! = わずか6通り）をパパッと回す
for p in permutations(diffs):
i, w, s = p
# 残る頭文字も 0 ではないことを確認し、最終チェックへ
if w != 0 and s != 0:
check(a, e, t, r, k, d, l, i, w, s)
print(f"\n合計：{cnt} 通り")
#=================================================
[OUT]
4905 + 24689 + 8017 = 37611
9728 + 19467 + 6205 = 35400
1632 + 41976 + 7380 = 50988
2543 + 72065 + 6491 = 81099
5270 + 85132 + 3764 = 94166
5180 + 65921 + 2843 = 73944
5094 + 75310 + 1962 = 82366
5096 + 35710 + 1982 = 42788
7092 + 37510 + 1986 = 46588
7092 + 47310 + 1986 = 56388
10 通り
このように、文字数の爆発をふせぐコードがかけますね。
もとはjuliaで書いてますが、もとのページはこちらです。
＜簡易区分groupby＞
グループ化というのは、割と使いたい場面があると思います。
SQL文ではありません。
順次走査で情報を縮約するので、並べ替えしてないとキーが再出現します。
それに、グループの集計して個数を数えたり、小計を出すわけでもありませんのでご注意。
イテラブルL（文字列やリスト）に対して、
itertools.groupby(L, key=None)：
(キーk,グループgを返すイテレータ)のタプル列を作成します。
次の例は動作イメージです。タプルの2番目の要素はリストではなくイテレタです。
# [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B
# [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D
返されるグループはそれ自体がイテレタで L を共有しています。だから、Lがもとなので、要素取り出しを先Nextに進めると、それ以前の要素であるグループは見えなくなります。
このgroupbyを使って別の関数も作れます。
from operator import itemgetter
from itertools import groupby
#反復された文字はスキップして取り出す関数。
def unique_justseen(iterable, key=None):
if key is None:
return map(itemgetter(0), groupby(iterable))
return map(next, map(itemgetter(1), groupby(iterable, key)))
キーを指定しないとき、groupby(iterable)は(キーk,グループgを返すイテレータ)列なので、itemgetter(0)つまり、タプルの先頭を取り出すと、グループのキーkだけのリストも作れます。
list(unique_justseen('AAAABBBCCDAABBB')) #['A', 'B', 'C', 'D', 'A', 'B']
キーをstr.casefoldで小文字にした文字にしたとき、groupby(iterable, key)のitemgetter(1)
より、タプルの2番目、つまりイテレタが取り出されるのですが、イテレタはもとのイテラブルL
を共有しているため、グループ先頭の位置でもとのイテラブルLから順に抜き出します。
list(unique_justseen('ABBcCAD', str.casefold) ) # ['A', 'B', 'c', 'A', 'D']
＜残高計算ができるaccumulate＞
reduceに似てますが、コマ送りでリスト化できます。
履歴つきのreduceという感じですね。走るreduce.
def accumulate(iterable, function=operator.add, *, initial=None):
アキュムレート累積は動作が単純です。
ドミノ倒しに似てます。基本、そのつど累和を求めます。
# list(accumulate([1,2,3,4,5])) → [1, 3, 6, 10, 15]
# list(accumulate([1,2,3,4,5], initial=100)) → [100, 101, 103, 106, 110 ,115]
だから、銀行の通帳で出と入りを数列にすると、残高数列が作れることになりますね。
それだけではありません。
演算する関数をoperator.mulにすれば、そのつど累積を出せますね。
list(accumulate([1,2,3,4,5], operator.mul)) → [1, 2, 6, 24, 120]
演算する関数をmaxにすれば、そのつどの最大値を出せますね。
だから、いつ一番多い入金があったのかを検索するなどにも使えそうです。
list(accumulate([3, 4, 6, 2, 1, 9, 0, 7, 5, 8], max))→ [3, 4, 6, 6, 6, 9, 9, 9, 9, 9]
＜他の小物たち＞
他にも小物が多数あります。listをかませないと、ただのイテレタだけだったりするのでご注意。
利用例を見れば、説明しなくてもわかりますね。
くわしくは、pythonのドキュメンテーションをご覧ください。
# chain('ABC', 'DEF') → A B C D E F 連結ですね。
# chain.from_iterable(['ABC', 'DEF']) → A B C D E F
# dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8 これは少し使えるかも。
# takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4 ドロップの逆ですね。
# pairwise('ABCDEFG') → AB BC CD DE EF FG
# repeat(10, 3) → 10 10 10
# starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000 これは面白い。
def take(n, iterable):
return list(islice(iterable, n))
def prepend(value, iterable):
# prepend(1, [2, 3, 4]) → 1 2 3 4
return chain([value], iterable)
def repeatfunc(function, times=None, *args):
if times is None:
return starmap(function, repeat(args))
return starmap(function, repeat(args, times))
def flatten(list_of_lists):
return chain.from_iterable(list_of_lists)
・・・・・
キリがないですね。
みんなスマートな定義ですね！
定義まで載せたのは、
関数が関数を呼ぶ、新関数をバケツリレーで作ることができる
ということを感じて欲しいからです。
純粋関数の自己増殖ワールド
ですね。
もちろん人が多数かかわっているでしょうから、自律的に増殖したわけではありませんけどね。
それだけ、役立ち、プログラマーがいじりたくなる道具が満載だということが
伝わってきますね。
課題：geogebraにあるリスト操作の小物関数をつないで新関数をつくってみましょう。
タイトル「groupbyもどきを作ろう」
list1 = { "a", "a", "x", "x", "x", "b" }
frq=Frequency(list1)# { 2, 1, 3 }
unq=Unique(list1)#{ "a", "b", "x" }
groupDeg=zip({a,b},a,unq,b,frq)
text0=""+list1+""
text1=""+groupDeg+""
text2=TableText(unq,frq,'h')