Procedural Programming w/ C# -アルゴリズムの威力

探索問題

配列 val[] に入っている 2 値の差がある定数 target0 に一致するか、という問題に直面し、まずは愚直にこんなコードを書いてみた。

// C# code

long[] val     = new long[n]; // val[0 .. n - 1] には単調増加な正値が入っている
long   target0 = ...;         // ある正値

for (int i = 0; i < n - 1; ++ i) {
  for (int j = i + 1; j < n; ++ j) {
    if (val[j] - val[i] == target0)
      return true;
  }
}

これが非常に遅い。速くできないかと思い、よく見てみると、val[i]target0j に依存しないことから

for (int i = 0; i < n - 1; ++ i) {
  for (int j = i + 1; j < n; ++ j) {
    if (val[j] == target0 + val[i])
      return true;
  }
}

と変形して、さらに

for (int i = 0; i < n - 1; ++ i) {
  var target1 = target0 + val[i];

  for (int j = i + 1; j < n; ++ j) {
    if (val[j] == target1)
      return true;
  }
}

val[i]target0for (j) の外に追い出してみる。これで定数倍早くしてみた ... と言っても参照と加算を  \frac{(n - 1) \cdot (n - 2)}{2} \rightarrow n - 2 に減らしただけであるため、さほど速くはならない。

しかし、変形してみると for (j)ただの線形探索をしているだけということに気付く。val[] は単調増加 (ソート済み) なので ... 二分探索が使える!

for (int i = 0; i < n - 1; ++ i) {
  var target1 = target0 + val[i];

  if (Array.BinarySearch(val, target1) >= 0)
    return true;
}

for (j) を書き直してついでに

for (int i = 0; i < n; ++ i)
  if (Array.BinarySearch(val, target0 + val[i]) >= 0)
    return true;

と (添字範囲の意訳を含みつつ) 変形してみる。探索範囲が i0 ~ n - 2 から 0 ~ n - 1 に、ji + 1 ~ n - 1 から 0 ~ n - 1 に広がっているにもかかわらず、爆速になった!

計算量を  O(N^2) \rightarrow O(N \cdot log N) と減らせるアルゴリズムを採用したことによる威力。。。たまには LINQ から離れてプリミティブな手続型で書くのも楽しい。