Zenn
😀

[Rust] HashSetとVecの速度比較

2022/08/03に公開
Rust
AtCoder
tech

要約

  • rustのHashSetとVec型について以下の3点で比較しました
    • 要素を追加する処理の速度
    • 要素をiterationで読み込んで代入する処理の速度
    • 要素を含むかどうか( contains() )の速度
  • 結論としては以下となります
    • 要素の追加はVecの方がだいぶ早いです
    • 要素の代入は定数倍でvecの方が若干早かったです
    • 含有検索はHashSetが圧倒的に早いです

この記事を読んでわかること

  • HashSetとVecの速度比較

この記事を読んでもわからないこと

  • 速度差の詳細な理由
  • 各処理のアルゴリズムの具体的な中身

記事作成の動機

自己紹介

新卒2年目の駆け出しほやほやJTCエンジニアです。普段はPythonでDeepLearningをしたりC++で組込みを書いたり、CADで図面書いたり、ソフトウェアインストール棚卸をしたりしてます。広く浅いです。

動機

最近Atcoderを始めて、慣れ親しんだPythonで挑戦しています。
実装力の無さもあり想定解でもTLEをたたき出してしまったり、型理解が浅く丸め誤差を考慮できなかったり情けない状況でした。そこで実行速度が速く型規則が厳しい言語を勉強することでプログラミング力の向上を図ろうと思いRustに乗り換えることとしました
（C++でもよかったのですがせっかくなので業務と関係ない言語を選定しました）
これでTLEとは無縁だと思っていたのですが、見事にもTLEをたくさん出してしまったのでどこがネックなのかを確認し、HashSetとVecの速度差に気づきましたので共有しようと思い作成いたしました。

使用したコード・実験内容

今回使用したコードはこちらです。
https://gist.github.com/KIrie-0217/64f4b7320735f8c4282c02ead7dd7716

取り分けて説明する内容もないのですが、各計測にはprintおよびiterationのオーバーヘッドを含みます。コードではiterationのみの速度も計測していますが、ここは差異はなかった為割愛しています

要素の挿入
    measure!(    {
        for i in 0..x{
            set_x.insert( (i , i) );
        }
        print!("set {} genetation:",x)
    }     );

    measure!(    {
        for i in 0..x{
            vec_x.push( (i , i) );
        }
        print!("vec {} genetation:",x)
    }     );
要素への代入
    measure!(    {
        for mut i in set_x.iter(){
             i  = &( 1 ,1 );
        }
        print!("set {} assignment:",x)
    }     );

    measure!(    {
        for mut i in vec_x.iter(){
             i  = &( 1 ,1 );
        }
        print!("vec {} assignment:",x)
    }     );
要素の含有計測
        measure!( {
            set_x.contains( &(num as i32, num as i32) );
            print!(" set {}_{} contains:", x,i)
        });
        measure!( {
            vec_x.contains( &(num as i32, num as i32) );
            print!(" vec {}_{} contains:", x,i)
        });

実施内容

以下の条件で実施しました

  • 要素を挿入する処理を10^n (n = 1..6)回実施し各nに対して実行速度をnsで計測
  • 要素への代入処理を10^n (n = 1..6)回実施し各nに対して実行速度をnsで計測
  • 要素を含んでいるかを配列サイズ10^n (n = 1..6)に対して実施
    • 各nに対してそれぞれ乱数で生成した要素を10個探索した結果の平均を算出[ns]
    • 乱数で生成した要素は必ずHashSet/Vec内に含むものとした

結果

要素の挿入

どちらもO(1)で動いてそうです。
vec.push()が要素数100、1000の時に差がない事が気になります。
今回Capacityは明示していませんがそこら辺の違いでしょうか？
挿入の速度差

要素の代入処理

当然ですがO(1)ですね
要素の代入

含有判定

HashSet.contains()は要素数に依らずO(1)に動くようです[1] ※理想的には
めちゃくちゃ早くて助かりますね。

Vec.contains()はリストをたどる必要があるため最大でO(N)の計算が必要になりそうです。
何も考えずにRustだから大丈夫でしょ、と使っていたら見事なまでにTLEをたたき出しました…反省です

含有判定

HashSet単体

まとめ

  • HashSetの探索はめちゃくちゃ便利
  • 入力で受け取ったVecをHashSetに変換するのにO(N)かかってしまうので探索をしないときはVecのままでいいかも
脚注

  1. https://users.rust-lang.org/t/what-is-the-algorithmic-complexity-of-hashset-contains/52998 ↩︎

Discussion