【めざせExcelマスターへの道】二分探索と高速VLOOKUP

こんにちは。ヒトツメです。
今日は大量のデータを扱うときに時間がかかってしまうVLOOKUPの高速化と、その前提となる二分探索について解説をしていきたいと思います。

高速VLOOKUP

関数の書き方

VLOOKUPというと、一般的な業務ではかなり使う頻度の高い関数ですが、二つのデータを突合する目的で利用するとき、例えば数万件と数万件のそれぞれのデータをくっつけるとした場合、VLOOKUPで処理すると、かなり時間がかかってしまいます。
よくExcelの右下に「○○%」と出ますが、処理に時間がかかると、これがなかなか進まず、ほかの業務ができなくてイライラすることもよくあると思います。

そこで、今回の技、高速VLOOKUPが役に立ちます。データの量にもよりますが、数分かかる処理が数秒で終わることもしばしばあります。記載自体は少々長いですが、先に記載してしまうと、次のような書き方になります。

データがソートされていることが前提

後述の解説の部分を読んでいただければ、意外とすんなりと覚えられてしまいますが、大前提として、この式は、データがソートされていることが前提となります。ソートされていないデータで処理をしようとすると、思わぬ結果が返ってきたりしますので、必ずその点は注意してください。

また、検索対象のデータに重複がある場合も、より下の値は無視されることになりますので、注意が必要です。この点は、通常のVLOOKUPの時でも同じ挙動です。

関数の考え方と二分探索

二分探索

では、具体的に関数でどんな処理をしているのか、ということを解説していくわけですが、その前提として、二分探索という考え方を理解しておくと、スムーズです。

そもそも探索のアルゴリズムには様々なものがありますが、VLOOKUPで、検索方法を「0」にした場合、完全一致の値を探すのが目的なので、検索範囲を上から一つ一つ見ていき、それが検索値と完全に一致しているかということを判定する、という処理がなされています。
検索値と同じものが上の方にあればいいですが、検索値が検索範囲に含まれていない場合、全ての値を確認する必要があるので、時間がかかります。VLOOKUPで大量のデータを扱おうとした場合に時間がかかるのは、これが原因です。
そこで、検索方法を「1」にしたときのVLOOKUPの検索方法、近似一致という方法を活用します。この近似一致に使われているのが、二分探索という方法です。

二分探索では、まず、検索範囲の一番上の値と真ん中の値をまず取り出します。この時、検索値に関して、「一番上の値」≦「検索値」≦「真ん中の値」になっているかどうかを判断します。これが真であれば、上半分に検索値が含まれているものと仮定し、含まれていなければ下半分に含まれているものと仮定します。さらにその上で、検索値が含まれていないとした（つまり下半分に含まれていると仮定された）場合、「真ん中の値」≦「検索値」≦「一番下の値」となっていなければ、その検索範囲に検索値は含まれていない、と判断します。これを続けていき、検索値がどこにあるかを判定します。

具体例として、次のような表の中で、「5」がどこにあるかを判定するということを、この二分探索によって行っていく場合、次のような処理になります。

1

2

4

5

8

10

14

15

18

この時、一番上の値は「1」で、真ん中の値は「8」です。検索値の「5」はその間にあるので、上半分にあると判断します。
さらに、上半分のうち、一番上の値は「1」で、真ん中の値は「4」です。検索値「5」はその間にないので、上半分のさらに下半分にあると判断します。
上半分のさらに下半分のうち、一番上の値は「4」で、真ん中の値は「5」です。検索値「5」はその間にあるので、上半分のさらに下半分のさらに上半分にあると判断します。
上半分のさらに下半分のさらに上半分は二つしか値がなく、そのうち二つ目の値が「5」なので、「5」は4番目にあると判断されます。

これくらいの量だと、一つ一つ見ていった場合と処理の分量は変わりませんが、これが数万件の処理となると、圧倒的に近似一致の方が処理が速くなります。何より、検索値が検索範囲に含まれていないという判断が、圧倒的に早くなります。

近似一致を活用して、完全一致を判定する

高速VLOOKUPでは、この近似一致を活用して、完全一致を判定します。上記の近似一致をさらに強化させていて、Excelでは、VOOLKUPの近似一致の場合などでは、必ず何らかの戻り値を戻してくるように設計されています。例えば、上記の表で検索値を「3」とした場合、「2」のすぐ後ろにあるはずだから、という理由で、「3番にそれに近しい数字がある」という結果を返すように設定されています。

これを利用し、高速VLOOKUPではまず、近似一致の検索結果で出てくる場所に、検索値と同じものが含まれているかどうかを判断します。

この部分が、その処理です。
その上で、これをIF関数の条件式の中に入れ、検索範囲を近似一致で検索し、その場所に含まれている値が、元の検索値と同じだった場合にのみ、VLOOKUPの処理を行い、そうではない場合には、何もしないという処理をしているのです。

毎回全部検索しない

この関数の良いところは、毎回すべての値を検索しないところです。VLOOKUPで完全一致の処理をした場合、先述の通り、検索値が検索範囲に含まれていない場合、全ての値をチェックすることになります。これが処理を重くしている最大の原因です。
これを、近似一致を活用することで回避し、検索速度を上げています。

逆に言えば、検索範囲に検索値が必ず含まれている場合は、あまりこの処理をしたからといって早くはなりません。というよりは、この処理をしなくても、それなりに早く処理が完了するはずです。

さいごに

この考え方を少し応用して、途中で関数を挟むことで、処理を劇的に早くすることも可能です。

このように、処理を三段階にします。
上記の高速VLOOKUPでは、IF関数の条件式がTRUEの場合、完全一致のVLOOKUPを処理していました。したがって、この時、上から一つ一つ確認するという作業は必ず発生してしまいます。
このように処理を三段階に分け、近似一致の検索結果（場所）を一度表示させ、そこに何があるかによって結果出力を変えるようにすれば、高速VLOOKUPの時の「一つ一つ確認する」という部分すら省略できます。

Excelの処理は、その前提となっている処理のアルゴリズムを理解すると劇的に改善ができます。また同時に、どういった書き方をすれば早くなるかがスムーズに覚えられるようになると思います。