Назначение ключей для быстрого поиска в python

Question

У меня будет 1 небольшой словарь (от 5 до 20 ключей), на который будет ссылаться до сотни раз или около того для загрузки одной страницы в Python 2.5.

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

Answer 1

Я должен был проверить; -)

с использованием

• f1, целочисленная клавиша 1
• f2 короткая строка, "one"
• длинная строка f3 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

как один из ключей в словарь длины 4. Итерация 10 000 000 раз и измерение времени. Я получаю этот результат:

<function f1 at 0xb779187c>
f1 3.64
<function f2 at 0xb7791bfc>
f2 3.48
<function f3 at 0xb7791bc4>
f3 3.65

Т.е. без разницы ...

Мой код

Answer 2

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

Возьмем, к примеру, этот тест времени на моем 4-летнем настольном компьютере (со смешным низкобюджетным двухъядерным процессором с 3,1 ГГц):

...>python -mtimeit --setup="d = {chr(i)*100: i for i in range(15)};\
k = chr(7)*100" "d[k]"

1000000 loops, best of 3: 0.222 usec per loop

И эти строки в десятки раз больше, чем все, что имеет смысл вводить вручную в качестве имени переменной. Сокращение длины от 100 до 10 приводит к 0,0778 микросекундам за поиск. Теперь измерьте скорость загрузки вашей страницы и сравните ее (в качестве альтернативы просто подумайте, сколько времени займет работа, которую вы фактически делаете при создании страницы); и принять во внимание кэширование, издержки фреймворка и все эти вещи.

Ничто из того, что вы делаете в этом отношении, не может повлиять на производительность, период, полный останов.

Answer 3

Поскольку хеш-функция Python выполняет итерации по символам (по крайней мере, если этот по-прежнему применим), я бы выбрал короткие строки.

Answer 4

Чтобы добавить еще один аспект:

для очень маленьких словарей и жестких временных ограничений, время для вычисления хэшей может составлять существенную долю общего времени.Следовательно, для, скажем, 5 элементов, может быть быстрее использовать массив и последовательный поиск (конечно, заключенный в некоторый объект MiniDictionary), возможно, даже дополненный двоичным поиском.Это может найти элемент с 2-3 сравнениями, которые могут быть или не быть быстрее, чем хеш-вычисления плюс одно сравнение.

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

Answer 5

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