Оптимизация скоростей поиска в словаре Python путем сокращения размера ключа?

Я не понимаю, что происходит за кулисами поиска в словаре. Имеет ли фактор размера ключа скорость поиска этого ключа?

Текущие словарные ключи находятся между 10-20 длинными, буквенно-цифровыми.

Мне нужно делать сотни поисков в минуту.

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

Также мне нужно будет изменить программу для поиска идентификатора, а затем получить URL-адрес, связанный с идентификатором.

Могу ли я просто добавить сложность в программу с небольшой пользой?

2 Solutions collect form web for “Оптимизация скоростей поиска в словаре Python путем сокращения размера ключа?”

Словари – это хеш-таблицы, поэтому поиск ключа состоит из:

  • Хеш ключ.
  • Уменьшите хэш до размера стола.
  • Индексируйте таблицу с результатом.
  • Сравните поисковый ключ с ключом ввода.

Обычно это амортизируемое постоянное время, и вам все равно, чем больше. Есть две потенциальные проблемы, но они часто возникают.


Хеширование клавиши занимает линейное время в длине ключа. Для, например, огромных строк это может быть проблемой. Однако, если вы посмотрите на исходный код для большинства важных типов, включая [ str / unicode ] ( https://hg.python.org/cpython/file/default/Objects/unicodeobject.c , вы увидите, что они кэшируют хэш в первый раз.Таким образом, если вы не вводите (или произвольно создаете или что-то еще) цепочку строк для поиска один раз, а затем выбрасываете, это вряд ли будет проблемой в большинстве реальных программ.

Кроме того, 20 символов действительно очень короткие; вы, вероятно, можете делать миллионы таких хэшей в секунду, а не сотни.

Из быстрого теста на моем компьютере хеширование 20 случайных букв занимает 973ns, хеширование 4-значного числа занимает 94ns, а хэширование значения, которое я уже сделал, занимает 77ns. Да, это наносекунды.


Между тем, «Индексировать таблицу с результатом» – это немного обманщик. Что произойдет, если два разных хэша ключей имеют один и тот же индекс? Тогда «сравнить проверенный ключ» не удастся, и … что будет дальше? Реализация CPython использует для этого исследование. Точный алгоритм очень хорошо объясняется в источнике . Но вы заметите, что, учитывая действительно патологические данные, вы можете сделать линейный поиск для каждого элемента. Это никогда не придет – если кто-то не сможет атаковать вашу программу, явным образом создавая патологические данные, и в этом случае она обязательно придет.

Переключение с 20-символьных строк на 4-значные цифры тоже не помогло бы. Если я создаю ключи к DoS вашей системе с помощью коллизий со словарями, мне все равно, как выглядят ваши фактические ключи, только то, что они имеют.


В более общем плане преждевременная оптимизация – это корень всего зла . Это иногда неверно цитируется, чтобы завысить точку; Кнут утверждал, что самое главное – найти 3% случаев, когда важна оптимизация, а не то, что оптимизация всегда пустая трата времени. Но в любом случае, дело в том, что если вы не знаете заранее, где ваша программа слишком медленная (и если вы думаете, что знаете заранее, вы обычно ошибаетесь …), профайл, а затем найдите ту часть, где вы получите максимальную отдачу за свой доллар. Оптимизация одной произвольной части вашего кода, скорее всего, не окажет никакого измеримого эффекта.

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

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

  • Преобразование Python в kwargs?
  • Что такое реализация хеш-таблицы / словаря для Python, которая не хранит ключи?
  • Доступ к элементам в заказе
  • Суммировать соответствующие элементы из нескольких словарей python
  • Почему изменение dict во время итерации не всегда вызывает исключение?
  • Преобразование строки cookie в Python dict
  • Объединить словарь python множеств
  • Python 2.6 TreeMap / SortedDictionary?
  • Python - лучший язык программирования в мире.