最良・平均・最悪計算量と償却解析
入力ごとの費用と、連続した操作全体に配分した費用を学びます。
説明
同じ長さの配列でも、探す値が先頭か末尾かで線形探索の比較回数は変わります。平均を求めるには、どの入力がどの確率で現れるかという条件が必要です。一方、償却解析は連続操作の総費用を数え、まれに起こる高い費用も含めて一回当たりへ配分します。
まず8要素の線形探索で最良・最悪・平均を計算します。続いて、満杯時に容量を倍増する配列へ9回追加し、各回のコピー数と総費用を表示します。確率的な平均と、操作列に対する償却費用を分けて説明します。
1成功する位置ごとの比較回数
先頭から探し、値が見つかった時点で止まる探索を考えます。8個の異なる値について、位置0なら1回、位置7なら8回です。
counts = list(range(1, 9))成功位置ごとの比較回数; list(enumerate(counts)), min(counts), max(counts)位置・最良・最悪成功時の最良は1回、最悪は8回です。入力長8という情報だけでは回数は一つに決まりません。未登録の値も最後まで調べるため8回です。
2全位置が同じ確率の場合
成功する8位置が同じ確率で選ばれる条件なら、比較回数の合計を8で割ります。
from fractions import Fraction分数を正確に計算; sum(counts)全位置の合計, Fraction(sum(counts), len(counts))一様分布の平均, float(Fraction(sum(counts), len(counts)))小数表示合計36、平均は4.5回です。一回の探索で4.5回比較するのではなく、この分布で繰り返したときの期待値です。
3位置の確率を変える
先頭に50%、残り7位置に等しく50%を割り当てます。先頭が多ければ平均回数は下がります。
weights = [Fraction(1, 2)] + [Fraction(1, 14)] * 7位置ごとの確率; sum(weights)確率の合計, sum(p*c for p, c in zip(weights, counts))重み付き平均確率の合計は1、期待比較回数は3です。最良1・最悪8が同じでも平均は変わります。平均という数値には、対象と確率分布の条件を付ける必要があります。
4容量拡張を含む書き込み回数を数える
容量1から始め、満杯なら2倍の領域へ使用中の要素をコピーします。各追加の費用は「コピーした個数+新要素の書き込み1回」とします。
def append_costs(n):n回の追加
size, capacity, trace = 0, 1, []使用数・容量・履歴
for operation in range(1, n+1):操作番号
copied = 0通常はコピーなし
if size == capacity:満杯の場合
copied = size全使用要素をコピー
capacity *= 2容量倍増
size += 1新要素を追加
trace.append((operation, size, capacity, copied, copied+1))各回の費用を記録
return trace履歴を返す容量管理の規則を固定した費用モデルです。Pythonの実際のlistの拡張倍率やメモリ確保時間を測るものではなく、コピーが発生する回と全体の合計を調べます。
59回の追加を表示
列は操作番号・使用数・容量・コピー数・今回の費用です。拡張した回だけ費用が跳ね上がります。
trace = append_costs(9)9回の連続追加; print(*trace, sep='\n')各操作の費用2・3・5・9回目に拡張し、コピー数は1・2・4・8です。9回目だけ見ると費用9ですが、直前の6・7・8回目は各1です。
6書き込み回数を全操作で平均する
9回分のコピー合計と書き込み合計を足し、9で割ります。
copy_total = sum(row[3] for row in trace)全コピー数; total = sum(row[4] for row in trace)新要素の書き込みも含む; copy_total, total, Fraction(total, len(trace))合計と一操作当たりコピー15回、総費用24、平均すると8/3です。これは成功位置の確率を仮定した平均ではなく、この9操作全体の費用を配分した値です。
7追加回数を増やす
8・9・16・17・1000回で、最も高い一回と一操作当たりの総費用を比べます。
[(n, max(row[4] for row in append_costs(n)), round(sum(row[4] for row in append_costs(n))/n, 3)) for n in [8, 9, 16, 17, 1000]]操作数・単発最大・配分費用拡張直後の一回の費用は大きくなりますが、一操作当たりの総費用は3未満に収まります。コピー数が1+2+4+…と増えるため、最後までのコピー合計は2n未満、新要素n回を合わせても3n未満です。
81個ずつ拡張した場合
満杯になるたび容量を1だけ増やすと、n回までに0+1+…+(n-1)個をコピーします。倍増との違いを計算します。
[(n, sum(range(n)), sum(row[3] for row in append_costs(n))) for n in [8, 16, 100]]操作数・1個拡張・倍増のコピー合計1個ずつ拡張するコピー合計はn(n-1)/2で二乗になります。倍増は空き領域を持つ代わりに拡張回数を減らし、一連の追加に対する費用を抑えます。
まとめ
最良・最悪は入力条件で変わり、平均には入力の確率分布が必要です。
償却費用は連続操作の総費用を一回当たりへ配分します。単発の最悪費用とは異なります。
容量倍増ではコピー合計を線形に抑えられ、追加一回当たりの償却費用は定数になります。
操作履歴と解説を振り返れます。
Python 3
counts = list(range(1, 9)); list(enumerate(counts)), min(counts), max(counts)([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8)], 1, 8)
from fractions import Fraction; sum(counts), Fraction(sum(counts), len(counts)), float(Fraction(sum(counts), len(counts)))(36, Fraction(9, 2), 4.5)
weights = [Fraction(1, 2)] + [Fraction(1, 14)] * 7; sum(weights), sum(p*c for p, c in zip(weights, counts))(Fraction(1, 1), Fraction(3, 1))
def append_costs(n):
size, capacity, trace = 0, 1, []
for operation in range(1, n+1):
copied = 0
if size == capacity:
copied = size
capacity *= 2
size += 1
trace.append((operation, size, capacity, copied, copied+1))
return tracetrace = append_costs(9); print(*trace, sep='\n')(1, 1, 1, 0, 1) (2, 2, 2, 1, 2) (3, 3, 4, 2, 3) (4, 4, 4, 0, 1) (5, 5, 8, 4, 5) (6, 6, 8, 0, 1) (7, 7, 8, 0, 1) (8, 8, 8, 0, 1) (9, 9, 16, 8, 9)
copy_total = sum(row[3] for row in trace); total = sum(row[4] for row in trace); copy_total, total, Fraction(total, len(trace))(15, 24, Fraction(8, 3))
[(n, max(row[4] for row in append_costs(n)), round(sum(row[4] for row in append_costs(n))/n, 3)) for n in [8, 9, 16, 17, 1000]][(8, 5, 1.875), (9, 9, 2.667), (16, 9, 1.938), (17, 17, 2.824), (1000, 513, 2.023)]
[(n, sum(range(n)), sum(row[3] for row in append_costs(n))) for n in [8, 16, 100]][(8, 28, 7), (16, 120, 15), (100, 4950, 127)]
演習完了