🏫

Rust(Tauri+React)で席替えソフトを開発してみた

2023/08/29に公開

Rust

TL;DR

この記事は，情報系のただのしがない大学院生がアルゴリズムを駆使して，能力のばらつきなどを考慮した小学校の席替えソフトをRust，Tauriで開発してみた話をまとめたものである．
Tauriの使い方などについて，詳細はこの記事では扱わないので，細かい部分は他の方が書いてくださった記事や公式のドキュメントなどを参考にして頂きたい．

きっかけ

小学校の教員をしている筆者の友人から，こんな連絡を頂いた．

「子供たちの能力や男女比とか考慮した席替えソフト作ってー笑」

児童・生徒にとっては，席替えは重大なイベントの一つである．
好きなあの子と隣になれるか，嫌いなアイツと離れられるか等とドキドキしていた方も多くいらっしゃることだろう．
くじ引きで決める方法もあるが，エリアによって生徒の雰囲気や能力にばらつきが出てしまう場合がある．
そのため，特に小学校においては，先生が席順をあらかじめ決めるケースもある．
しかし，それを人力でやるのは決して楽ではないのは容易に想像できる．
ただでさえ教員の激務が社会問題になっている中で，さらに教員の負担が増えることは決して喜ばしいことではない．

依頼を受けた瞬間，アルゴリズムがなんか浮かんできたので，上記のような問題が解決できそうと思い，快諾することにした．

要件

画面上に現在の席順を入力させる．各席をクリックすると，出席番号，生徒名，性別，学力，運動能力，リーダーシップ力，支援の必要有無を入力できる．能力に関する項目は5段階評価とする．

席替えは，単にランダムに並び替えるわけではなく，能力に関する値のばらつきを最小化しながらも，前に前後，隣同士だった者とはなるべく離れさせるようにする．
支援を必要とする者は，なるべく教員の目につきやすいところに配置する．

また，席替えの結果は画面に表示させるとともに，本ソフトで読み込み可能なファイル（json），csv，pdfに出力できるようにする．

なお，今回は外部との通信は一切行わず，ソルバーも含めて全てローカル上で動作させるものとする．
（扱うデータの性質上，情報の漏洩が絶対に許されないため）

使用技術

フレームワーク：Tauri
フロントエンド：React
バックエンド：Rust

Tauriって？

Rustでデスクトップアプリを複数のプラットフォーム向けに開発することが可能なフレームワークである．
https://tauri.app/
ElectronのRust版ともいえる．ただ，Electronとは異なり，Chromiumに依存せず，OSに備わっているWebViewを用いているため，大幅にアプリケーションのサイズが大幅に小さくなる上，セキュリティ面でも優れている．
また，バックエンドはRustで記述するため，パフォーマンス面にも優れていることから，特にアルゴリズムを駆使するアプリケーションとは相性は良い．
フロントとバックの連携や，描画の詳細についてはこの記事で詳しく述べられている．
2022年にv1.0.0がリリースされ，まだ少し挙動がおかしい部分も散見されるものの，注目を集めつつあるフレームワークの一つである．
また，フロントエンド部分もReactやVue，Angularなどの有名なフレームワークに対応しており，Webアプリの開発がメインの方にとっても，Rustさえある程度分かればとっつきやすい．

【参考】TauriとElectronのスター数の比較

依然Electronの方がスター数は多いものの，伸びるスピードはTauriに軍配が上がる．

ファイル構成

.
├── README.md
├── app-icon.png
├── index.html
├── node_modules
├── package.json
├── pdf-generator
│   ├── Cargo.lock
│   ├── Cargo.toml
│   ├── assets
│   ├── src
│   └── target
├── solver
│   ├── Cargo.lock
│   ├── Cargo.toml
│   ├── src
│   └── target
├── src
│   ├── App.tsx
│   ├── EditLayout.tsx
│   ├── __tests__
│   ├── components
│   ├── main.tsx
│   ├── types
│   └── vite-env.d.ts
├── src-tauri
│   ├── Cargo.lock
│   ├── Cargo.toml
│   ├── build.rs
│   ├── icons
│   ├── src
│   ├── target
│   └── tauri.conf.json
├── tsconfig.json
├── tsconfig.node.json
├── tune.py
├── vite.config.ts
├── yarn-error.log
└── yarn.lock

ソルバー，PDF生成とtauriのメイン部分は別クレートで実装している．
これは，デバッグ時のビルド時間を短くするためである．
例えば，ソルバーのデバッグをする際，全て同じクレートに実装されていると，ソルバーにとっては必要ない部分までコンパイルされるため大幅に時間がかかるケースがある．
その上，ファイルの整理がしにくくなる場合もあるため，自作ライブラリなどは別クレートに分けることを推奨する．

席替えのアルゴリズム

目的関数（席順の評価基準）

目的関数とは，最小化または最大化（今回は便宜上最大化）したい式のことである．この場合は席順の評価基準であり，これを決めなければどうすることもできない上，これが非常に肝になってくるので慎重に決める必要がある．

前回の近所とは離れさせる

近所とは，自席の前後左右斜め方向に隣接している席とする．
各席に対して，前回近所にいた者とのマンハッタン距離の平均を算出し，それらを全て足したものを最大化する．

ばらつきの最小化

まず，自分とその近所の各パラメータの平均を算出し，これを $x_{is}$ （パラメータ $i$ ，児童 $s$ ）とする．
そして， $\sum_i\min_{s} x_{is} / \max_{s} x_{is}$ を最大化すればよい．

男女比については，男子を1，女子を0として計算すれば同様に扱える．

支援を必要とする者の扱い

支援を必要とする者それぞれに対して，黒板（ここでは，先頭の中央とする）との距離をそれぞれ計算する．それに重み（ $W$ とする）をかけた値をペナルティ値として，上記2つの合計から引く．

まとめ

児童全体の集合を $S$ ，支援を必要とする児童の集合を $T$ ，黒板の位置を $b$ ，現在の児童の隣接関係をグラフ $G=(S,E)$ ，項目 $i$ の重みを $W_i$ で表すとき，目的関数は以下のように表される．

\mathrm{score} = \sum_{s\in S}\sum_{t\in\delta(s)} \frac{1}{|\delta(s)|}d_1(s,t) + \sum_iW_i\frac{\min_{s} x_{is}}{\max_{s} x_{is}} - W\sum_{s\in T} d_2(s,b)

席毎の各パラメータ平均値の計算方法との計算量について

自席とその近所にパラメータの値を足し合わせる．
愚直にループで足し合わせるのではなく，いもす法を用いて計算している．
これにより，定数倍ではあるものの計算量を減らすことができた．
（因みに近所の範囲が大きくなるほど，いもす法による効果が大きくなる）
目的関数の計算時間が短縮されることにより，後述するアルゴリズムにおいて，短時間でより多くの試行を行うことができる．
一見些細な改善に見えるが，今回採用したアルゴリズムにおいて試行回数は非常に重要であるため，計算量のオーダーは変わらなくても定数倍の改善だけでも試みるのも良い．

この問題の難しさ

実は，近所の者を離れさせるだけなら一瞬で計算可能である．
実際，ICPC2023 国内予選のC問題でこのような問題が出題された．
しかし，これに加えてばらつきの考慮もするとなるとそう簡単にはいかない．
一般にこのような組合せ最適化問題はしらみつぶしに調べるしかないと考えられており（NP困難），この場合は $N!$ 通りのパターンを調べるしかないことになる．
例えば $N=30$ だと2溝6525穰2859𥝱8121垓9105京8636兆3084億8000万通りもあり，いくらコンピュータで計算するとはいえ，全部調べ終わる前に人類どころか宇宙そのものが滅亡していることだろう．（どんなに多くても1秒あたり約 $10^8$ 通りしか調べられない）

アプローチ

最適解を出すのは難しいが，それなりに良い解を出すのが難しいとは言っていない．
難しい問題に対する近似的なアプローチなら数多く提案されており，実務でもそのような手法を用いているケースも多い．
その中で，ここでは焼きなまし法と呼ばれる手法を採用した．

焼きなまし法

局所探索法という手法を改良したものである．この手法は解を一部改変して，スコア（目的関数値）がよくなったら解を更新するといった，極めてシンプルなアイデアがベースになっている．これだけでも妥当な解が得られるケースも結構ある一方で，一旦あえて悪化させた後にもう一度改変を加えた方がよくなるケースに対応することができない（局所最適解にはまる）という弱点を抱えている．
この問題に対処するために考案された手法が焼きなまし法（アニーリング法，SA法とも呼ばれる） である．
具体的には以下の式で表される確率で解を更新する．

P=\min\left(1, \exp\left(-\frac{\Delta}{T}\right)\right)

$\Delta$ はスコアの変化（旧スコアー新スコア）， $T$ は温度である．
温度は，実行時間や，ループ回数に応じて徐々に下げていくのが一般的である．
これにより，初めの方は悪化した解の採用確率が上がり，終わりになるにつれて確率が下がる．ここでは温度の値は $T_0$ からスタートし $T_1(<T_0)$ まで下げる．
$T_0,T_1$ はハイパーパラメータであり，この値により性能が変わる．
ここでは，Optunaを用いてパラメータを決定した．

Rustから直接呼び出すことはできないが，Pythonから呼び出し可能．コマンドライン引数を用いてパラメータを決定できるようにした上で，コンパイルしたバイナリファイルをPythonから呼び出すことにより実行可能である．

なお今回は，ループ回数が200000回に達した段階で処理を終了させるようにした．

GUI

以下のような見た目になった．

生徒・児童の情報は，席をクリックすると編集可能．

PDFへの出力

PDFは，printpdfというライブラリを用いて生成した．

機能面ではまだ備わっていない面も否めないが，直感的な記述でPDFの作成が可能である．

出力例

標準で用意されていない機能への対処

文字のセンタリング

テキストの横幅が分かればよい．
フォントサイズ（pt）からmm単位に変換することで対応可能．
半角の場合は，フォントサイズの半分を足す．

実装例

日本語フォント

デフォルトでは日本語フォントが含まれていないため，日本語テキストを出力しようとしても何も表示されない．
ttfファイルをバイト列として読み込むことにより対応した．
具体的にはinclude_bytes!マクロを使用する．これを用いることにより，コンパイル時にttfファイルも含まれるようになる．
ここでは，IPAフォントを採用した．

実装例

実際のコード

ビルド

GitHub Actionsを用いた．
公式からGitHub Actionsのツール（tauri-apps/tauri-action@v0）が配布されているため，これを用いた．

macOS Universal Binaryへの対応

ymlファイルでは，argsに--target universal-apple-darwinを設定しているが，GitHub Actions上ではこれだけでは不十分である．
GitHub ActionsにおけるmacOSでは，IntelベースのCPUが使用されているため，rustup target add aarch64-apple-darwinを実行することにより，Apple Silicon向けにもビルド可能にする必要がある．
しかし，tauri-apps/tauri-action@v0はDockerコンテナ上で実行されるため，ymlファイルでターゲット追加の記述をしても意味がない．
従って，tauri.conf.jsonの"beforeBuildCommand"に設定することにより対応した．

さいごに

競プロで培った知識も駆使しつつ，席替えソフトをTauriを用いて開発した．
実際に友人にご使用いただいたところ，結構いい感じに席順が出力されていたとのことであり，一人の教員を激務から多少は救えたのではという気分になった．
alpha版のみではあるものの（2023年8月現在），モバイルにも対応可能であるためiPadでも使用可能にするとさらに利便性が上がるかもしれない．

実際にTauriを使ってみたところ，当初の想定以上にReactに時間を割くことが多く，意外とRustばっかりというわけではなかった．
今回のケースでは，自分で書いたアルゴリズムをローカル上で動作させていたため，Rustによる恩恵を受けられたように思えるが，ローカル上で重めの処理を走らせないなどのケースでは，業務での使用はあまりオススメしない．（MVPで利用する分にはアリ）
筆者はAHCや研究などでRustの使用経験があるため，抵抗はあまり感じなかったが，Tauriに関する情報はまだ決して多くはないのが現状である．Rust自体がNode.jsよりも学習難易度が高いことを考慮すると，今の段階ではElectronや.NETのように定着させるのは難しい印象である．

とはいえ，個人的にはかなり好きなフレームワークであるため，Rustの普及率が上がることを祈りつつ個人開発ではまた使ってみたいと考えている．

謝辞

提案からテストまでご協力くださった友人に心から感謝申し上げます．