.NET Framework - Есть ли способ сделать Dictionary <> немного быстрее?

Question

Я делаю поиск Dictionary<> в цикле O (n ^ 2) и мне нужно, чтобы он был смехотворно быстрым.Это не.Кто-нибудь знает, как реализовано Dictionary<>?Я тестирую производительность словаря с помощью изолированного тестового примера после запуска моего кода через профилировщик и определения, что поиск по словарю составляет основную часть процессорного времени. Мой тестовый код выглядит следующим образом:

Int32[] keys = new Int32[10] { 38784, 19294, 109574, 2450985, 5, 398, 98405, 12093, 909802, 38294394 };

Dictionary<Int32, MyData> map = new Dictionary<Int32, MyData>();
//Add a bunch of things to map


timer.Start();
Object item;
for (int i = 0; i < 1000000; i++)
{
   for (int j = 0; j < keys.Length; j++)
   {
      bool isFound = map.ContainsKey(keys[j]);
      if (isFound)
      {
         item = map[keys[j]];
      }
   }
}
timer.Stop();

ContainsKey и map[] - это две медленные части (одинаково медленные). Если я добавлю TryGetValue, он почти идентичен по скорости ContainsKey.Вот некоторые интересные факты ..

A Dictionary<Guid, T> примерно вдвое медленнее, чем Dictionary<Int32, T>.Dictionary<String, T> примерно вдвое медленнее словаря Guid.A Dictionary<Byte, T> на 50% быстрее, чем использование Ints.Это наводит меня на мысль, что Словарь выполняет O (log n) двоичный поиск, чтобы найти ключ, а операторы сравнения на ключах являются узким местом.По какой-то причине я не верю, что он реализован как Hashtable, потому что .NET уже имеет класс Hashtable, и, по моему опыту, он даже медленнее, чем Dictionary.

Доступ к создаваемым мной словарям доступен толькопо одному потоку за раз, поэтому блокировка чтения не является проблемой.ОЗУ тоже не проблема.В словаре, скорее всего, будет только около 10 сегментов, но каждый блок может указывать на одну из около 2000 возможных вещей.У кого-нибудь есть отзывы о том, как сделать это быстрее?Спасибо!

Майк

Answer 1

Словарь реализован с использованием хеш-таблицы, я посмотрел код с помощью Reflector некоторое время назад.

"Словарь скорее всего будет только есть около 10 ведер, но каждый ведро может указывать на один из около 2000 возможно вещи. "

Есть ваша проблема. Словарь использует хеш для поиска сегмента, но поиск в блоке является линейным.

Вы должны реализовать алгоритм хеширования с лучшим распределением, чтобы получить лучшую производительность. Соотношение должно быть как минимум противоположным, то есть 2000 ведер по 10 штук в каждом.

Answer 2

В дополнение к комментариям о создании собственной реализации, основанной на знании данных, вот пример, который не будет иметь противоречий.Это может вызвать исключения OutOfMemoryException в зависимости от размера объектов.Я попытался с помощью индексации int, но это будет исключение OutOfMemoryException.Если возвращается значение null, элемент не существует.

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

public class QuickLookup<T> where T : class
{
    private T[] _postives = new T[short.MaxValue + 1];
    private T[] _negatives = new T[short.MaxValue + 1];
    public T this[short key]
    {
        get
        {
            return key < 0 ? _negatives[(key * -1) - 1] : _postives[key];
        }
        set
        {
            if (key < 0)
                _negatives[key * -1] = value;
            else
                _postives[key] = value;
        }
    }
}

Answer 3

Проницательность во внутреннюю работу хэш-таблицы очевидна.Вам определенно следует использовать TryGetValue в качестве всего внутреннего цикла:

  map.TryGetValue(keys[j], out item);

при выполнении ContainsKey, а Item [] выполняет сложную часть (поиск) дважды.Дополнительные if и дополнительные клавиши [j] являются второстепенными, но будут складываться в тесном цикле.Использование foreach над вашими ключами, вероятно, будет медленнее, но в зависимости от фактического содержимого цикла это может стоить профилирования.

Answer 4

Похоже, вы говорите, что в вашем словаре будет только 10 элементов. Если это так, хеш-таблица может быть необоснованной. Вы можете просто сохранить свои данные в списке / массиве и либо выполнить итерацию по ним, либо использовать двоичный поиск, чтобы найти ваши ключи (попробуйте оба, чтобы увидеть, что быстрее).

Если вы используете бинарный поиск, ваш список должен быть отсортирован; если вы просто перебираете свой список, и некоторые ключи просматриваются чаще, чем другие, вы можете поместить их в начало списка, чтобы ускорить процесс.

С другой стороны, если ваши ключи известны заранее, вы можете написать собственную реализацию хеш-таблицы с быстрой и совершенной хеш-функцией (т.е. без коллизий), и это должно быть непобедимым.

Answer 5

Если у вас есть только 10 блоков по 2000 штук в каждом, можете ли вы просто создать один список со всеми 20000 вещами, которые можно напрямую проиндексировать с помощью ключа, известного вашему циклу? Например:

List<MyData> = new List(); 

//add all items to list indexed by their key (RAM is not an issue right?)

item = ItemList[key];

Таким образом, вы можете ссылаться на них напрямую без словаря или хеш-поиска.