プログラミング作法 第２章 アルゴリズムとデータ構造 ２．６ 配列の伸張

　ただ、個数は可変だが、要素数の少ない物事を管理したいケースはよくある。そういう場合には依然として配列が最善の選択肢となり得る。その際に、配列は割り当てコストを最小限に抑えるためにチャンク単位でサイズ変更する必要があるし、物事をすっきりさせるために配列を、配列の管理に必要な情報と、ひとまとめにする必要がある。

チャンク(chunk)：大塊
Cによる配列伸張のプログラムに対して

reallocを呼び出すたびに要素１個分ずつしか配列を伸張させないと、性能がＯ(n^2)になってしまう。しかし上のコードのようにreallocを実行するたびに(要素数の)サイズを２倍にすることで、個々の要素のコピーに必要なコストの期待値が一定に保たれる。

Cによる配列からのデータ削除のプログラムに対して

　一方、名前を削除する作業はこれほど素直にはいかない。配列に残った隙き間をどう扱うかを判断しなければならないからだ。要素の順序がどうでもよければ、最後の要素を隙き間に入れ換えるのが一番簡単だろう。ところが順序を維持したいときには、隙き間以降の要素の位置を１個ずつずらさなければならない。

順序がどうでもいい場合は、削除した位置と最後の位置のデータを交換ということ。順序を維持する場合には、以下に示すようにデータの移動が必要。

　ＡＮＳＩＣ標準にはmemcpy関数とmemmove関数が定義されている。前者は高速だが、コピー元とコピー先が重なっているとメモリが上書きされてしまう。後者は遅いが、どんな場合でも正しく動く。正しさと速度を天秤にかける負担をプログラマに要求するのは間違っており、本来は１種類の関数しか存在すべきでない。最初から１種類しか存在しないと思って、いつでもmemmoveを使うようにすること。

我々がmemmoveを使うほうがいいと思う理由は、要素を間違った順序でコピーしてしまうというありがちなミスを防止できるからだ。

　配列要素を移動させるやり方以外に、削除された要素を未使用としてマークする方法もある。その場合、新しい項目を追加したいときにはまず未使用スロットを検索してみて、それが全く存在しなかったときに初めてベクタ(配列)を伸張させることになる。

　配列はデータをまとめるもっとも単純な手段だ。効率的で便利なインデックスつき配列がほとんどの言語に用意されていたり、文字列が文字の配列として表現されるようになっているのは決して偶然ではない。配列は簡単に使えるし、どの項目にもＯ(1)でアクセスできるし、二分探索やクイックソートと相性がいいし、領域のオーバーヘッドもほとんどない。固定サイズのデータ集合や要素数が少ないとわかっているデータ集合の場合には、配列にかなうものはない。とくに前者の場合には、コンパイル時にデータ集合を作成するのも可能だ。しかし配列の値の集合が変化する場合には管理作業が高くつくことがあるので、要素数が予測できなかったり膨大になる可能性があったりするようなケースでは、おそらく別のデータ構造を使ったほうがいいだろう。

問題２−５
わざわざ返却する必要はないと思う。理由は、返却するさいにもreallocを使えば内部的にメモリコピーが行われてそれだけ性能が落ちる可能性があるからだ。したがって私の考えでは、一度確保した配列領域を返却するタイミングは、配列の未使用要素が配列全体の大部分をしめる場合になる。要素がたりないときに２倍することを考えれば、使用率が２５％以下になったときに、配列の大きさを０．５倍する程度でよいと思う。
問題２−６
削除済み項目に対して未使用をマークする方式に対応したソースは以下のようになると思う。

/* delname:最初にマッチするnamevalをnvtabから除去し、未使用のマークを設定 */
int delname(char *name)
{
  int i;
  for (i = 0; i < nvtab.nval; i++) {
    if (strcmp(nvtab.nameval[i].name, name) == 0) {
      nvtab.nameval[i] = NULL; /* 未使用のマークとしてNULLを使用 */
      nvtab.nval--; 
      return 1;
    }
  }
  return 0;
}

/* addname:新しい名前と値をnvtabに追加 */
int addname(Nameval newname)
{
  Nameval *nvp;
　int i;
  if(nvtab.nval >= nvtab.max) { /* 伸張 */
    nvp = (Nameval *)realloc(nvtab.nameval, (NVGROW*nvtab.max) * sizeof(Nameval));
    if (nvp == NULL) {
      return -1;
    }
    for (i = nvtab.max; i < (nvtab.max * NVGROW); i++) {
      nvp[i] = NULL;
    }
    nvtab.max *= NVGROW;
    nvtab.nameval = nvp;
  }
  /* 未使用の要素の探索 */
　for (i = 0; i < nvtab.max; i++) {
    if(nvtab.nameval[i] == NULL) {
      nvtab.nameval[i] = newname;
      return nvtab.nval++;
    }
  }
  return -1;
}

delname()で削除するさいに、削除対象にNULLを設定することで削除とする。この変更にともなって、addname()で「一番最初」にmalloc()で確保していた領域を、addname()以外で(例えばinitname()とかで)確保する必要がある。また、addname()で追加するさいに領域の探索処理が加わることになる。