.NET/C#コレクションタイプのクエリベンチマーク

クズども · 掲載地 2022/03/07 16:47:50

要件:コレクションを追加、削除、変更せず、コレクションのみをクエリする読み取り専用のコレクションタイプを定義する必要があります。私たちはそう願っています問い合わせが早ければ早いほど良いです。

共通集合比較

アルゴリズムの複雑度を記述する際には、対応するアルゴリズムの時間計算量を表すために一般的に o(1), o(n)、o(logn)、o(nlogn)、すなわちアルゴリズムの時空間的複雑度の表現を表します。時間的複雑性を表すだけでなく、空間的複雑性を表すためにも使われます。

Oの後には、アルゴリズムが消費する時間/空間と成長するデータ量との関係を示す関数が括弧内に続きます。ここでnは入力データの量を表します。

例えば、時間計算量がO(n)の場合、データ量は数倍に増加し、時間消費も数倍増加します。例えば、一般的なトラバーサルアルゴリズムなどです。もう一つの例は時間計算量O(n^2)で、これはデータ量がn倍に増加するとn平方倍にかかる時間がかかることであり、これは線形時間よりも高い時間計算量です。例えば、バブルソートは典型的なO(n^2)アルゴリズムで、n×n回スキャンしてn個の番号をソートする必要があります。

別の例はO(logn)で、データがn倍に増加するとlogn倍を増やすのに時間がかかります(ここでのlogは2に基づいています。例えば、データを256倍に増やしても、必要な時間は8倍のみ増加し、線形時間より短いです)。二分探索はO(logn)のアルゴリズムであり、見つけるたびに半分の可能性を排除し、256のデータで検索すると8回見つければ目標が見つかります。

O(nlogn)は同じで、データを256倍にすると時間消費は256×8=2048倍に増加します。この複雑さは平方以下の線形性よりも高いです。マージとソートはO(nlogn)の時間計算量です。

O(1) は最も時空間的複雑度が低いものであり、消費される時間/空間は入力データのサイズに依存しません。入力データを何回増やしても消費される時間/空間は変わりません。ハッシュアルゴリズムは典型的なO(1)の時間計算量を持ち、データの大きさに関わらず単一の計算で(競合の有無に関わらず)ターゲットを見つけることができます。

本記事ではBenchmarkDotNetペアを使用していますList、HashSet、SortedSet、辞書ベンチマークのクエリは以下の通りです:

.NET/C#はBenchmarkDotNetを使ってコードのパフォーマンスをテストします
https://www.itsvse.com/thread-9576-1-1.html

.NET/C# 反射、エミット、表現のパフォーマンステスト
https://www.itsvse.com/thread-9598-1-1.html

コードは以下の通りです:

ログインが見えます。

テスト結果:辞書やハッシュセットでキーを見つけるのは、リストやSortedSetで調べるよりもはるかに速いです。 DictionaryとHashSetアルゴリズムの時間計算量はO(1)であり、メモリを節約するためにDictionaryの値は役に立たないので、それでもHashSetの保存を選びました。

トビウオ · 掲載地 2022/03/07 23:09:48

また学びに来た。

クズども · 掲載地 2022/03/09 9:55:12

ハッシュセットテスト

ログインが見えます。

クズども · 掲載地 2024/02/24 17:45:14

.NET/C#コレクションリスト、HashSetで要素にベンチマークがあるかどうかを判定します
https://www.itsvse.com/thread-10735-1-1.html

[出典] .NET/C#コレクションタイプのクエリベンチマーク

関連記事

閲覧したセクション