こんな問題が出てきたらあなたはどうするだろうか？
引用元：長い長い数列
数列 A = (A_1, A_2, …, A_n) と数列 B = (B_1, B_2, …, B_m) が与えられる。
n 行 m 列のマス目に | A_i – B_j | を書き込む。これらを小さい順に並べたとき k 番目にくる値を求めよ。
ただしnとmの取り得る最大値は30,000である。
このような問題です。nとmは最大で30,000ということはマスは最大900,000,000個存在することになります。一応intの範囲内なのが唯一の救いです。
数列が短ければどうやってでも解けるのだが
どうやって考えればよいでしょうか？ まずは普通の考え方。
実際に各マスに入る数をひとつずつ計算していきます。
絶対値がついているため単なる引き算と比べて時間がかかります。引き算であれば2800ms（たくさん計算すると結構時間がかかります）ですが、Math.Abs(ns[x] – ms[y])をすべて計算しようとすると6600msかかります。ソートしたいのでこれらをリストに格納してソートします。すると全部で96000msかかりました。1分以上かかるというのです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Program { static void Main() { // 実際に問題で使う数列をふたつ作り、乱数を格納しておく // この部分は処理時間としてカウントしない int n = 30000; int m = 30000; Random random = new Random(); int[] an = new int[n]; int[] bm = new int[m]; for (int i=0; i<n; i++) an[i] = 1 * 1000 * 1000 - random.Next(2 * 1000 * 1000); for (int i = 0; i < m; i++) bm[i] = 1 * 1000 * 1000 - random.Next(2 * 1000 * 1000); // 巨大な数列の作成完了。ここから処理にかかる時間を計測してみる System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); List<int> vs = new List<int>(); for (int y = 0; y < m; y++) { for (int x = 0; x < n; x++) { //_ = an[x] - bm[y]; // 2800ms //_ = Math.Abs(an[x] - bm[y]); // 6600ms vs.Add(Math.Abs(an[x] - bm[y])); // 13600ms; } } int[] arr = vs.ToArray(); // 14900ms; Array.Sort(arr); // 96000ms sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); } } |
リストと配列の差 要素の数が増えるとその差は無視できない
鳩でもわかるC#管理人には配列よりもリストを使いたがる悪いクセがあります。
そこで最初から配列に格納してしまえばリストに格納していくより処理速度は速くなります。計算が終わってループを抜けるまでにかかった時間は9700ms。リストに格納し終えたときの時間は13600msだったのでかなり改善されています。
しかしそのあとソートの処理が必要です。この部分は同じなのでやはり1分以上かかってしまいます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Program { static void Main() { int n = 30000; int m = 30000; // テストの使用する数列生成の処理は省略 System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); int[] arr = new int[n * m]; int index = 0; for (int y = 0; y < m; y++) { for (int x = 0; x < n; x++) arr[index++] = Math.Abs(an[x] - bm[y]); } // ループを抜けたとき 9700ms。リストを使ったときは13600msかかっていたので大きな差です。 Array.Sort(arr);// ここで時間がかかる sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); } } |
いかにして計算量を減らすか？
この問題はランクアップ問題集（ユーザー同士で解答を教え合いコードを公開することが許されている）の二分探索カテゴリ内のものであり、二分探索をうまくつかって処理時間5秒以内に答えを導き出すというものです。
解説には以下のようなことが書かれています。
数列の k 番目に小さい値は、「数列に x 以下の値が k 個以上含まれるような値 x の最小値」と言い換えることができる。言い換えたあとの問題には、数列に x 以下の値が k 個以上含まれているならば、x ≦ y を満たすすべての y について、数列に y 以下の値が k 個以上含まれているという単調性がある。だから二分探索によりこの境界を求めれば良い。
とのことです。
改善されたコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Program { static void Main() { int n = 30000; int m = 30000; int k = 10 * 10000; // 先頭から10万番目の値を取得する // 実際に問題で使う数列をふたつ作り、乱数を格納しておく // この部分は処理時間としてカウントしない int[] an = new int[n]; int[] bm = new int[m]; { Random random = new Random(); for (int i = 0; i < n; i++) an[i] = 1 * 1000 * 1000 - random.Next(2 * 1000 * 1000); for (int i = 0; i < m; i++) bm[i] = 1 * 1000 * 1000 - random.Next(2 * 1000 * 1000); } // 巨大な数列の作成完了。ここから処理にかかる時間を計測してみる System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); int left = -1, right = 200000000; while (right - left > 1) { int mid = (left + right) / 2; int smaller = 0; for (int i = 0; i < n; i++) smaller += UpperBound<int>(bm, an[i] + mid) - LowerBound<int>(bm, an[i] - mid); if (smaller < k) left = mid; else right = mid; } Console.WriteLine(right); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); } } |
上記コード内で使われているLowerBoundメソッドとUpperBoundメソッドを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Program { public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer) { int low = start; int high = end; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (comparer.Compare(arr[mid], value) < 0) low = mid + 1; else high = mid; } return low; } //引数省略のオーバーロード public static int LowerBound<T>(T[] arr, T value) where T : IComparable { return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default); } public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer) { int low = start; int high = end; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (comparer.Compare(arr[mid], value) <= 0) low = mid + 1; else high = mid; } return low; } //引数省略のオーバーロード public static int UpperBound<T>(T[] arr, T value) { return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default); } } |
これだと約200msで結果が出力されます。
