探索問題
配列 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]
と target0
が j
に依存しないことから
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]
と target0
を for (j)
の外に追い出してみる。これで定数倍早くしてみた ... と言っても参照と加算を に減らしただけであるため、さほど速くはならない。
しかし、変形してみると 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;
と (添字範囲の意訳を含みつつ) 変形してみる。探索範囲が i
は 0 ~ n - 2
から 0 ~ n - 1
に、j
は i + 1 ~ n - 1
から 0 ~ n - 1
に広がっているにもかかわらず、爆速になった!
計算量を と減らせるアルゴリズムを採用したことによる威力。。。たまには LINQ から離れてプリミティブな手続型で書くのも楽しい。