【C#】 Listを使った場合とHashSetを使った場合とで処理速度に差が生まれる理由が分からない

Question

分からない点

入力を受け取り、被りがない場合は受け取った入力の番号を出力するという処理を①Listを用いた場合と②HashSetを用いた場合とで行いました。
同じような処理を行っているつもりですが、処理速度に非常に差異が生まれました（②の方が高速）
※コードは後述します
何故このような差異が生まれたのか自分には理解できないので、教えていただけないでしょうか？

自分の予想

①Listを用いた処理のif文の判別式に含まれる

list.Contains(input);

の処理は、list内に含まれる要素をインデックス番号が0から順に確認していくため、listに含まれる要素数が増加すると処理量が増加するのではないか？？

問題文

文字列 S を１行ずつ N 回受け取ります。 i (1 <= i <= N) 番目の文字列 Si が i-1 番目までの入力された文字列と被っていない場合　i を出力してください。

制約

1 <= N <= 10^5
Si (1 <= i <= N)は英小文字および数字からなる 1 文字以上 15 文字以下の文字列
    ※正規表現では[a-z0-9]{1,15}で表せる

入力

N
S1
S2
:
SN

出力

 i 番目の文字列　Si が i-1 番目までに被りがない場合、 i を出力

①Listを使った処理

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder
{
    class Problem
    {
        static void Main()
        {
            // Step1. Nを受け取る
            var N = int.Parse(Console.ReadLine());

            // Step2. 要素をメモするListを作成する
            var list = new List<string>();

            // Step3. 入力を受け取り、Listに含まれていない場合のみ追加＆番号出力
            for (int i = 0; i < N; i++)
            {
                var input = Console.ReadLine();
                if (!list.Contains(input))
                {
                    Console.WriteLine(i+1);
                    list.Add(input);
                }
            }
        }
    }
}

②HashSetを使った処理

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder
{
    class Problem
    {
        static void Main()
        {
            // Step1. Nを受け取る
            var N = int.Parse(Console.ReadLine());

            // Step2. 要素をメモするHashSetを作成する
            var list = new HashSet<string>();

            // Step3. 入力を受け取り、HashSetに含まれていない場合のみ番号を出力
            for (int i = 0; i < N; i++)
            {
                var input = Console.ReadLine();
                if (list.Add(input))
                {
                    Console.WriteLine(i+1);
                }
            }
        }
    }
}

Comments

[Zuishin]

他の質問もそうだけど、単に回答者を試そうとしてるだけじゃないの？
それか自分の別アカウントにスコアをつけるためか。
質問が不自然すぎる。

Answer 1

内部のアルゴリズムが違うからです。
あまり私は(その手の学校には通っていないtため)無学ですが、軽く調べた中では、アルゴリズムそのものが違うようです。

Listは名前はリストですが内部的には動的配列ですね。
で、HashSetはハッシュテーブルかなんかだと思います。

ハッシュテーブルの場合、値か何らかのデータをとある関数に通して得られる値を用いるようです。(厳密には違いますが)

ヒント: 参考1

で、公式ドキュメントで調べると、HashSet.Containsには、

このメソッドは、O(1) 操作です

とあります。これは、データの容量がいくつだろうが、常に一定であることを示します。

逆にList.Containsには、

このメソッドは、線形検索を実行します。したがって、このメソッドは O(n) 操作です

とあります。

そう、Listの方では、質問者さんのお考えのように、先端とかから一つずつ見ていくリニアサーチになっていて、

でもHashSetではハッシュ関数かなんかで一つの場所に定まるようなやつを通して検索するようです。

具体的なアルゴリズムはわかりませんが、例えばint用のHashSetだと 検索対象を x とすると、key = x % 2 + 2, value = x 的な感じにするようなものでしょうか。(計算式は適当)

そうすると、x がわかっていれば単純に 計算式 x % 2 + 2 を通して キーの値がわかる。そうすればその位置にアクセスするだけで済む。…的な感じかと。

ただし、私は具体的な計算式やらアルゴリズムやらは知らないのであくまでイメージですが。

Comments

[Zuishin]

> ただし、私は具体的な計算式やらアルゴリズムやらは知らないのであくまでイメージですが。

アルゴリズムに関してはソースコードがあります。

https://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs,3000888850fdc510

ハッシュの計算に関しては各クラスの GetHashCode に一任されているため、クラスにより異なります。
int の GetHashCode についてはこちら。

https://referencesource.microsoft.com/#mscorlib/system/int32.cs,86

見ての通り、何の計算もせず自分自身を返しています。

[taka10taka12]

@BeatStarさま
回答へのお礼が遅くなってしまい申し訳ございません。
Listの要素検索の仕方についてはなんとなく想像ができていたのですが、
今回初めてHashSetを用いて要素検索を行いました。
ハッシュについてはRubyでちょっと学んだ事があったのですが、
検索するときに処理速度に差が生まれる原因が全く分からず、質問しました。
わかりやすい説明に加え、@ZuishinさんのソースコードのおかげでHashSetの検索について
非常に理解が深まりました。
ありがとうございました！！

[taka10taka12]

@Zuishinさま
添付していただいたソースコードのおかげで非常に理解できました。
もし良ければ、以下に自分の認識を書きましたので、認識が間違っていないか見ていただけないでしょうか？

①Listを用いた処理では計算量がo(N)
②HashSetを用いた処理では計算量がo(1)
であることに疑問を持ったので、添付されてましたURLにあったHashSetのソースコードを確認しました。
結論としては、計算量はo(1)とは限らないが、要素はHashCodeをbucketsで割った余りで分類されているため、検索する量が少なくて済むという理解です。

②HashSetを用いた処理について一旦整理します。
「②HashSetを用いた処理」ではHashSetクラスのインスタンスを作成した後、
Addメソッドを用いることで
「要素が既に存在しているかの確認」と「存在していない場合は追加する」
という処理を行なっているという認識です。

そこで、HashSetクラスのソースコードの231行目にある
void ICollection<T>.Add(T item) {
AddIfNotPresent (item);
}
これが「②HashSetを用いた処理」で用いたAddメソッドという認識です。

この場合、Addメソッド内では「AddIfNotPresent (item)」が実行されるので、1044行目から続く
AddIfNotPresent (T value) {
if (m_buckets == null) {
:
を追っていきます。

まず、1054行目から続く
for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, value)) {
return false;
}
:
}
では、HashCodeが同じかつ値(value)が同じであれば、入力値は追加されない(return false)
というような処理を何回か繰り返すという認識です。

これでは、①のlist.Contains(input)の計算量と変わらないのではないか？
しかしながら、1049行目、1050行目にて
int hashCode = InternalGetHashCode(value);
int bucket = hashCode % m_buckets.Length;
とあり、要素はhashCodeをbucketsの長さで割った余りで先に分類されているため、
1054行目から続くfor文の検索回数が少なく済んでいる
という認識です。

次に、1063行目から1082行目まで続く
int index;
if (m_freeList >= 0) {
:
では、要素を追加するので配列のサイズを大きくし、hashCodeとvalueを同時に追加しているという認識です。

Answer 2

List<string> だと新たな値がリスト上にあるかどうかを全要素分比較するしかないので、要素が増えれば増えるほど照合に時間がかかると想定できます。

HashSet は GetHashCode で衝突した数だけ比較するので要素数に応じて急激に遅くはなりにくいからでは。

https://ufcpp.net/study/dotnet/bcl_collection_algorithm.html

Comments

[taka10taka12]

@papinianusさま
回答いただきありがとうございます。
@papinianusさまの仰る通りでした。
自分のHashSetの理解が足りておりませんでした。
添付していただいたURLもありがとうございました。
ListやHashSetの他にも様々なリストがあるのですね！
他のリストについても勉強してみます。