Неожиданные плохие результаты SortedDictionary по сравнению с Словарем

Я не понимаю, почему производительность SortedDictionary примерно на 5 раз медленнее, чем Словарь для установки и извлечения значений. Я ожидал, что вставки и удаления будут медленнее, но не будут обновляться или извлекаться. Я протестировал .Net 3.5 и .Net 4.0, выпустил скомпилированный код. Массив случайных ключей был предварительно вычислен для обеспечения того, чтобы случайные вариации не отвечали за различия в произвольном доступе.

Ниже приведены следующие сценарии.

• Последовательное обновление каждого значения с помощью [key] accessor
• Последовательный доступ каждого значения с помощью [key] accessor
• Последовательный доступ каждого значения с помощью TryGetValue
• Случайный доступ к каждому значению с помощью [key] accessor
• Случайный доступ к каждому значению с помощью TryGetValue

Кто-нибудь знает, почему разница в производительности?

Пожалуйста, если я делаю что-то неправильно или глупо, укажите это.

Пример кода: просто выберите словарь с SortedDictionary, чтобы проверить разницу.

    const int numLoops = 100;
    const int numProperties = 30;
    const int numInstances = 1000;

    static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray)
    {
        Stopwatch sw = new Stopwatch();
        double total = 0.0d;

        for (int j = 0; j < numLoops; j++)
        {
            //sw.Start();
            Dictionary<string, object> original = new Dictionary<string, object>(numValues);
            for (int i = 0; i < numValues; i++)
            {
                original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString());
            }
            List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances);
            for (int i = 0; i < numInstances; i++)
            {
                collectionList.Add(new Dictionary<string, object>(original));
            }
            sw.Start();
            //Set values on each cloned instance to uniqe values using the same keys
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString();
                }
            }

            //Access each unique value
            object temp;
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    temp = collectionList[k]["Key" + i.ToString()];
                }
            }
            //Random access
            //sw.Start();
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k].TryGetValue(keyArray[i],out temp);
                }
            }
            sw.Stop();
            total += sw.ElapsedMilliseconds;
            sw.Reset();
        }

Ответы

Ответ 1

SortedDictionary использует поиск двоичного поиска, который является O ( log n).
Dictionary использует хэш-таблицу, которая является O (1).

Следовательно, Dictionary дает быстрый поиск.

Разница будет еще больше с строковыми клавишами, которые стоить сравнивать.
A Dictionary будет повторять только строку дважды (или больше, если есть хеш-коллизии) - один раз, чтобы вычислить хэш-код, и один раз, чтобы обеспечить точное соответствие. A SortedDictionary будет перебирать строку для каждого сравнения.

Ответ 2

Я не думаю, что это необычно. Другие получили те же результаты.

Я думаю, что это довольно просто, почему каждый будет медленнее, чем другой. SortedDictionary делает больше. Это сортировка. Словарь не является, поэтому он быстрее.

Единственное истинное испытание того, что должно и не должно быть исполнено, - это тест, который вы выполняете выше. Я не думаю, что вы делаете что-то не так.