Go to Qiita Advent Calendar 2024 Top
LoginSignup
9
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

C#Advent Calendar 2024

Day 8
@prozolic

[C#].NET 9から導入されたOrderedDictionaryについて

Last updated at Posted at 2024-12-07

この投稿はC# Advent Calendar 2024 8日目の記事です。

はじめに

.NET 9からジェネリック版のOrderedDictionaryが導入されました。
OrderedDictionaryの特徴は、要素を追加した順番を維持した状態でキーと要素を保持できる点になります。
これだけなら .NET 9以前にも非ジェネリック版のSystem.Collections.Specialized.OrderedDictionaryも同様の特徴をもっています。ただキーと要素がObjectであるから、つねにボックス化が発生してしまい、パフォーマンスもあまり良いとはいえませんでした。
ジェネリック版ではパフォーマンスも向上し、またジェネリック版から導入されたインデックスを用いたメソッドも追加されましたので、今回はこれらについて色々触れていきます。

確認環境

  • Visual Studio Community 2022 (v17.12.0)
  • .NET 9 (C# 13)

基本的な使い方

Dictionaryと同じようにキーと要素の型を指定し、インスタンスを作成します。
追加、削除、検索、取得についても、Dictionaryと同様のAPI群を使用して実行可能です。
また順番を維持した状態で要素を保持しているため、要素を追加した順番で列挙します。

// インスタンス作成
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// キーと要素を追加
dict.Add("D", 4);
// キーに紐づく要素を作成
dict.Remove("D");
// キーと要素を追加
dict.Add("E", 5);

// キーに紐づく要素を検索し、見つかった場合には要素を取得する
if (dict.TryGetValue("A", out var value))
{
    Console.WriteLine(value); // 1
}

// 保持しているキーと要素を列挙する
// 追加した順番（登録した順番）で列挙する
foreach (var pair in dict)
{
    Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
}
// key = A, Value = 1
// key = B, Value = 2
// key = C, Value = 3
// key = E, Value = 5

インデックスを用いた追加/削除/検索/取得

インデックスから要素へアクセスする方法が非ジェネリック版から変更されています。
インデックスの要素の取得、更新は、非ジェネリック版はインデクサー（this[int index]）でしたが、ジェネリック版ではGetAtメソッドとSetAtメソッドに変更されています。
GetAtメソッドは、KeyValuePair<TKey, TValue>で返却するため、指定したインデックスの要素だけでなくキーも取得できます。
SetAtメソッドは、指定したインデックスの要素だけでなく、キー自体も更新できます。

// インスタンス作成
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// index:1の要素を取得します
var value = dict.GetAt(0);
Console.WriteLine(value); // [A, 1]

// index:1の要素を更新します
dict.SetAt(1, 4);
// index:2のキーと要素をそれぞれ更新もします
dict.SetAt(2, "D", 5);

// key = A, Value = 1
// key = B, Value = 4
// key = D, Value = 5

指定したインデックスへキーと要素の挿入は、Insertメソッドで可能です。

var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// index:1に["D", 4]を挿入します
dict.Insert(1, "D", 4);

foreach (var pair in dict)
{
    Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
}

// key = A, Value = 1
// key = D, Value = 4
// key = B, Value = 2
// key = C, Value = 3

指定したインデックスのキーと要素の削除は、RemoveAtメソッドで可能です。

var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// index:1のキーと要素を削除します。
dict.RemoveAt(1);

foreach (var pair in dict)
{
    Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
}

// key = A, Value = 1
// key = C, Value = 3

IndexOfメソッドは、キーからインデックスを取得することが可能です。

var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

var index = dict.IndexOf("B");
Console.WriteLine(index); // 1

var pair = dict.GetAt(index);
Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");

パフォーマンス比較

ジェネリック版や通常のDictionaryと比べてどれくらいパフォーマンスが上がっているのか、BenchmarkDotNetを使用して確認しました。

ベンチマークのソースコード 

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Columns;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Diagnosers;
using BenchmarkDotNet.Exporters;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using System.Runtime.InteropServices;

new BenchmarkSwitcher(
    [typeof(AddBenchmark), typeof(IndexerBenchmark)])
    .Run(["Release", "--filter", "*"]);

[Config(typeof(BenchmarkConfig))]
public class AddBenchmark
{
    private int count;
    private List<string> keys;

    [GlobalSetup]
    public void GlobalSetup()
    {
        count = 1000000;
        keys = Enumerable.Range(1, count).Select(i => i.ToString("x")).ToList();
    }

    [Benchmark(Baseline = true)]
    public void OrderedDictionary_Add()
    {
        var keys = CollectionsMarshal.AsSpan(this.keys);
        var dict = new OrderedDictionary<string, int>();

        for (int i = 0; i < keys.Length; i++)
        {
            dict.Add(keys[i], i);
        }
    }

    [Benchmark]
    public void OrderedDictionaryForNonGeneric_Add()
    {
        var keys = CollectionsMarshal.AsSpan(this.keys);
        var dict = new System.Collections.Specialized.OrderedDictionary();

        for (int i = 0; i < keys.Length; i++)
        {
            dict.Add(keys[i], i);
        }
    }

    [Benchmark]
    public void Dictionary_Add()
    {
        var keys = CollectionsMarshal.AsSpan(this.keys);
        var dict = new OrderedDictionary<string, int>();

        for (int i = 0; i < keys.Length; i++)
        {
            dict.Add(keys[i], i);
        }
    }
}

[Config(typeof(BenchmarkConfig))]
public class IndexerBenchmark
{
    private List<string> keys;
    private OrderedDictionary<string, int> orderedDict;
    private System.Collections.Specialized.OrderedDictionary orderedDictForNonGeneric;
    private Dictionary<string, int> dict;

    [GlobalSetup]
    public void GlobalSetup()
    {
        this.keys = Enumerable.Range(1, 1000000).Select(i => i.ToString("x")).ToList();

        orderedDict = new OrderedDictionary<string, int>();
        orderedDictForNonGeneric = new System.Collections.Specialized.OrderedDictionary();
        dict = new Dictionary<string, int>();

        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            orderedDict.Add(keys[i], 1);
            orderedDictForNonGeneric.Add(keys[i], 1);
            dict.Add(keys[i], 1);
        }
    }

    [Benchmark(Baseline = true)]
    public void OrderedDictionary_Indexer()
    {
        var sum = 0;
        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            sum += orderedDict[keys[i]];
        }
    }

    [Benchmark]
    public void OrderedDictionaryForNonGeneric_Indexer()
    {
        var sum = 0;
        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            sum += (int)orderedDictForNonGeneric[keys[i]];
        }
    }

    [Benchmark]
    public void Dictionary_Indexer()
    {
        var sum = 0;
        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            sum += dict[keys[i]];
        }
    }
}

internal sealed class BenchmarkConfig : ManualConfig
{
    public BenchmarkConfig()
    {
        AddExporter(MarkdownExporter.GitHub);
        AddDiagnoser(MemoryDiagnoser.Default);
        AddColumn(RankColumn.Arabic);
        AddColumn(StatisticColumn.Min);
        AddColumn(StatisticColumn.Max);

        //AddJob(Job.ShortRun);
        AddJob(Job.MediumRun);
    }
}

まず、1000000個のキーと要素を追加した場合の計測結果になります。

Method Mean Error StdDev Min Max Ratio RatioSD Rank Gen0 Gen1 Gen2 Allocated Alloc Ratio
OrderedDictionary_Add 59.48 ms 1.144 ms 1.566 ms 56.07 ms 62.07 ms 1.00 0.04 1 1222.2222 1222.2222 1222.2222 71.95 MB 1.00
OrderedDictionaryForNonGeneric_Add 379.71 ms 11.404 ms 16.716 ms 357.69 ms 419.80 ms 6.39 0.32 2 8000.0000 7000.0000 2000.0000 131.08 MB 1.82
Dictionary_Add 56.34 ms 2.370 ms 3.474 ms 52.05 ms 65.09 ms 0.95 0.06 1 1222.2222 1222.2222 1222.2222 71.95 MB 1.00

ジェネリック版と比較すると約6倍の高速化、アロケーションも約2倍削減とパフォーマンスがかなり向上しているようです。
またDictionaryと比較しても、同じぐらい（わずかにおそい程度）の速度で実行されていました。
追加処理だけで計測したため、他処理と組み合わさった場合もう少し遅くなる見込みですが、それでもは向上していると思います。

次に1000000個のキーと要素が追加されている状態で、1000000回インデクサー経由で値を取得した場合の計測結果になります。

Method Mean Error StdDev Min Max Ratio RatioSD Rank Allocated Alloc Ratio
OrderedDictionary_Indexer 28.18 ms 1.671 ms 2.449 ms 24.70 ms 33.72 ms 1.01 0.12 2 12 B 1.00
OrderedDictionaryForNonGeneric_Indexer 67.20 ms 0.896 ms 1.255 ms 64.95 ms 70.54 ms 2.40 0.20 3 50 B 4.17
Dictionary_Indexer 25.04 ms 0.511 ms 0.717 ms 23.91 ms 26.20 ms 0.90 0.08 1 12 B 1.00

ジェネリック版と比較すると約2倍の高速化、アロケーションも約4倍削減とこちらもパフォーマンスがかなり向上しているようです。
またDictionaryと比較しても、同じぐらい（わずかにおそい程度）の速度で実行されているため、要素取得についてもパフォーマンスは向上していると思います。

その他

DictionaryやHashSetに追加されたGetAlternateLookupメソッドがOrderedDictionaryには実装されていないため、キーに指定した型のみでしか検索できないようです。

おわりに

ちょっとしたアプリを作成しているときなどに、順番を保持したハッシュテーブルが必要になることがありました。そのたびに順番保持用のListを作成したりするなどちょっとした手間が発生していました。
.NET 9からは、自前実装する必要なくパフォーマンスが良いジェネリック版を使用することができるため、積極的に使用していきましょう！
C# Advent Calendar 2024、9日目は@akiojinさんです。
よろしくお願いいたします！

9
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?