アルゴリズム遅延

アルゴリズム遅延（）はアルゴリズムに内在する待ち時間である。
概要.
プログラムはアルゴリズムからなり、アルゴリズムが計算機によって処理されることで実行される。計算処理には当然時間がかかるため、プログラムの開始から実行完了には遅延（レイテンシ）が発生する。しかし無限の能力をもつ計算機（=処理遅延0秒）を仮定してもレイテンシが発生する、すなわちアルゴリズムそのものに由来してレイテンシが発生する場合がある。このアルゴリズムに内在する遅延をアルゴリズム遅延という。
例えば2つの音声加工アルゴリズム「A: 音量倍増」と「B: ノイズ除去」を考える。Aの音量倍増では時刻 formula_1 の入力信号を2倍にして即返せばよいので、無限の計算能力があれば即座に出力できる。Bのノイズ除去の場合、時刻 formula_1 の入力信号が formula_3 のとき、この1点だけを見てもどの程度ノイズが乗っているかは判別できない。ノイズ検出にはある程度の時間区間（ブロック）を見る必要があり、そのために信号を一定時間貯める必要がある。つまりBでは処理そのものに追加してアルゴリズムのための信号蓄積が必要であり、たとえ無限の処理能力があっても信号が貯まるまでの待ち時間がかかる。ゆえにBのアルゴリズムはブロック長分の遅延を必ずもつ、すなわちアルゴリズム遅延をもつことになる。
アルゴリズム遅延はリアルタイム情報処理において重要である。例えばボイスチャットではリアルタイムに自分の音声を圧縮、ネットワーク転送し、相手方で伸展して音を届ける。経験的に知られているように、遅いマシンやネットワークを利用すると相手の声が遅れて聞こえ、コミュニケーションを阻害してしまう。しかし超高性能のマシンとネットワークを利用したとしても、圧縮伸展アルゴリズムが大きなアルゴリズム遅延をもっていると音が遅れて聞こえてしまう。なぜならアルゴリズム遅延は処理能力に依存しない、それ以上下げることのできない遅延だからである。音声圧縮伸展アルゴリズムすなわち音声コーデックの分野ではこのような低遅延リアルタイム用途を意識してアルゴリズム遅延を最小化できるコーデックが多数発表されている（例: Opus）。
アルゴリズム遅延はアルゴリズムが規定する入力形式に強く依存する。入力形式には時間に依存するストリームや時間に依存しないバッチなどがある。例えば上記アルゴリズムBはリアルタイム処理用のストリーム入力を前提としているため、ストリームからブロック長分貯めるためのアルゴリズム遅延が発生している。一方、ブロック単位のノイズ除去をオフライン用のバッチ入力に適用するとする。その場合、全ての入力が既に揃っている、すなわち全ての信号が「既に貯まっている」状態で処理を開始できる。ゆえに信号蓄積にかかる遅延が0になってアルゴリズム遅延が0になる。このような背景から、通話などのリアルタイム用途ではアルゴリズム遅延が重視され、保存用圧縮などの非リアルタイム用途では相対的に重視されない傾向がある。
アルゴリズムの実処理（実行）にかかる遅延は処理遅延と呼ばれる。処理遅延は計算機の性能や実装の質により左右される。
要因.
アルゴリズム遅延は様々な要因（手法）により決定される。以下はその一例である。
先読み.
アルゴリズム遅延の要因の1つが先読み/前方参照（）である。時刻 formula_1 の入力信号 formula_5 を処理する際、時刻 formula_6 の情報を利用することでより良い formula_5 の処理をできる場合がある。この先データアクセスが先読みである。先読みをおこなう場合、formula_5 を処理するために formula_9 までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、formula_10 サンプルの先読みは formula_10 のアルゴリズム遅延をもたらすことになる。アルゴリズムを設計する際には、先読みで得られる出力の質向上と遅延増大のトレードオフを理解する必要がある。
時刻 formula_12 すなわち過去の信号を後読み（）することは一般にアルゴリズム遅延へは影響しない。なぜならストリーム入力であっても過去の入力は既に手元にあるからである。formula_10 を大きくすることはむしろ処理量の増大による処理遅延と質の兼ね合いになる。
ブロック処理.
アルゴリズム遅延の要因の1つがブロック処理である。ブロック処理では時刻 formula_1 の入力信号 formula_5 を逐次処理するのではなく、formula_5 ~ formula_9 を1かたまりとしこの単位で一括処理する。次の処理では時刻を formula_18 進めた formula_19 ~ formula_20 を同様に一括処理する。処理単位はブロック、"フレーム"、ウィンドウなどと、間隔 formula_18 はホップ長（）やストライド（）と呼ばれる。ブロック長 formula_10 とホップ長 formula_18 は必ずしも一致しない。
formula_24 のブロック処理では、ブロック先頭 formula_5 を処理するためにブロック末端 formula_19 までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、ホップ長 formula_18 のブロック処理は入力 formula_28 に「最大で」 formula_18 のアルゴリズム遅延をもたらす。「最大」なのはサンプル位置によりアルゴリズム遅延が異なるからである。ブロック末端 formula_19 の視点でみると取り込まれた瞬間に処理されるためブロック処理のアルゴリズム遅延は0である。ブロック単位でみた遅延は最大値たる formula_18 になる。
formula_32 の場合、ブロック処理を出力の視点でみると、ホップ長 formula_18 分の出力を一括で出力している。formula_32 で出力長以上の入力を取りこんでいるということは、ブロック内での先読み/後読みをおこなっていることになる。つまり formula_1 ~ formula_36 を出力するために formula_37 ~ formula_38 を入力している（formula_39） 。アルゴリズム遅延に影響するのは先読みであるため、ブロック単位でみたアルゴリズム遅延は formula_40 になる。
またブロック処理と先読みを組み合わせ、ブロック formula_41 の処理にブロック formula_42 を必要とさせることもできる。その場合は formula_18 単位で必要な入力が増えていくため、アルゴリズム遅延が formula_44 になる。