集合演算

ある記号があるかないか。記号の組のなかに求める記号が含まれているか。記号の組ふたつのなかに共通の記号は存在せずお互いに独立しているか。

そういう記号のある・なしを考える、集合論と呼ばれる分野がある。

プログラムでももちろん扱うことができて、うまく応用できると処理を効率化できたりもする。だからたまに作ってみたくなる。

代表的な集合操作は三つ。
１　ふたつの集合すべての記号をあつめる「和集合」を取る操作（一方にあれば、そして両方に含まれていてもよい）、
２　集合の共通部分「積集合」を取る操作（両方に含まれる記号だけをあつめる）、
３　一方の集合から他方の集合に含まれるものをすべて取り除く「差集合」を取る操作。

以下、 values が集合の要素「元」を集めるオブジェクト。
元は N 種類あるものとして、 values にはそのうち n 個（0 <= n ⋀ n < N）の互いに相異なる元を持ち vs で管理する。そして vs は昇順に整列されているとする。

すると和集合、積集合、差集合は、 m を集合 A の元の数、 n を集合 B の元の数として、それぞれ最大 m + n 回の比較で求められる。

struct values {
  unsigned n;
  value_t vs[N];
};

// R = A + B
struct values *values_union(
  struct values *r,
  const struct values *a,
  const struct values *b)
{
  const value_t *it_a = a->vs;
  const value_t *it_b = b->vs;
  value_t *out = r->vs;
  while (it_a != a->vs + a->n && it_b != b->vs + b->n) {
    if (*it_a == *it_b) {
      *out++ = *it_a++;
      ++it_b;
    } else {
      if (*it_a < *it_b) {
        *out++ = *it_a++;
      } else {
        *out++ = *it_b++;
      }
  }
  while (it_a != a->vs + a->n) {
    *out++ = *it_a++;
  }
  while (it_b != b->vs + b->n) {
    *out++ = *it_b++;
  }
  r->n = out - r->vs;
  return r;
}

// R = A * B
struct values *values_intersection(
  struct values *r,
  const struct values *a,
  const struct values *b)
{
  const value_t *it_a = a->vs;
  const value_t *it_b = b->vs;
  value_t *out = r->vs;
  while (it_a != a->vs + a->n && it_b != b->vs + b->n) {
    if (*it_a == *it_b) {
      *out++ = *it_a++;
      ++it_b;
    } else {
      if (*it_a < *it_b) {
        ++it_a;
      } else {
        ++it_b;
      }
  }
  r->n = out - r->vs;
  return r;
}

// R = A - B
struct values *values_difference(
  struct values *r,
  const struct values *a,
  const struct values *b)
{
  const value_t *it_a = a->vs;
  const value_t *it_b = b->vs;
  value_t *out = r->vs;
  while (it_a != a->vs + a->n && it_b != b->vs + b->n) {
    if (*it_a == *it_b) {
      ++it_a;
      ++it_b;
    } else {
      if (*it_a < *it_b) {
        *out++ = *it_a++;
      } else {
        ++it_b;
      }
  }
  while (it_a != a->vs + a->n) {
    *out++ = *it_a++;
  }
  r->n = out - r->vs;
  return r;
}

＊　＊　＊

こういうのを考えては実装して動かして確かめることが、ほんとうに好き。だけれど、この程度の処理はたいていの言語に組み込みで実装されている。だからふと我に返ってあまりに非生産的だと悲しくなる。

＊　＊　＊

ところでそれぞれの主たる while 文は次のように書き換えてもよい。

  // A + B
  while (it_a != a->vs + a->n && it_b != b->vs + b->n) {
    const value_t va = *it_a, vb = *it_b;
    *out = va;
    out += 1;
    it_a += va == vb || va < vb;
    it_b += va == vb || va > vb;
  }

  // A * B
  while (it_a != a->vs + a->n && it_b != b->vs + b->n) {
    const value_t va = *it_a, vb = *it_b;
    *out = va;
    out += va == vb;
    it_a += va == vb || va < vb;
    it_b += va == vb || va > vb;
  }

  // A - B
  while (it_a != a->vs + a->n && it_b != b->vs + b->n) {
    const value_t va = *it_a, vb = *it_b;
    *out = va;
    out += va < vb
    it_a += va == vb || va < vb;
    it_b += va == vb || va > vb;
  }

それぞれの違いは、書きだす位置を変更するかどうかのロジックだけ。
どちらがわかりやすいだろう？

（１月３０日、修正。初出時 it_a += *it_a == *it_b || *it_a < *it_b; it_b += *it_a == *it_b || *it_a > *it_b; としていましたが、これだと it_b の更新前に it_a が変化することがあり問題になるため、参照を外した値を先に保存するよう変更しました）