Mapは $O(1)$ 、Switchは $O(N)$ ？

Goのmapは、なにか深遠なるアルゴリズムによって取得時 $O(1)$ が成立していると聞いています。
switchは単純に一つ一つの節にマッチするか検証しているから $O(N)$ ですよね？
だから、switchよりもmapを使ったほうがいいと思います

switchで十分実現できる処理がmapで書かれていたのでレビューで変えるように指摘すると、このようなことを言われました。
確かにmapは取得時 $O(1)$ の時間計算量が掲げられていますし、対してswitchは一つ一つ検証していそうです。
ここで、 $O(N)$ 程度の時間計算量なんか気にするのはcaseが1万とかになってからにしろ、「推測するより計測せよ」「早すぎる最適化」だと、どっちもどっち論で話を終わらせてもいいのですが、Goのような恵まれた環境ではちょっとでもopが増えたりnsレベルでも速度が遅くなるのは気になるのかもしれません。

しかし実際に計測してみるとswitchのほうが速いケースのほうが多いです。
なんてこった！時間計算量が裏切った！信じていたのに！

納得できないレビュイーのために、せっかくなのでコンパイラの実装も交えて見ていきましょう。

switchは $O(N)$ ？

switch文をコンパイラがどう解釈するかは

の部分がわかりやすいでしょうか。
jump tableをまず最初に適用可能か調べて適用可能であれば適用し、そうでなければ二分探索を行うという記述です。

jump tableは機械語で言えば大体1命令であるようなもので、ざっくり表現するなら配列アクセスと同じような処理で条件分岐を実現します。
mapアクセスの $O(1)$ を信じているのであれば、配列アクセスと中身がほぼ同じだと言われればjump tableの $O(1)$ はすんなりと信じることができるでしょう。

そして、適用外だった場合の二分探索ですが、 $O(\log N)$ ですね。
適用外になるには、jump table命令が使用できない^[1]かjump table命令では非効率^[2]かといったときですが、そうなったとしても $O(\log N)$ なわけです。

一応ですが、if文の列挙と同レベルまで落ちるケースもあります。

逆に言えばこれまでの話はif文の列挙よりもswitch文の方が速くなりやすいという話でもあったわけです。

総じて、switchは基本的にcase数に対して $O(1)$ 、一部の場合で $O(\log N)$ 、もっとも不利な条件を仮定してもifの列挙という十分に高速な $O(N)$ を安定的に提供してくれるということが言えます。

Mapは $O(1)$ ？

翻ってGoのmapはどうでしょうか。
まず触れておかなければならないのは、mapが $O(1)$ と言われているのが平均計算量のことであるということです。
ハッシュ値が衝突するなどの理由で、最悪計算量は $O(N)$ にもなり、その時点で配列アクセスと同じものとみなせるものではありません。

最良で $O(1)$ 最悪で $O(N)$ 。さっきの説明のとおりならだいたいswitchと同じじゃん、と思うのも早計です。
まず、mapを動かすためにはhash計算が必要で、これは比較的重い処理であるというのが一つ。
またmapは、SwissTableなどアルゴリズムの進展でだいぶそのようなことはなくなりましたが、メモリ局所性などの理由から二分探索 $O(\log N)$ のTreeMapのほうが速いことすらあるという代物です。
対してswitchが $O(1)$ でなくなるのは一部のケースに限られ、基本的には一貫して $O(1)$ アクセスを提供します。

言い換えれば

線形の計算量であってもNが小さいうちは定数項が支配的になりやすい (mapは定数項が重い、switchは定数項が軽い)
switchが線形の計算量であるというのが誤解

ということで、冒頭のレビュイーは推測の出発点を間違えていたということになります。

このようなことから、実際にベンチマークを取ってみたときに、mapで書くよりもif文の連鎖のほうが速く、それよりさらにswitch文で書いたほうが速いというケースがほとんどになるのです。
結論としてはswitchが基本的に速度面で有利なので、分岐数が100を超えてきて初めてmapを検討するために計測を始めるくらいの向き合い方でいいと思いますが、そもそもswitchで分岐数が100を超えそうなときは設計を疑ったほうがいいかもしれません。

ベンチマーク

古いPC(Windows10, Intel 6700K)で全くクリーンではないので参考までに

実装タイプ	小規模(8)	中規模(100)	大規模(1000)	性能特性
整数リテラルSwitch	2.47 ns/op	6.83 ns/op	12.40 ns/op	Jump Table
整数Map	11.32 ns/op	21.10 ns/op	18.71 ns/op	Swiss Table
浮動小数点数リテラルSwitch	-	-	17.30 ns/op	二分探索
浮動小数点数Map	-	-	37.45 ns/op	Swiss Table
変数Switch	0.59 ns/op	11.74 ns/op	285.1 ns/op	線形探索

感想

ベンチマークは実際の環境で困ったときに測るほうがよっぽど有用だと思っているので補足程度に認識お願いします。

整数リテラルswitchが大規模になるにつれて遅くなっていますが、アセンブリを見てみた感じjump tableは使っていたのでキャッシュミスとかなんですかね。まぁ1000ケースのswitch書いたらまずIDEが重くなったので実用的にはどうでもいいといえばどうでもいい。
整数Mapが中規模と大規模で速さ変わらないのは $O(1)$ の片鱗をのぞかせてて面白いですね。
二分探索が別に遅くも早くもないのはまぁ1000程度でそんな差が出ることも望めないという感じ。二分探索のアセンブリも見れて満足。
線形探索でもmapよりswitchのほうが速いのはそれだけmapが重いのを示してますね。100程度だったらmapの $O(1)$ よりsliceで線形探索した方が良いまであるというやつですね。

SwitchよりMapのほうが対応関係を示しているとわかりやすい？

MapはKeyとValueの対応を表すための構造を値として示せるじゃないですか
対してSwitchは制御構造だから、対応関係を表しているとわからないじゃないですか
だから、switchよりもmapを使ったほうが分かりやすくていいと思います

これもレビューで指摘したときに言われました。

switch v {
case 1:
    return "good morning"
case 2:
    return "good afternoon"
case 3:
    return "good evening"
default:
    return "hello"
}

という節内で即座に値をreturnしているswitchと、

map[int]string{
	1: "good morning",
	2: "good afternoon",
	3: "good evening",
}

というMapを見比べたとき、Mapが単純に対応関係を書いているだけなのに対し、switchは余計な構文がついてしまっているように見えます。
それもそのはずで、switchは即座に値を返して対応関係を作る以外のこともできるわけで、節内で即座に値のreturnしかしていないということは全節を見るまでわからないわけです。

また、一行目だけ見てみますと、

switch v {

はswitch文なんだなーと思うだけ

map[int]string {

はKeyがintでValueがstringのMapなんだなとわかるわけです。

なるほど、確かに冒頭の話は間違いではなさそうです。
ですが、速度よりも可読性を重視するとしてもmapは良い選択ではありません。

先程のmapを関数を通じて提供してみましょう。

var greetingMap = map[int]string{
	1: "good morning",
	2: "good afternoon",
	3: "good evening",
}

func Greeting(t int) string {
	if v, ok := greetingMap[t]; ok {
		return v
	}
	return "hello"
}

どうでしょうか？

まず、Greeting関数のインターフェースを知りたい人は、

func Greeting(t int) string

を見るので、

var greetingMap = map[int]string

という記述の重要さは小さくなりました。

そして、このGreeting関数がどういう対応関係を持つのかというのを把握するためには、greetingMapとGreeting関数のfallbackの分断された二箇所を見る必要が出てきたということもわかります。

さらに、mapは実行時に要素を変更することが可能なので、スコープ内でmapが変更される可能性を調べ上げなければその二箇所に書かれていることだけが真実だということも確定できないということも言えます。

これがswitchになれば

func Greeting(t int) string {
	switch t {
	case 1:
		return "good morning"
	case 2:
		return "good afternoon"
	case 3:
		return "good evening"
	default:
		return "hello"
	}
}

素晴らしい。mapの持っていた問題点はすべて解決し、インターフェースが一見してわかるという特徴はそのままです。

switchで新たに発生している問題といえば、構文が宣言的なものから手続き的なものに変化したことによって、やろうと思えばcaseの中で長い処理をベタ書きできるようになってしまったというのが思い浮かびますが……それはレビューで弾きましょう。
そんなことが起こり得る環境でswitchではなくmapであれば宣言的に書いてくれるはずという仮定も虚しいです。
逆に、基本的に純粋関数で書かれているプロジェクトなら、あまり気にしなくてもいいでしょう。

mapよりもswitchが当然に速いという感覚

記事冒頭のレビュイーの感覚に、いやいやとんでもない誤解だぞと、推測せずとも計測せずともswitchのほうが速いことを当然に期待するものじゃないかと思われた方々も多くいらっしゃると思います。
自分もそうで、最初からこの記事のように(特にGo言語において)完全な根拠を揃えて言語化してからmapではなくswitchを使えとレビューしたわけではありません。
switchのほうがmapより速くてわかりやすいでしょうというのを当然の感覚として持っていたわけです。

実際に計測すること、実際のコンパイラの実装を読むこと、実際に生成されるマシン語を読むこと、これらは確実ですがコストがかかります。
なにより、そもそもの感覚がなければ疑問にも思わず、計測も調査も行おうとすら思わないかもしれません。

コンパイラ最適化を信じているとか、ハッシュテーブル実装が重いことを経験的に知っているとか、そもそも条件式をベタ書きでいくら列挙しようが $O(1)$ 感覚でいいものでしょとか。個別具体で言えばそういうことになりますが、この件をより一般的な教訓にするなら

静的に決定できるものは静的な形で書け

ということです。
mapはメモリ上に積まれる構造体であるわけで、要素の増減はもちろんのこと、宣言時や取得時にも動的な要素が絡みます。
これは、コンパイル時の最適化が効きにくいことを意味していて、速度的に不利な傾向があります。
また動的であるということはそれだけ不確実性が増すということで、コード上の処理の追いやすさにも影響します。

この原則はmap以外のことにも言えて、最も単純なものでは変数よりも定数を選べとか、動的型よりも静的型を選べ、ということにも通底しています。
静的に決定できるものを静的に書くことが、静的型付け言語を好む人に共通する基本的なマインドセットとも言いかえられます。

動的型付け言語の人々はまた違ったマインドセットを持っていたりもします^[3]が、静的型付け言語ではこの教訓を持っていれば一つ指針になるのではないでしょうか。

脚注

浮動小数点数、32bit環境の64bit数値、アーキテクチャにjump table命令が存在しないなど ↩︎
switchの密度が十分に濃くないなど ↩︎
実際このレビュイーたちはJavaScriptの経験が主な人たちでした ↩︎

Discussion