アルゴリズムの処理とデータ管理

要点と定義

アルゴリズムは、入力や現在の状態から目的の結果を得るための、順序立った処理手順です。処理を設計するときは、何を入力として受け取り、どの状態を保ち、どの条件で処理を続けたり終えたりするかを明確にします。順次処理、条件分岐、繰返しは、手順を組み立てる基本要素です。

繰返しでは、カウンタや処理位置がどの対象を指すかを確認します。たとえば、表のデータ行を順に読む位置と、結果を書き出す行の位置は役割が違います。年ごとの集計では、販売データを走査し、商品コードが一致する間に単価と数量の積を合計し、年ごとの出力位置を次の年へ進めます。出力行の間隔が5行なら、基準行からのオフセットも年ごとに5増やします。条件、参照位置、更新処理がそれぞれ役割に合っていることが正しい集計の条件です。

処理量を考えるときは、対象となるデータの数を処理手順と対応づけます。マークアンドスイープ方式では、マーク処理は到達可能な使用中のセルをたどるため、使用中のセル数を L とすると処理量は L に比例します。スイープ処理はメモリ領域の全セルを走査するため、全セル数を M とすると処理量は M に比例します。未使用セルがない状況では、使用中でない M−L 個のセルを回収して再利用できます。

データを詰め直す処理では、データの並びと、その位置を指す参照情報を一緒に保つ必要があります。たとえば、文字列の長さ情報を1要素、その後に文字列を格納するなら、1件の格納量は「長さ＋1」です。格納済み要素数を表す位置から書き始め、長さ情報を書いた後に文字列分だけ位置を進めます。参照されているメモだけを順番に詰め直す場合は、各メモの新しい開始位置も参照配列に記録し直します。

適用条件と例

配列の要素を削除して後続の要素を詰める場合は、削除位置の次の要素から順に一つ前へコピーします。削除位置を p とすれば、コピー元は p+1 から始まります。たとえば [赤, 青, 黄] の青を削除するなら、黄を青の位置へ移し、末尾側の有効件数を1減らします。削除位置からコピーを始めると、削除対象より前の要素を上書きしてしまいます。

要素を別の位置へ移すときは、コピーによる上書きで未処理の値を失わない向きに走査します。後ろの要素を前へ移す場合は、移動元から移動先の次の位置まで逆順にずらし、退避した値を移動先に置きます。前の要素を後ろへ移す場合は、移動元から移動先の一つ前まで順方向にずらします。