け日記

SIerから転職したWebアプリエンジニアが最近のITのキャッチアップに四苦八苦するブログ

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

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

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

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

  1. キーの値を連結するなどして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]);
  1. 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]);
  1. 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.を採用することが多いかと思います。

で、どっちを使うかですが、実装レベルではキーを1つにまとめられる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>>のデータ構造を使う、というのが妥当な線ですね。