Почему меньший набор данных замедляет поиск в TDictionary?

Delphi , Компоненты и Классы , Коллекции

Вопрос, поднятый Tony Stone, касается неожиданного поведения производительности TDictionary из библиотеки Generics.Collections при работе с различными объемами данных. Приведенные наблюдения показывают, что при работе с большим набором данных (18 миллионов элементов) скорость поиска выше, чем при работе с меньшим набором (39 тысяч элементов). Давайте разберемся в возможных причинах такого поведения.

Внутреннее устройство TDictionary

TDictionary — это обобщенный класс, предоставляющий хэш-таблицу для хранения пар ключ-значение. Внутренняя реализация включает в себя хэш-функцию, которая распределяет элементы по "ведрам" (buckets), и механизм управления этими ведрами.

Влияние размера на производительность

Эффект кэширования

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

Количество коллизий

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

Использование простых чисел

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

const
  NPRIMES = 28;
  PRIMELIST: array[0 .. NPRIMES-1] of Longword =
  (
    ...
  );

Пример кода для выбора простого числа

function GetNearestPrimeCapacity(Capacity: LongInt): LongInt;
var
  i: Integer;
begin
  Result := Capacity;
  if Capacity <= 0 then
    Exit;

  if Capacity > PRIMELIST[NPRIMES - 1] then
    Capacity := PRIMELIST[NPRIMES - 1];

  for i := 0 to NPRIMES - 1 do
    if PRIMELIST[i] > Capacity then
      Break;

  Result := PRIMELIST[i];
end;

Альтернативные реализации

Benny также упомянул о наличии альтернативных реализаций хэш-таблиц в библиотеке LGenerics на GitHub, которые могут предложить более высокую производительность.

Заключение

Для улучшения производительности поиска в TDictionary можно попробовать следующие шаги:

1. Выбрать размер хэш-таблицы, основанный на простом числе, используя функцию GetNearestPrimeCapacity.
2. Протестировать альтернативные реализации хэш-таблиц, например, из библиотеки LGenerics.
3. Изучить книгу "Tomes of Delphi - Algorithms and Data-structures" для глубокого понимания алгоритмов хэширования.

Применение этих рекомендаций может помочь оптимизировать работу с TDictionary и улучшить скорость поиска, особенно для меньших наборов данных.

Создано по материалам из источника по ссылке.

Контекст обсуждает причины неожиданной высокой производительности TDictionary при работе с большими объемами данных, связанные с кэшированием, коллизиями и использованием простых чисел для размера хэш-таблицы.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Коллекции ::