社長「やめ太郎くん」
ワイ「なんでっか社長」
社長「画期的なソートアルゴリズムをJavaScriptで書いたから見てくれや」
ワイ「ソートアルゴリズムちゅうのは配列を数字が小さい順に並べ替えてくれるやつでんな」
ワイ「（どうせバブルソートとかやろ）」
社長「これや」
function sleep(duration) {
return new Promise(resolve => setTimeout(resolve, duration));
}
function sleepSort(arr) {
const result = [];
return Promise.all(
arr.map(elm => sleep(elm * 100).then(() => result.push(elm)))
).then(() => result);
}
sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]).then(console.log);
// 1秒後に [1, 1, 1, 2, 3, 3, 4, 4, 6, 10] と表示される
ワイ「スリープソートやないかい！」
※この記事は全編やめ太郎さんリスペクトでお送りします。（3週間ぶり2回目）
スリープソートを読み解く
ワイ「思わず突っ込んでもうたけど何やっとんのか全然分からんで」
ワイ「スリープソートっちゅうんは寝ている間に小人がソートしてくれるっちゅうことでっか？」
社長「んなわけあるかい！」
社長「これはタイマーを使うことで複雑なロジックを書かんでもソートができる画期的なアルゴリズムや」
ワイ「それだけ聞いてもどんなソートなのか全然分かりまへんわ」
社長「仕方あらねんなあ、ワイ自ら解説したるで（ワイって一人称ワイで合っとるんか？ みんな一人称同じやんけ）」
社長「まず結果の配列を用意する。これはまあええやろ」
const result = [];
社長「そして与えられた配列の各要素に対してsleep(elm * 100).then(() => result.push(elm))を実行するんや」
社長「ここでいくらか時間がかかるからそれを待つんや」
社長「Promise.allっちゅうのは全部の要素が終わるまでしっかり待つっちゅうことやな」
社長「そして全部終わったらresultを返す」
ワイ「社長アホになったんでっか？ sleepSortにreturn result;なんて書いとらんやん」
社長「お前本当にJavaScript書いとんのか？ 非同期処理なんだからPromiseに包んで値を返すのは当たり前やん」
社長「最後の.then(() => result)で処理が全部終わったらresultっちゅう結果をPromiseに包んで返すことを表しとるんや」
ワイ「（そもそもソートを非同期処理にする方がどうかしとるんちゃうか）」
ハリー先輩「（こいつソートを並列化したこと無いんか）」
ワイ「じゃあsleep(elm * 100).then(() => result.push(elm))はどういう意味でっか」
社長「sleepってのは与えられたミリ秒数だけ経ったら解決されるPromiseを返す関数や」
社長「そしてそのPromiseが解決されたらresultにelmを追加する」
社長「つまりelm * 100ミリ秒後にresultにelmを追加するっちゅうことや」
ワイ「elmってのは配列の要素やから」
ワイ「elmが1なら100ミリ秒後、2なら200ミリ秒後にresultに1とか2が追加されるわけでんな」
社長「せや」
社長「小さい数ほど先にresultに追加されるから全部追加し終えたらソートが完了しとるっちゅうわけや」
ワイ「このsleepっちゅうのはarr.mapで各要素に対して実行されとるけど」
ワイ「配列の各要素に対して順番に実行されるんでっか」
社長「ちゃうで」
社長「Promiseで表されるのは非同期処理や」
ハリー先輩「非同期処理っちゅうのは終わるまでボケっと待っとらんでもええってことやで」
社長「つまり一つ一つが終わるのを待たんでも全部同時にsleep(elm * 100)が走るんや」
ハリー先輩「つまりelm * 100秒後にresultにelmを追加するっちゅう処理が全要素同時に始まるっちゅうことや」
社長「どや、画期的やろ」
ワイ「これ負の数はどうするんでっか」
社長「適当にゲタ履かせときゃええやろ」
ワイ「1000000とか渡されたら1日以上待つんでっか」
社長「あー忙し、仕事しよ」
ワイ「社長！」
スリープソートを高速化してみた
ハスケル子「やめ太郎さん」
ワイ「何や（この筆者ハスケル子好きやな……）」
ハスケル子「スリープソートを高速化してみたんですけど」
ワイ「ほう、見せてみい」
async function sleep(duration) {
for (let i = 0; i < duration; i++) {
await null;
}
}
function sleepSort(arr) {
const result = [];
return Promise.all(
arr.map(elm => sleep(elm).then(() => result.push(elm)))
).then(() => result);
}
sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]).then(console.log);
// すぐに [1, 1, 1, 2, 3, 3, 4, 4, 6, 10] と表示される
ハスケル子「これです」
ワイ「sleep関数が変わっただけやな」
ワイ「おお、一瞬でソートが終わったで」
ワイ「でもsleep関数の意味が分からんわ」
ハスケル子「これはasync関数です」
ワイ「返り値が自動的にPromiseになるやつやな」
ハスケル子「await null;がポイントで」
ハスケル子「これは一瞬待つって意味です」
ワイ「ほお」
ハスケル子「つまりelmが1なら一瞬待って」
ハスケル子「elmが2なら二瞬、elmが3なら三瞬待ちます」
ワイ「は？」
ハスケル子「つまりelm * 100ミリ秒待つ代わりにelm瞬待つようにして高速化したんです」
ワイ「説明聞いてもやっぱり意味が分からんわ」
イベントループ
ハスケル子「最近のJavaScript処理系はイベントループという仕組みを持っています」
ハスケル子「JavaScriptは非同期といっても全部シングルスレッドで動くので」
ハスケル子「非同期処理のコールバックが呼ばれる場合は今実行している処理が終わってからそっちに移るんです」
ワイ「溜まっとる一個一個の処理をループで順番に処理していくからイベントループってわけやな」
ハスケル子「await nullはループ一周分待つってことなんです」
ワイ「はあ」
ワイ「でもそれがスリープソートと何の関係があるんや」
ハスケル子「まだ理解できないんですか…… じゃあちょっとさっきのコードを書きなおしてみましょう」
function sleep(duration) {
let i = 0;
const loop = () => {
if (i < duration) {
i++;
return Promise.resolve(null).then(loop);
} else {
return null;
}
};
return loop();
}
function sleepSort(arr) {
const result = [];
return Promise.all(
arr.map(elm => sleep(elm).then(() => result.push(elm)))
).then(() => result);
}
sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]).then(console.log);
// すぐに [1, 1, 1, 2, 3, 3, 4, 4, 6, 10] と表示される
ワイ「sleepの中がますます意味不明になったで」
ハスケル子「さっきのコードをasyncとawaitを使わずに生のPromiseを使うように書きなおしただけです」
ワイ「async/awaitが分かとっらん読者もおるかもしれんけど本題とは関係ないから省略するで」
ハスケル子「こういうふうにPromise.resolveで作られたPromiseは一瞬で解決されます」
ハスケル子「つまり、それにthenでつなげた関数はイベントループの次のループで呼び出されるんです」
ワイ「はあ」
ハスケル子「じゃあイベントループを自分で再現してみましょう」
const events = [];
// ソートの結果
const result = [];
// 最初に実行する処理を登録
events.push(() => sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]));
// ここからイベントループの処理
while (events.length > 0) {
// eventsの先頭から1つ取り出して呼び出す
const nextEvent = events.shift();
nextEvent();
}
// イベントループが終わったらresultを表示
console.log(result);
function sleep(elm, callback) {
let i = 0;
const loop = () => {
// イベントループ1回の処理
if (i < elm) {
i++;
events.push(loop);
} else {
// ループが終了したのでコールバックを呼ぶ
callback();
}
};
return loop();
}
function sleepSort(arr) {
for (const elm of arr) {
// 各elmに対する処理を実行
sleep(elm, () => result.push(elm));
}
}
ワイ「一気にコードが長くなって読むのがつらいで」
ワイ「でもイベントループっちゅうのがどこかは分かるで」
ワイ「while (events.length > 0)のところやな」
ハスケル子「そうです、イベントループはeventsに登録された関数を順番に呼び出すだけです」
ハスケル子「sleepSort関数はarrの各要素に対する処理を別々にイベントループに登録します」
ワイ「sleep(elm).then(()=> result.push(elm))がsleep(elm, ()=> result.push(elm))になっとるで」
ハスケル子「thenを実装するのが面倒なのでsleepにコールバックを渡す形にしたんです」
ワイ「sleep関数の中はPromise.resolve(null).then(loop)がevents.push(loop)に変わっとるで」
ハスケル子「Promise.resolve(null)は一瞬で解決されるので、それにthenしたloopは次のイベントループで呼び出されるんです」
ハスケル子「だから自前のイベントループを使うためにこう直しました」
ワイ「なるほどな」
スリープソートを最適化してみる
ワイ「何となく分かったから自分でちょっとコードをいじってみるで」
ワイ「まずイベントループはsleepSort関数の中に押し込んでもええやろ」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
const events = [];
for (const elm of arr) {
// 各elmに対する処理を実行
sleep(elm, () => result.push(elm));
}
while (events.length > 0) {
// eventsの先頭から1つ取り出して呼び出す
const nextEvent = events.shift();
nextEvent();
}
return result;
function sleep(elm, callback) {
let i = 0;
const loop = () => {
// イベントループ1回の処理
if (i < elm) {
i++;
events.push(loop);
} else {
// ループが終了したのでコールバックを呼ぶ
callback();
}
};
loop();
}
}
ワイ「events配列の中に関数を突っ込むのはようわからんわ」
ワイ「スリープソート専用にしてiとelmを覚えといてくれるオブジェクトにするで」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
const events = [];
for (const elm of arr) {
// 各elmに対する処理を実行
sleep(elm);
}
while (events.length > 0) {
// eventsの先頭から1つ取り出して呼び出す
const { i, elm } = events.shift();
if (i < elm) {
events.push({
i: i + 1,
elm
});
} else {
result.push(elm);
}
}
return result;
function sleep(elm) {
events.push({
i: 0,
elm
});
}
}
ハスケル子「なんかsleepの中身がすっきりしてイベントループの中にベタ書きになりましたね」
ワイ「もうsleepとか要らんから消すわ」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
const events = [];
for (const elm of arr) {
// 各elmに対する処理を実行
events.push({
i: 0,
elm
});
}
while (events.length > 0) {
// eventsの先頭から1つ取り出して呼び出す
const { i, elm } = events.shift();
if (i < elm) {
events.push({
i: i + 1,
elm
});
} else {
result.push(elm);
}
}
return result;
}
ハスケル子「あの」
ハスケル子「このiってオブジェクトの中に入れる必要無くないですか？」
ワイ「せやろか」
ハスケル子「iは最初みんな0で」
ハスケル子「みんな一緒にiが増えていってelmに達したやつがresult.push(elm)されるんですよね」
ハスケル子「なのでiは別々に持つんじゃなくて共通にしましょう」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
let events = [];
for (const elm of arr) {
// 各elmに対する処理を実行
events.push({
elm
});
}
for (let i = 0; events.length > 0; i++) {
const nextEvents = [];
while (events.length > 0) {
const { elm } = events.shift();
if (i < elm) {
nextEvents.push({
elm
});
} else {
result.push(elm);
}
}
events = nextEvents;
}
return result;
}
ワイ「なんか随分変わりよったなあ」
ハスケル子「次のイベントループに登録するものはeventsに直にpushするんじゃなくてnextEventsを作ってそっちにpushするようにしました」
ワイ「なんで？」
ハスケル子「今のiの処理が終わったらiを増やしてから次のイベントループに行きたいので今のiに対する処理と混ざらないようにするためです」
ワイ「さよか（難しくなってきたで、若者の考えることはよう分からんわ）」
ワイ「でもこれeventsの中身のオブジェクトがelmしか値を持たんから数値を直に入れてもええやろ」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
let events = [];
for (const elm of arr) {
events.push(elm);
}
for (let i = 0; events.length > 0; i++) {
const nextEvents = [];
while (events.length > 0) {
const elm = events.shift();
if (i < elm) {
nextEvents.push(elm);
} else {
result.push(elm);
}
}
events = nextEvents;
}
return result;
}
ハスケル子「でも」
ワイ「今度は何や」
ハスケル子「これもうi要らなくないですか？」
ワイ「なんでや」
ハスケル子「iがどんどん増えていってelmに到達したやつからresultにpushされるんですよね」
ワイ「せやな（これそういう意味なんか、やっと分かったで）」
ハスケル子「ということは一番小さいelmが最初にresultにpushされますよね」
ワイ「せやな」
ハスケル子「じゃあ一番小さいelmを直接探せばいいんじゃないですか？」
ハスケル子「iは要らない子ですね」
ワイ「（iを要らない子にしたのはお前やろ！）」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
let events = [];
for (const elm of arr) {
events.push(elm);
}
while (events.length > 0) {
// 一番小さいelmを探す
let minElm = Infinity;
for (const elm of events) {
if (elm < minElm) {
minElm = elm;
}
}
// eventsの中から一番小さいelmをresultに入れて他はnextEventsに入れる
const nextEvents = [];
for (const elm of events) {
if (minElm === elm) {
result.push(elm);
} else {
nextEvents.push(elm);
}
}
events = nextEvents;
}
return result;
}
ワイ「やっとることは分かったけど」
ワイ「なんかnextEventsを毎回作っとるのが気に入らんで」
ハスケル子「じゃあ作らないようにしましょう」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
const events = [];
for (const elm of arr) {
events.push(elm);
}
while (events.length > 0) {
// 一番小さいelmを探す
let minElm = Infinity;
for (const elm of events) {
if (elm < minElm) {
minElm = elm;
}
}
// eventsの中から一番小さいelmを抜き出してresultに入れる
for (let k = 0; k < events.length; k++) {
const elm = events[k];
if (minElm === elm) {
result.push(elm);
// eventsからk番目を抜く
events.splice(k, 1);
// 次の要素がk番目に来るので調整のためにkを減らす
k--;
}
}
}
return result;
}
ハスケル子「nextEventsを作る代わりにeventsからspliceを使って抜き出していくようにしました」
ワイ「なるほどな」
ハリー先輩「動くな、計算量警察や」
ワイ「は？」
ハリー先輩「spliceは$O(N)$かかる計算や」
ハリー先輩「さっきまで$O(N^2)$だったアルゴリズムが$O(N^3)$になったんとちゃうか？」
ハスケル子「くっ……」
ワイ「（なんの話しとるのかさっぱり分からんで）」
ワイ「（前回の話では英語の仕様書を一瞥しただけで理解できる天才だったのにどうしてこうなったんや）」
（1時間後）
ハスケル子「！！！」
ハスケル子「待ってください、splice(k, 1)は配列のk番目以降を全部前にずらすのが$O(N)$の理由です」
ハスケル子「ということはfor (let k = 0; k < events.length; k++)というforループと合わせればこれは全体として配列全体を1回舐めているだけ、よって$O(N)$です」
ワイ「（ちくわ大明神）」
ハリー先輩「だとしたらsplice(k, 1)の後にbreak;が必要なんとちゃうか？」
ハスケル子「あっ……」
ハスケル子「でもspliceを呼ぶと一番外側のループの回数がひとつ減るから……」
（1時間後）
ハスケル子「でもminElmを持つelmが複数あったときにもう一度最小値を探しなおすのは無駄ですよね」
ワイ「（話についていけなくて飽きてきたで）」
ハリー先輩「じゃあこういうときに使えるテクニックを教えたるで」
ハリー先輩「要素を全部動かすんやなくて要素の入れ替えを使うんや」
ワイ「お、やっと2人が次のコードを書き始めたで」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
for (const elm of arr) {
result.push(elm);
}
// まだソートされていない部分の開始位置
let start = 0;
while (start < result.length) {
// 一番小さいelmを探す
let minElm = Infinity;
for (let k = start; k < result.length; k++) {
const elm = result[k];
if (elm < minElm) {
minElm = elm;
}
}
// resultの中から一番小さいelmを探す
for (let k = start; k < result.length; k++) {
const elm = result[k];
if (minElm === elm) {
// elmをstart番目に入れて代わりに今start番目にあるやつをk番目に移動
result[k] = result[start];
result[start] = elm;
// start番目はソート済み
start++;
}
}
}
return result;
}
ワイ「なんか元のコードの面影はあるけどまた大分変わってもうたで」
ワイ「eventsもnextEventsも消えてresultだけになってもうたわ」
ハリー先輩「このコードではresultは2つの意味を持つで」
ハリー先輩「前半、つまりstart番目より前はソート済みでそれより後は未ソートや」
ワイ「最初startが0ってことはまだなんもソートされてないっちゅうことでんな」
ハスケル子「配列から最小値を見つける部分は同じですが」
ハスケル子「start番目より前は既に処理済みなのでstart番目以降から探すようになってます」
ハリー先輩「そして最小値elmを見つけたらそれを処理済み部分に付け足すんや」
ハリー先輩「つまりstart番目に移動させてやってstartを1増やしてやる」
ハスケル子「もともとstart番目にあったresult[start]はまだソートされていないですが」
ハスケル子「ちょうどelmがあった位置であるk番目が空いてるのでそこに入れておきます」
ハリー先輩「ここがポイントやな」
ハスケル子「要素の入れ替えによりソートを進めることでspliceによる配列をずらす操作を無くしているんです」
ハリー先輩「これなら誰が見ても計算量は$O(N^2)$や」
まとめ
ワイ「ところで」
ハリー先輩「ん？」
ワイ「これだとソートの安定性が失われるんとちゃいますか？」
ハスケル子「えっ……確かにそうですが」
ハリー先輩「誰やお前、さっきまでアホ面して半分寝とったあいつはどこに行ったんや」
ワイ「お前人様のキャラに向かって言っていいことと悪いことがあるで」
ワイ「てかなあ」
ハリー先輩「おう」
ワイ「これただの選択ソートやんけ！」
スリープソートを最適化したら選択ソートになった話 〜完〜
おまけ
ハスケル子「というか」
ワイ「なんや」
ハスケル子「計算量警察以降の話って無駄じゃないですか？」
ワイ「せやな」
ワイ「正直、iが消えた段階（↓）で既に選択ソートになっとると思うんやけど」
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);
function sleepSort(arr) {
const result = [];
let events = [];
for (const elm of arr) {
events.push(elm);
}
while (events.length > 0) {
// 一番小さいelmを探す
let minElm = Infinity;
for (const elm of events) {
if (elm < minElm) {
minElm = elm;
}
}
// eventsの中から一番小さいelmをresultに入れて他はnextEventsに入れる
const nextEvents = [];
for (const elm of events) {
if (minElm === elm) {
result.push(elm);
} else {
nextEvents.push(elm);
}
}
events = nextEvents;
}
return result;
}
ワイ「選択ソートでググっても要素の入れ替えを使って並び替えるのが選択ソートやっちゅう説明しか出てこんかったから無理やりそこまで持ってったんや」
ハスケル子「まあメモリ使用量が違いますからね」
ワイ「てか要素の入れ替えを使うとかプログラム書き換えすぎやろ、それでスリープソートが選択ソートになってもなんも面白ないで」
ワイ「見た目変わってるけど考え方は変わってないでってアピールするのが大変だったわ」
ハスケル子「アピール失敗してますよそれ」
ハスケル子「最後だけ説明が長くてコードが全然出てこないし」
ワイ「まあソートアルゴリズムの本質を分かっとる奴はあの段階でピンと来とったやろ」
ワイ「そうでない奴らから何言われたって痛くないで」
ハスケル子「（何で最後の最後に喧嘩売るんですかこの人は）」
〜完〜