C#: Dictionaryのキーに複数の値を使う

Dictionaryのキーに複数の値を使う方法について、考察してみます。

Dictionaryのキーに複数の値を使う方法

Dictionaryのキーに複数の変数値を使いたい場合（例えば、クラス名と出席番号をキーとして氏名を値とする、など）にいくつかの方法が考えられますが、以下3つに分類されるかと思います。

キーの値を連結するなどして1つのキーを作成する

var className = "Aクラス";
var number = 1;
var name = "荒岩 一味";

var students = new Dictionary<string, string>();
students.Add(className + number, name);
Console.WriteLine(students[className + number]);

Dictionaryを値とするDictionaryを作成する（Dictionary<TKey1, Dictionary<TKey2, TValue>>）

var students = new Dictionary<string, Dictionary<int, string>>();
students.Add(className, new Dictionary<int, string>{ { number, name } });
Console.WriteLine(students[className][number]);

Tupleをキーとする（Dictionary<Tuple<TKey1, TKey2>, TValue>）

var students = new Dictionary<Tuple<string, int>, string>();
students.Add(new Tuple<string, int>(className, number), name);
Console.WriteLine(students[new Tuple<string, int>(className, number)]);

1.は気軽に実装できるのですが、キーの型が異なる場合に型変換を行う必要があったり、結合した結果キーが重複する場合（"クラス1"と"23"、"クラス12"と"3"は結合するといずれも"クラス123"となる）を考慮しないといけないなど、使えるケースは限定的です。

実際の開発ではキーの型と同一性が保証される2.か3.を採用することが多いかと思います。

で、どっちを使うかですが、実装レベルではキーを１つにまとめられるTupleを使う3.の方法の方が素直だと思います。 2.の方法では、値（TValue）を追加・参照するたびに、上位のDictionaryのキー（TKey1）の有無を常にチェックする必要があるのも面倒です。

性能は状況により異なりそうですが、2.の方が分は良さそうです。

追加・参照のたびにTupleを生成する必要がある
TKey1が値の数に比べて少ない場合は、メモリ効率が良い（TKey1が集約されるため）

性能比較

それぞれの方法でDictionaryに値を追加・参照するコードを使って、両者の性能を比較してみます。

firstKeyPatternは上位のDictionaryのキー（TKey1）、secondKeyPatternは下位のDictionaryのキー（TKey2）のパターン数です。例えば、firstKeyPatternが2、secondKeyPatternが3の場合、キーは（"0", 0）、（"0", 1）、（"0", 2）、（"1", 0）、（"1", 1）、（"1", 2）の6パターンとなります。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var firstKeyPattern = 1;
            var secondKeyPattern = 1000000;

            var sw = new Stopwatch();
            var name = "荒岩 一味";

            sw.Start();
            var firstDictionary = new Dictionary<string, Dictionary<int, string>>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                var secondDictionary = new Dictionary<int, string>();
                for (int j = 0; j < secondKeyPattern; j++)
                {
                    secondDictionary.Add(j, name);
                }
                firstDictionary.Add(i.ToString(), secondDictionary);
            }
            sw.Stop();
            Console.WriteLine("2.(Add): " + sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            var list = new List<string>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                if (firstDictionary.ContainsKey(i.ToString()))
                {
                    for (int j = 0; j < secondKeyPattern; j++)
                    {
                        if (firstDictionary[i.ToString()].ContainsKey(j))
                        {
                            list.Add(firstDictionary[i.ToString()][j]);
                        }
                    }
                }
            }
            sw.Stop();
            Console.WriteLine("2.(Get): " + sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            var tupleDictionary = new Dictionary<Tuple<string, int>, string>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                for (int j = 0; j < secondKeyPattern; j++)
                {
                    tupleDictionary.Add(new Tuple<string, int>(i.ToString(), j), name);
                }
            }
            sw.Stop();
            Console.WriteLine("3.(Add): " + sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            list = new List<string>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                for (int j = 0; j < secondKeyPattern; j++)
                {
                    var key = new Tuple<string, int>(i.ToString(), j);
                    if (tupleDictionary.ContainsKey(key))
                    {
                        list.Add(tupleDictionary[key]);
                    }
                }
            }
            sw.Stop();
            Console.WriteLine("3.(Get): " + sw.ElapsedMilliseconds);
        }
    }
}

Macbook Pro（.net core 1.1）の環境で実行した結果は以下の通りでした。

TKey1のパターンが少ない場合は、2.の方法が性能的には優位
最悪ケース(firstKeyPattern=1000000, secondKeyPattern=1)でも両者の性能差はそれほど無い
- Tupleの生成や比較にかかるコストが高そう

実行時間(ms)	2.値の追加	2.値の参照	3.値の追加	3.値の参照
firstKeyPattern=1, secondKeyPattern=1000000	60	359	600	781
firstKeyPattern=1000, secondKeyPattern=1000	124	345	691	726
firstKeyPattern=1000000, secondKeyPattern=1	978	741	853	937

まとめ

複数の変数を組み合わせてDictionaryのキーとする方法をそれぞれ比較してみました。

実装の素直さを優先したり格納するデータが少ない場合はDictionary<Tuple<TKey1,TKey2>, TValue>、データ数が多く一方のキーに重複が多い（カーディナリティが低い）場合はDictionary<TKey1, Dictionary<TKey2, TValue>>のデータ構造を使う、というのが妥当な線ですね。