Scala: マッピングモデルを使う構造で表示用データを高速に組み立てる方法
はじめに
こんにちは。エンジニアの久保です。
普段は保育士バンク！コネクトというサービスを開発しています。
今回はScalaでコレクション操作する際のパフォーマンスに関する小ネタについてお話ししたいと思います。
概要
「ユーザーが複数のグループに所属する」という設計の場合。
こんなかんじのマッピングテーブルを使う実装ってよくあると思います。
で、このデータ構造から下記のような「ユーザとその所属グループ一覧」を複数取得したい場合のScalaでの良い書き方と悪い書き方を紹介していこうと思います。
言語やフレームワークによっては LEFT JOIN など使ってクエリの方で解決する手段もあると思いますが、今回はScalaの世界で実装する前提で書きます。
ちなみにバージョンは 2.13.1です。
■ 悪いパターン
実装確認
まず悪いパターンから。
1. userSeq を map で回して
2. userId で GroupMember を特定し
3. それに紐づく Group を取得する
といった流れですね。
仕様をそのまま素直に書くとこういう書き方になるかと思います。
どこがいけないのでしょうか？
では実行速度を見てみます。
まずは10件。
3回ほど実行。
$ scala testA.scala
3ミリ秒
$ scala testA.scala
2ミリ秒
$ scala testA.scala
3ミリ秒問題なさそう。
では10,000件。
同じく3回実行。
$ scala testA.scala
5231ミリ秒
$ scala testA.scala
4681ミリ秒
$ scala testA.scala
5225ミリ秒悲惨ですね。なぜこうなってしまうのでしょうか。
問題箇所
計算量を確認します。
filter はコレクションの先頭から末尾まで確認するので、計算時間は線形です。
なので計算量は
となり、ユーザー数、グループ数、マッピング数それぞれが10,000件(n=10,000)の場合
200,000,000 = 2*10,000*10,000
2億回。絶望的ですね。
O(n²) の部分をなんとかすれば速くなりそうです。
■ 良いパターン
要らないと思いますが10件で実行した結果。
$ scala testB.scala
4ミリ秒
$ scala testB.scala
4ミリ秒
$ scala testB.scala
2ミリ秒大差無いですね。
では10,000件
$ scala testB.scala
472ミリ秒
$ scala testB.scala
420ミリ秒
$ scala testB.scala
470ミリ秒うーん、爆速ってわけじゃないですが割とマシになりました。
工夫した点
- ①で最初に GroupMember を使って、ユーザーIdをキーにしたグループリストのマップを作ってしまいます。
- ②でマッピング数分回るので10,000回
- ③は今回の例では1回。ユーザーが10グループに所属してたら10回となりますがさほど影響しません
- ④はfindなので線形、Vectorを使えば実質定数です（性能特性)
- ⑤はユーザー数分
なので
となりn=10,000なら20,000。
2万回で済む、というわけですね。
全ユーザーが10グループに属しているとしても11万回で、悪いパターンの2億回よりはマシです。
まとめ
Scala勉強し始めたころは filter が便利すぎて多用してしまいがちですが、計算量はしっかり意識して実装したいですね。
find は定数なので、 groupBy でマップを作ってしまってキーで find する、というこの方法は割と色んな場面で使えるのではないかと思います。
また、データ量が少ないと問題が表面化しないのも罠ですね。
お読み頂きありがとうございました。
改善の余地はある気がするので、
間違っている点、改善できる点あればご指摘頂けますと幸いです🙇♂️
We are Hiring!
「人口減少社会において必要とされるインターネット事業を創造し、ニッポンを元気にする。」
を理念に掲げ一緒に働く仲間を募集しております。
