AtCoder Practice BをJavascriptで解いてみる
※ネタ記事です。息抜きにでもなれば幸いです。
最近はJavascriptに慣れすぎて、他の言語を使うのがおっくうになってしまった。 今回はJavascriptでAtCoderのPractice B問題を解いてみようとおもう。
問題の原文は是非公式でみて欲しいが要約するとこうだ。
- 長さ26の配列を100回の大小比較でソートせよ
- 長さ5の配列を7回の大小比較でソートせよ
幸いJavascriptには既に配列のソートが用意されている。 というわけでこうだ。
const array = [{label: 'A'}, {label:'b'}, .... ]; const compare = (a, b) => { return query(a, b) === '<' ? 1 : -1; }; const result = array.sort(compare);
とおもったらWA（Wrong Answer）の嵐。
ソートが出来ていないわけではないが、ここでソート回数制限に気が付く
たしかNode.jsのソート （Array.prototype.sort）はクイックソートで実装されているはず。 試しにテストをつくって実行してみる。
const array = new Array(26); for(let i=0; i<array.length; i++) array[i] = Math.random(); let count = 0; const compare = (a, b) => { count++; return a-b; }; array.sort(compare); console.log(count);
そうすると、だいたい120～160程度の比較が実行されている。 ものぐさせずに計算量を調べてみる。 クイックソートの計算量は最良で n×ln(n) だが最悪で n2 になる。 n = 5 なら 8 ～ 25, n=26 なら 85 ～ 676 になる。
8?! と思うも知れないが、これはあくまでも計算量のオーダーであって、実計算量とはまた異なる。 想像してみればわかるが3つのものを、クイックソートする時に、最良は比較2回でソートは完了する。 3 × ln 3 = 3.296 ... と比較してもわかるが、実際の計算量はそのオーダーから定数が足し引きされる。
というわけで、この問題は最悪計算量を優先して、ヒープソートでも実装すればいいということだ。 で、こうなりました。
Array.prototype.bucket = function (callback) { if (!callback) callback = (a, b) => { if (a < b) return 1; if (a > b) return -1; return 0; } if (typeof callback !== 'function') throw new Error('callback require type of function'); const full = []; const push = (sub, array) => { if (sub.length <= 1) full.push(array.concat(sub)); else { for (let i = 0; i < sub.length; i++) { const t = sub.filter((x, j) => j !== i); push(t, array.concat([sub[i]])); } } }; push(this.map((x, i) => i), []); // console.log(full); const pairs = []; for (let i = 0; i < this.length; i++) { for (let j = i + 1; j < this.length; j++) { pairs.push([i, j]); } } // console.log(pairs); const findIndex = (array, value) => { let i = 0; while (array[i++] !== value); return i - 1; }; const run = (pair, current) => { if (current.length <= 1) return current[0]; const result = pair.map(x => { return Math.abs(current.length / 2 - current.filter(y => y.indexOf(x[0]) - y.indexOf(x[1]) > 0).length); }); const min = Math.min.apply(null, result); const index = findIndex(result, min); const [a, b] = [pair[index][0], pair[index][1]]; const t = callback(this[a], this[b]) || -1; return run( pair.filter(x => x.indexOf(a) < 0 || x.indexOf(b) < 0), current.filter(x => (x.indexOf(a) - x.indexOf(b)) * t > 0) ); }; const index = run(pairs, full); if (!index) throw new Error('can not sort'); return index.map(x => this[x]); };
まず、与えられた配列のソート結果の全候補を列挙する。 変数 full がこれに相当し、配列の長さが3なら [[0,1,2] [0,2,1] [1,0,2] [1,2,0] [2,0,1] [2,1,0]] となる。
次に、実際に比較する「2つの数字の組み合わせ」を列挙する。 これは変数 pairs で次のようになる。 [[0, 1] [0, 2] [1, 2]]
ここまででまだ一度も比較を実行していない。 これだけそろえば、どの数字を比較すれば、最も次の候補を減らせるかを探索すればいい。
例えば [0,1] のペアで比較をすると、先の full を2つに分割されて、 0 > 1 :: [0,1,2], [0,2,1], [2,0,1] 0 < 1 :: [1,0,2], [1,2,0], [2,1,0] となる。
実際に比較した結果をもとに候補を絞っていけばいい。
具体的には配列 [100, 7, 256] が与えられたとき、各ペアに対して
[0,1] で比較すると次の候補は 1. [0,1,2], [0,2,1], [2,0,1] 2. [1,0,2], [1,2,0], [2,1,0]
[0,2] で比較すると次の候補は 1. [0,1,2], [0,2,1], [1,0,2] 2. [1,2,0], [2,0,1], [2,1,0]
[1,2] で比較すると次の候補は 1. [0,1,2], [1,0,2], [1,2,0] 2. [0,2,1], [2,0,1], [2,1,0]
となり、どのペアで比較しても、候補は二分される。 [0,1]で比較すると、実際の数字は 100 > 7 であるため、次の候補は [[1,0,2], [1,2,0], [2,1,0]]に絞られる。
2回目の比較をしたときに候補の増減を調べると
[0,1] で比較すると次の候補は 1. [] 2. [1,0,2], [1,2,0], [2,1,0]
[0,2] で比較すると次の候補は 1. [1,0,2] 2. [1,2,0], [2,1,0]
[1,2] で比較すると次の候補は 1. [1,0,2], [1,2,0] 2. [2,1,0]
となる。ここで、優先すべきは最悪計算量を減らすことであるため、比較の結果のばらつぎが なるべく少ない比較のペアを選びたい。[0, 2]と[1,2] ではどちらもばらつきは 1 であるためどちらを選んでもいい。 実際に[0,2]で比較をすれば 100 < 256 であるため、次の候補は [[1,2,0], [2,1,0]] に絞られる。
このような戦略で行けば、常に最小の比較回数で、ソートが完了する。 試しに次のコードで比較回数を調べてみる。
require('../lib/ArrayPrototype'); const n = 10; const a = new Array(n); for (let i = 0; i < n; i++) a[i] = ({ name: `N${i}`, value: Math.random() }); let count = 0; const b = a.bucket((a, b) => { count++; return a.value - b.value }); console.log(`Count: ${count}`); b.map(x => console.log(x.value));
長さ5の配列を100回ソートしてみたが、必要な比較回数は、6～7 (ave. 6.97)となり、 目論見通り7回の比較で終了することが確かめられた。 入力に制限がない配列のソート方法としては最小の計算量となるはずだ。
それでは、提出してみよう
アルゴリズムを文字だけで説明するのって難しい 難しくない？
