SortedListとSortedDictionary

あまりSortedDictionaryはあまり使ったことがないのですが、

何が違うんだろうとちょっと疑問に思ったので調べてみた。

SortedList コレクション型と SortedDictionary コレクション型

第2回 ジェネリック − ＠IT

上のリンクの下のほうにある表にある「取得は O(log n) です。」の意味がよくわからなかった（後で調べた - ランダウの記号 - Wikipedia）。

下のリンクのこれまた下のほうにSortedDictionaryクラスの特徴が簡潔にまとめられていたので

それをみてSortedListのほうが速く取り出せるということがわかった。

で、一応自分でも試してみた。

はじめはSortedListの例。100万回追加してみる。

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var listWatch = new Stopwatch();
            var list = new SortedList<int, string>();

            listWatch.Start();

            for (int i = 0; i < 1000000; i++)
            {
                
                list.Add(i, i.ToString());
            }

            listWatch.Stop();

            Console.WriteLine(listWatch.Elapsed.ToString());
            Console.ReadKey();
        }
    }
}

結果は00:00:00.5657404。

次はSortedDictionary。

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

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var sortedDictionary     = new SortedDictionary<int, string>();
            var sortedDictionaryWatch = new Stopwatch();
            
            sortedDictionaryWatch.Start();

            for (int i = 0; i < 1000000; i++)
            {
                sortedDictionary.Add(i, i.ToString());
            }
            sortedDictionaryWatch.Stop();

            Console.WriteLine(sortedDictionaryWatch.Elapsed.ToString());

            Console.ReadKey();
        }
    }
}

結果は00:00:01.6936629。

随分差が出るなぁ。