Link! Like! ラブライブ!というゲームに、スクールアイドルショウ（通称スクショウ）と呼ばれるリズムゲー（いわゆる音ゲー）が存在します。
プレイをするには、自身が所持しているカードを利用し6枚の編成を組む必要があります。私は機械的に最適な編成を探索するツール「スクショウ自動編成機」をWebアプリとして公開しました。
アルゴリズム自体はシンプルで、点数計算ルールは明らかになっているため、$\mathcal{O}(_n\mathrm{P}_6)$の計算を回すだけです。もっとざっくり評価して$\mathcal{O}(n^6)$の時間がかかりますが、まあ競プロみたいに2秒とかで全てを完了しなければならない決まりはないので。たかだか$n\approx10^2$程度です。
今回は、このツール開発時に使用したJavascriptのAPIなどを紹介したいと思います。
技術たち
フレームワーク：Nuxt.js
Nuxt.js 4を開発に使用しています。選定理由としては、僕が普段Nuxt.js開発をよくしている以上の理由はありません。
React勢の中にはVueを冷笑するやつもいますが、そのうちの半数以上は純粋型がどうだのTypescriptとの相性がどうだの、Vue 2を想定してものを喋っていました。技術者なのに情報のインプットで遅れを取って良いんですかね（）。
Local Storage
必須・任意・除外などの選択状況を保存するためにLocal Storageを使用しています
File API
TSV読み込みを実装するためFile APIを使用しています。
こういう系は今の時代AIにまかせてしまうと楽ですね。データの形式の変換とか覚えるの結構しんどいので。
Web Workerによるマルチスレッド化
計算資源を最大限利用するため、Web Workerによるマルチスレッド化を実装しています。
ただ、やっぱマルチスレッド用では使いづらいですね。
というのも、Web Workerはメッセージベースなので、変数とかの共有は簡単には出来ず、もし厳密に変数の共有をしたいならSharedArrayBufferなどを使う必要があります。
しかし、SharedArrayBufferは型つき配列でオブジェクトなどを扱うのはちょっと厳しいものがあります。オブジェクトがC++の構造体みたいな作りをしてればよかったのですが……。というか、基本JSって型無しなのにこういうときだけ型あるの何。
というわけで、自動編成機ではメモリの無駄だと理解しつつもオブジェクト（主にカードや楽曲のデータ）のコピーをWeb Workerに転送して計算しています。Javaのsynchronized宣言とかが恋しいです。
ちなみにPromiseは非同期であってマルチスレッドではないので注意しましょう。イメージとしては、窓口に列が出来てたとして、Promiseは割り込みができる、マルチスレッドは窓口を増やせると思うのが良いと思います。
navigator.hardwareConcurrency
ところでマルチスレッド化するにしてもコア数が分からないと最大効率が出せないですよね。コア数を知ることはできないのでしょうか。出来ますけど。
MDNの例示でもWorkerの作成数として利用してますね。
Screen Wake Lock API
Windowsはわからないのですが、少なくとも手元のMacはスリープ状態に入ると計算速度が低下してしまいます。
そこで、Screen Wake Lock APIを使用し、計算中はスリープにならないようにしています。
ジェネレーター
$_n\mathrm{C}_6$通りの組み合わせについて計算を行わなければならないのですが、これを配列とかで管理すると一瞬でメモリを圧迫します。そのため、1個ずつ計算を行う必要がありますが、for文は使いたい。そんなときに便利なのがジェネレーターです。
以下の感じで書けば、$_n\mathrm{C}_6$個の配列を生み出すことなく、for文で処理を回すことが出来ます。
export function* combinations<T>(arr: T[], r: number): Generator<T[]> {
if (r === 0) {
yield []
} else if (r === 1) {
for (const item of arr) {
yield [item]
}
} else {
for (let i = 0; i < arr.length - r + 1; i++) {
const rest = arr.slice(i + 1)
for (const combination of combinations(rest, r - 1)) {
yield [arr[i]!, ...combination]
}
}
}
}
for (const optionalMemberPair of combinations(
optionalMembers, // nの要素を持つ配列
optionalMemberSelectedNumber, // いくつ選び出すか（k）
)) {
// 処理
}
ところでこれ再帰数的には大丈夫なんですかね。あんま詳しくないですが。
Bigint（実は今のところ不要）
JavascriptでNumber.MAX_SAFE_INTEGER=9007199254740991以上の数字を安全に扱うには、bigintなどが必要になります。
計算途中経過を表示するために組み合わせ数を計算する必要があり、それがオーバーフローするかと思ったので入れたのですが、よく考えたらしばらくは大丈夫そうでした。
というのも、$_n\mathrm{C}_k$を以下で実装してしまったのですが……。
const factorialBigInt = (n: bigint) => {
let i = 1n
for (let j = 1n; j <= n; j++) {
i *= j
}
return i
}
const combinationNumBigInt = (n: bigint, k: bigint) => {
return factorialBigInt(n) / (factorialBigInt(k) * factorialBigInt(n - k))
}
これ明らかに無駄です。数学だったら$n!$のほうが扱いやすいのでこう定式化されてますが、プログラミングではfor文なり配列なり便利なものがあるので、$k$個の数をかけるだけのほうがいいです。
あと組み合わせ最適だと思いこんでBigintにしたのもあります。実際は$\mathcal{O}(n^6)$なので、もはやNP困難ですらなくPです。6乗をPとかいうのちょっと抵抗ありますけど。
V8エンジンへの最適化
Chromeとかに入ってるJavascriptの実行エンジンをV8エンジンといいますが、コイツは結構色々な最適化をしてくれます。それを最大限行うため、色々コードに修正を入れています。例えば以下とかが参考になるでしょう。
まあ基本的にTypescriptを使っていると勝手に達成できることが多いですが、少し油断すると微妙に遅い方法で書いてしまうこともあったり。
例えば型が混合してるタプル（例えば[string, number]）は、配列の最適化の都合上よくありません。読みにくいコードを招くことにもつながるのでシンプルにオブジェクト（{a: string, b: number}など）を使いましょう。