社長「やめ太郎くん」
ワイ「なんでっか社長」
社長「画期的なソートアルゴリズムを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;
}
ワイ「選択ソートでググっても要素の入れ替えを使って並び替えるのが選択ソートやっちゅう説明しか出てこんかったから無理やりそこまで持ってったんや」
ハスケル子「まあメモリ使用量が違いますからね」
ワイ「てか要素の入れ替えを使うとかプログラム書き換えすぎやろ、それでスリープソートが選択ソートになってもなんも面白ないで」
ワイ「見た目変わってるけど考え方は変わってないでってアピールするのが大変だったわ」
ハスケル子「アピール失敗してますよそれ」
ハスケル子「最後だけ説明が長くてコードが全然出てこないし」
ワイ「まあソートアルゴリズムの本質を分かっとる奴はあの段階でピンと来とったやろ」
ワイ「そうでない奴らから何言われたって痛くないで」
ハスケル子「(何で最後の最後に喧嘩売るんですかこの人は)」
〜完〜