【基本情報の実務】処理速度の見積もり──測るべきは「いまの速さ」ではなく「増え方」
賢者の図書塔の司書見習いから、処理速度の見積もりについて相談が届く。
「蔵書の一覧から目的の1冊を探す処理を作りました。今は先頭から1件ずつ照合しています。蔵書が1万冊から10万冊に増える予定なのですが、処理はどれくらい遅くなるのでしょうか。速くする案があれば、それも教えてほしいです。」
基本情報の知識がここで力になるのは、答えを「秒」で出そうとしないときだ。いまが何秒かは機械や状況で変わるので、そこから伸ばした数字は当てにならない。手順から言えるのは、増え方のほうである。この記事では、そこから整理する。
まず結論：件数に比例するので、10倍になる
| 探し方 | 10倍に増えると | 言える根拠 |
|---|---|---|
| 先頭から1件ずつ | 手数も10倍 | 1件増えれば、確かめる回数が1回増える |
| 半分ずつ絞る | 数回増えるだけ | 1回で候補が半分になる |
いまの探し方は先頭から1件ずつ照合である。1件増えるごとに、確かめる回数が1回増える。
だから件数が10倍になると、確かめる回数も10倍になる。これは機械の速さと関係なく言える。
ここが大事なところである。「いま1秒だから、10秒になります」とは言わないほうがよい。
その1秒には探す以外の時間も混ざっているし、10万件になると、それまで無かった事情——一度に置いておけるか、など——が出ることもある。
手順から確かに言えるのは「10倍になる」までである。そこまでを、はっきり言う。
平均と最悪を、分けて答える
「10倍」も、実はどの場合の話かで変わる。3つに分けて考える。
- 運がよいとき——1冊目で見つかる。件数が増えても変わらない
- ふつうのとき——平均すると半分あたりで見つかる。1万冊なら5,000回ほど
- いちばん重いとき——最後まで見る。1万冊なら1万回
そして「いちばん重いとき」が、いつ起きるかが問題である。
探している本が、無いときである。無いことを確かめるには、全部を見るしかない。
ここは見落とされやすい。見つかる検索より、見つからない検索のほうが重い。
そして探し間違いや、蔵書に無い本の問い合わせは、実際によく起きる。いちばん重い場合が、めずらしい場合とは限らない。
だから見積もりでは最悪の場合で答える。10万冊なら、1回の検索で10万回照合しうる。
「遅くなる」と「困る」は別
10倍と分かったところで、まだ判断できない。10倍になっても困らないかもしれないからである。
だから速くする話に進む前に、1つ確かめる。
何秒までなら、困らないかである。
- 誰かが窓口で待っているのか——数秒でも長い
- 夜間にまとめて動かすのか——数分でも構わない
- 1日に何回使うのか——1日1回と、1分に10回では話が違う
この答えが出ると手を入れるかどうかが決まる。
10倍になっても許せる範囲なら、いまのままでよい。速くする改修には、手間と、新しい間違いの余地が付いてくる。
速くできることと、速くすべきことは、別である。
半分ずつ絞る──ただし前提が要る
速くする案として、いちばん効くのが半分ずつ絞るやり方である。
並べておいた一覧のまん中を見る。探している本より前か後ろかが分かるので、片側を丸ごと捨てられる。これを繰り返す。
1回で候補が半分になるので、増え方がまったく変わる。
- 1万冊——14回まで
- 10万冊——17回まで
件数が10倍になっても、増えるのは3回である。1万回と14回を比べると、違いの大きさが分かる。
ただし前提がある。並んでいることである。
本を追加するたびに正しい位置に入れる必要がある。探すのが速くなる代わりに、増やすときに手間が移る。
だから判断は探す回数と、増やす回数の比で決まる。
図書塔なら、蔵書を増やすのは時々で、探すのは毎日だと思われる。その形なら、並べておくほうが得である。
逆に、絶えず増え続けて、たまにしか探さないものなら、並べる手間のほうが重くなる。
回答の例
蔵書検索の処理速度について
1. どれくらい遅くなるか
照合の回数は、10倍になります。
先頭から1件ずつ確かめる方法では、1件増えるごとに確かめる回数が1回増えます。ですので、蔵書が10倍になると回数も10倍です。
「いま1秒なので10秒です」という形ではお答えしていません。いまの1秒には探す以外の時間も含まれており、10万冊になると別の事情も出てくるためです。手順から確かに言えるのは、10倍という増え方までです。
2. いちばん重いのは、見つからないとき
平均すると半分あたりで見つかるので、1万冊なら5,000回ほどです。
ただし探している本が蔵書に無い場合は、最後まで見ることになります。無いことを確かめるには、全部を見るしかないためです。
10万冊なら、1回の検索で10万回の照合が起こりえます。お問い合わせには「うちには無い本」も含まれますので、これはめずらしい場合ではありません。
3. 先にうかがいたいこと
何秒までなら、お困りになりませんか。
窓口でお客様がお待ちなのか、夜間にまとめて動かすのかで、必要な速さが変わります。1日に何回お使いになるかもあわせて教えてください。
10倍になっても許せる範囲でしたら、いまのままをおすすめします。速くする改修には手間がかかり、新しい間違いの余地も生まれるためです。
4. 速くする案
いちばん効くのは並べておいて、半分ずつ絞る方法です。
まん中を見て、探している本より前か後ろかを判断し、片側を丸ごと捨てます。これを繰り返します。
- 1万冊 → 14回まで
- 10万冊 → 17回まで
10倍に増えても、3回しか増えません。
5. その代わりに増える手間
この方法には並んでいることが要ります。本を追加するたびに、正しい位置に入れる必要があります。
探すのが速くなる代わりに、増やすときに手間が移ります。
図書塔では、蔵書を増やすのは時々で、探すのは毎日かと思います。その形でしたら、並べておくほうが得になります。
蔵書の追加がどれくらいの頻度か、あわせて教えていただけますでしょうか。
「秒でお答えしていません」と、その理由を書いた。答えなかったことを、答えていない形にしない。
見つからないときを、独立した項にした。聞かれていないが、いちばん効く情報である。
速くする案の前に、質問を置いた。直さない選択を先に見せている。
「いまのままをおすすめします」と書ける形にした。改修が要らないなら、そう言う。
最後に代わりに増える手間を書いた。速くする案だけ渡すと、その手間があとから出てくる。
作り方の手順
- 秒で答えようとしない。環境で変わる。
- 増え方を見る。手順から言える。
- 1件増えると、手数がいくつ増えるかを数える。
- 平均と最悪を分ける。
- 最悪がいつ起きるかを確かめる。ここでは「無いとき」。
- それがめずらしいかどうかまで見る。
- 「何秒までなら困らないか」を先に聞く。
- 直さない選択を見せる。
- 速くする案の前提を書く。
- 手間がどこへ移るかを書く。
この場面で効いている基本情報の知識
- 線形探索——件数に比例して手数が増える
- 二分探索——1回で候補が半分になる。並んでいることが前提
- 最悪の場合——見つからない検索は、必ず全件を見る
- トレードオフ——探すのが速くなると、増やすときに手間が移る
知識そのものより、速さを「秒」ではなく「増え方」で答えられることが、この場面で効いている。
見積もりで外したくないポイント
- 秒から伸ばさない。環境で変わる。
- 増え方は、手順から言える。
- 先頭から1件ずつなら、件数に比例。10倍で10倍。
- 平均と最悪を分ける。
- 見つからない検索が、いちばん重い。
- それはめずらしい場合ではない。
- 「遅くなる」と「困る」は別。
- 何秒までなら困らないかを先に聞く。
- 半分ずつ絞ると、10倍でも数回しか増えない。
- 並べる手間がどこへ移るかを書く。