時間計算量・空間計算量と並列化
結果を保存する費用と再利用の効果、並列化できない処理による速度向上の上限を学びます。
説明
処理時間を減らすために計算結果を保存すると、その分の領域が必要です。逆に、一つずつ生成してすぐ使えば保存量を減らせますが、後で再利用するときに計算し直すことがあります。時間と空間の費用は、何を何回使うかによって変わります。
二乗の合計をリストと逐次生成で計算し、同じ値を複数回問い合わせたときのキャッシュを調べます。最後に、処理時間の20%が逐次処理として残る条件で、並列数を増やしても速度が無限に上がらないことを計算します。
1全結果を保存して合計
0から9までの二乗をリストに保存します。保存した値は後から再利用できます。
values = list(range(10))入力; squares = [x*x for x in values]二乗を全て保存; squares, len(squares), sum(squares)保存値・個数・合計保存した二乗は10個、合計285です。ここで数える追加領域は二乗の結果リストです。入力valuesの領域も含めた総使用量とは分けて考えます。
2一つずつ生成する
ジェネレーター式は、次の値が必要になったときに二乗を計算します。まず3個取り出してから残りを合計します。
stream = (x*x for x in values)必要時に二乗を生成; first = [next(stream) for _ in range(3)]3個を取り出す; first, sum(stream), sum(first)+sum(squares[3:])残りと全体を照合最初は0・1・4、残りの合計は280、全体は285です。ジェネレーターは全二乗を結果リストとして保存せず、現在の位置を保持して進みます。このコマンドでは最初の3個だけ別のリストに保存しました。
3使い切った列は再生成が必要
ジェネレーターは末尾まで消費済みです。もう一度sumすると残りは0です。同じ合計を再度求めるには生成し直します。
sum(stream)消費済みの残り, sum(x*x for x in values)二乗を再計算, sum(squares)保存結果を再利用使い切ったstreamの合計は0、新しく計算した合計と保存済みリストの合計は285です。リストなら二乗結果を再利用でき、逐次生成なら保存を省ける代わりに再計算が必要になります。
4同じ値の問い合わせ
3・4・3・5・4・3の二乗を順に求めます。キャッシュなしなら6回、引数ごとに保存すれば異なる3個だけ二乗を計算できます。
requests = [3, 4, 3, 5, 4, 3]繰り返しのある要求; cache = {x: x*x for x in sorted(set(requests))}異なる入力の結果を保存; [cache[x] for x in requests], len(requests), len(cache)結果・要求数・保存数結果は9・16・9・25・16・9です。計算結果3個とキーを保存して、繰り返しを再利用しています。二乗のように軽い計算では、キャッシュ管理の方が高くつく可能性もあり、回数削減がそのまま高速化になるとは限りません。
5区間和を保存して再利用
累積和を作ると、区間の合計を二つの値の差で求められます。準備には全要素の走査とn+1個の領域が必要です。
from itertools import accumulate累積和; data = [4, 7, 2, 9, 1]入力; prefix = [0] + list(accumulate(data))先頭0を含む累積表; prefix, prefix[4]-prefix[1], sum(data[1:4])2参照の差と直接計算を照合累積和は0・4・11・13・22・23です。区間[1,4)の7+2+9=18を22-4で求められます。大量の区間問い合わせに再利用できますが、元データを変更したら影響する累積和も更新する必要があります。
6並列化できる割合
元の処理時間を1とし、20%は逐次、80%はp個で理想的に分割できるとします。並列化後の時間は0.2+0.8/pです。通信などの追加費用はこの式に含めません。
from fractions import Fraction割合を分数で計算; serial = Fraction(1, 5); parallel = 1-serial逐次20%・並列80%; [(p, float(serial+parallel/p), float(1/(serial+parallel/p))) for p in [1, 2, 4, 8]]並列数・時間・速度向上4並列で時間0.4、速度向上2.5倍です。逐次の0.2は並列数を増やしても短くならないため、4倍にはなりません。速度向上は元の時間を新しい時間で割った値です。
7並列数を増やした先の上限
並列部分の時間を限りなく0へ近づけても、逐次部分0.2が残ります。
[(p, round(float(1/(serial+parallel/p)), 3)) for p in [16, 64, 1024]]並列数を増やした速度向上, 1/serial理想的な上限1024並列でも約4.981倍で、上限は5倍です。これが固定した仕事量と逐次割合に対するAmdahlの法則です。実際には同期・通信・負荷の偏りなどで、さらに時間が加わります。
8逐次部分を減らした場合
逐次割合を20%から5%へ改善した条件で、8並列と上限を再計算します。
[(s, round(float(1/(s+(1-s)/8)), 3), 1/s) for s in [Fraction(1, 5), Fraction(1, 20)]]逐次割合・8並列の倍率・上限8並列の速度向上は約3.333倍から5.926倍へ、上限は5倍から20倍へ変わります。並列数だけでなく、逐次部分を減らす設計も結果に影響します。保存量・再計算・並列化を、同じ仕事量と条件で比較することが必要です。
まとめ
結果を保存すると再利用でき、逐次生成すると全結果の保存を省けます。再利用回数で利点が変わります。
キャッシュや累積和は追加領域と準備を使って、繰り返す処理を減らします。
固定した仕事量では、並列化できない部分が速度向上の上限になります。
操作履歴と解説を振り返れます。
Python 3
values = list(range(10)); squares = [x*x for x in values]; squares, len(squares), sum(squares)([0, 1, 4, 9, 16, 25, 36, 49, 64, 81], 10, 285)
stream = (x*x for x in values); first = [next(stream) for _ in range(3)]; first, sum(stream), sum(first)+sum(squares[3:])([0, 1, 4], 280, 285)
sum(stream), sum(x*x for x in values), sum(squares)(0, 285, 285)
requests = [3, 4, 3, 5, 4, 3]; cache = {x: x*x for x in sorted(set(requests))}; [cache[x] for x in requests], len(requests), len(cache)([9, 16, 9, 25, 16, 9], 6, 3)
from itertools import accumulate; data = [4, 7, 2, 9, 1]; prefix = [0] + list(accumulate(data)); prefix, prefix[4]-prefix[1], sum(data[1:4])([0, 4, 11, 13, 22, 23], 18, 18)
from fractions import Fraction; serial = Fraction(1, 5); parallel = 1-serial; [(p, float(serial+parallel/p), float(1/(serial+parallel/p))) for p in [1, 2, 4, 8]][(1, 1.0, 1.0), (2, 0.6, 1.6666666666666667), (4, 0.4, 2.5), (8, 0.3, 3.3333333333333335)]
[(p, round(float(1/(serial+parallel/p)), 3)) for p in [16, 64, 1024]], 1/serial([(16, 4.0), (64, 4.706), (1024, 4.981)], Fraction(5, 1))
[(s, round(float(1/(s+(1-s)/8)), 3), 1/s) for s in [Fraction(1, 5), Fraction(1, 20)]][(Fraction(1, 5), 3.333, Fraction(5, 1)), (Fraction(1, 20), 5.926, Fraction(20, 1))]
演習完了