はじめに
SENSYN ROBOTICS(センシンロボティクス)の中山です。開発組織全体を見る技術統括という組織でディレクターをやっています。
社内のコードを見ていて、性能を担保するための基礎力を向上させたいと思って記事を書くことにしました。
今回は性能がなぜ重要なのかと、性能を考える基礎として計算量を取り上げます。
なぜ性能が重要か
- ユーザー体験を良いものにするため
- システムのインフラコストを抑えるため
の2つがあると思います。
ここではperformance tuningの手法ではなく、tuningが必要になる機会を減らすための心構えを書いていきます。
性能とは
性能と言ってもいくつか指標があります。
- Throughput
- 単位時間あたりの処理の量
- Latency
- 要求を送ってから応答が返るまでの時間
- Resource consumption (どれだけの計算資源を使うか)
- CPU
- Memory
- Storage
- I/O
ユーザー体験に関係するのはLatencyで、インフラコストに効いてくるのはThroughputとResource consumptionです。
Latencyはユーザーが何か操作してから結果が返ってくるまでの時間とだいたい同じと見なせます。Latencyが大きいと操作するたびにユーザーを待たせる事になって、ストレスを感じさせることになります。
計算量を意識する
3つの性能指標すべてに効いてくるのが計算量です。
簡単な例を使って、計算量がどのように変換するかを見てみます。
2つのリスト foos, bars
foos, barsは以下のデータ構造を持つものとします。
{
key: string,
value: number,
}[]
const foos = [
{key: "a", value: 0},
{key: "b", value: 1},
{key: "c", value: 2},
...
];
const bars = [
{key: "z", value: 100},
{key: "y", value: 101},
{key: "x", value: 102},
...
];
foos, bars, それぞれの要素数をM, Nと置きます。
処理内容
例としてfoosのvalueをbarsのvalueで置き換える処理を考えます。
const replaced = foos.map(e => ({
key: e.key,
value: bars.find(b => b.key === e.key)?.value ?? e.value
}));
の計算量は
-
bars.find()は平均でN/2個の要素を探索します -
foos.map()は平均でM個の要素を変換します
トータルで平均 (N/2)*M=MN/2 個の要素を探索するので、計算量のオーダーはO(MN)となります (O記法については 良い記事 がたくさん あります)。
M, Nが小さければ問題になりませんが、数千、数万オーダーになってくると計算時間が急激に増大します。
- M, Nのオーダーが同じである場合、計算量はO(N^2)になります
- M, Nがそれぞれ100の場合、計算時間は100*100=10,000です
- M, Nがそれぞれ10,000の場合、10,000*10,000=100,000,000となります。
- 要素数が100倍になると、計算量は10,000倍です。
- 要素数が100倍になると、計算量は10,000倍です。
改善
O(MN)の計算量をO(M+N)に改善していきます。
データ量が少ないと分かっている場合は改善不要ですが、多くなる可能性が高いのであれば検討すべきです。
戦略
事前に計算用の一時的なデータ構造を用意して、bars.find(e.key) の計算量を定数時間(に近いオーダー)にします。
道具
計算量を抑える道具として Map object を利用します。
Map objectはJavaScript組み込みのhash mapで、key, valueのペアを格納します (言語規格としてはhash tableでなくてもsublinearであれば良いとなっていますが、多くの場合はhash tableで実装されていると思われます)。keyを指定してvalueを取得する処理が概ね定数時間O(1)で行えます(衝突状況や実装によっては定数時間でない場合もありますが、平均的には定数時間とみなせます)。
コード
// barsの各要素のkey,valueを元にMapを作る
const barMap = new Map(bars.map(e => [e.key, e.value])); // O(N)
// Mapを使って対応するkeyの値を高速に取得する
const r = foos.map(e => ({
key: e.key,
value: barMap.get(e.key) ?? e.value
}))
処理する要素数はbarMapを作るときがN、置き換えがMになるので、計算量はO(M+N)になります。
まとめ
性能の最適化はできる限り遅らせろ、とよく言われますし、ある程度は正しいと思います。ただ、最初に作る時点で全く性能を考慮しないと、最適化すべき箇所があまりにも多くなって大変なことになります。要は実装コストとのバランスなのですが、O(N)程度を基準としてある程度は意識しておくのが良いのではないかと思います。