はい、どうも、Rubyをかれこれ5年くらい使っているものです
さて、競プロをやっていると、パフォーマンスとか考えないといけなくなることがあるんですが、何となくSetというものは知っている&ちょっと速いらしいけど、どこで使えばいいのかなって、ピンときてない人もいるんじゃないでしょうか
私もその一人ですし、そうでした
色々調べていくと、Setも厳密にやると色々と考えることがあって、ケースバイケースではあるんですが、今回は簡単に、Setの使い所と、速い理由を超ざっくりとまとめておきたいと思います
たくさんの要素から検索しなきゃ…の時
えーと、まずは共通認識作っておきたいので、以下の部分お付き合いください
まず、ちょっと宝くじみたいなことをかんがえます
1から10000の数字の中に、いくつかの当選番号があるとしますね
例えば1234と2345とかです
そして、Aさん、Bさん、Cさん…という人たちが、好きな数字を選んで投票するとします
例えばAさんは100、Bさんは1234、Cさんは3000に投票するとかいう感じです
この時、投票した順番にIDが1から順番に振られるとします
つまりAさんの投票はID:1、Bさんの投票はID:2、Cさんの投票はID:3…という感じです
この時、当選番号のIDを集めるプログラムを考えてみたいと思います
ちょっと考えてみてください！
というのもアレなんで、大体以下のような感じになると思います
winner_numbers = [1234, 2345]
votes = [100, 1234, 3000]
winners_ids = []
votes.each_with_index do |vote, index|
if winner_numbers.include?(vote)
winners_ids << index + 1
end
endで、この時、ちょっと気にして欲しいのが、winner_numbers.include?(vote)の部分です
ここって、それぞれの要素の数が大きくなるとどうなるかちょっと考えてみて欲しいんですね
例えばwinners_numbersが10000個いや、大小の当たり合わせて100万個とかあったとします
そうすると、投票に対応する番号が、当選番号であるwinner_numbersの配列の先頭から順番に全ての要素を探すことになるので、最悪、100万個とか探さないといけないことになります
そして、その上で、投票voteの要素の数が増えることを考えます
もしvoteが1つなら、最大100万個要素を探すことになりますが、voteが2つならMAX200万、voteが10個なら、1000個ならという形で、めっちゃくちゃな数になります
つまりここはパフォーマンスとして、問題を抱える可能性がある箇所ともいえます…まあそんな数になることがあるかどうかってことは置いといてですね
ちょっと具体的にいうと、配列のinclude?のロジックがO(N)ってことです
じゃあ、どうしましょうという話です
Setはhashで値を作る
ここでsetが使えます！という話です
どういうことかというとwinner_numbers.include?(vote)の部分で、winner_numbers.to_setとすると、winner_numbersがHashの形式で保存されます！
例えば、winner_numbers = [123, 456, 789] をSetに変換して検索すると…
- 各要素のハッシュ値を計算して格納
- 例:
123→ ハッシュ値:0x1A,456→ ハッシュ値:0x2B
- 例:
include?(456)を呼び出すと、対応するハッシュ値（0x2B）に直接アクセスして一致を確認
こうやると検索時は直接ハッシュ値を参照するため、winner_numbersがどんなにサイズが大きくなってもほぼ O(1) の時間で検索が可能になります
すごすぎる…天才だ…！
Set考えた人はすごい…
まとめ
というわけで、Setの使い所と、setが速いわけを説明してみました
Setは、特に検索する配列の量が多くなればなるほど、効果が大きいです
ただ配列をsetに変換するのにも結構計算あったり、どのくらいの配列の大きさからSetの効果が出始めるとか結構色々考慮する部分あったりします
なのでそのあたり詳しく知りたい場合はちょっと調べてみるといいと思います
が、今回のポイントは、配列をhashにして、そのkeyに対応する値を引っ張ることでO(1)で検索できるようになるから、はやくなるってことがわかっているのが重要な気がしますね
これがわかっていると、使い所も見えてくる気がします！
ではではー！
