Улучшение производительности очень большого словаря в Python

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

Я подозреваю, что проблема в том, что словарь не знает количества ключей во время init, и он не делает что-то очень умное, поэтому, возможно, столкновение с хранилищем становится довольно часто, и оно замедляется.

Если я знаю количество ключей и именно то, что есть эти ключи, есть ли способ в python, чтобы сделать dict (или хэш-таблицу) более эффективным? Я смутно помню, что, если вы знаете ключи, вы можете хорошо спланировать хэш-функцию (идеальный хеш?) И заранее выделить пространство.

Ответ 1

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

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

Тем не менее, если ключи всегда известны заранее, вы можете сохранить их в set и построить свои словари из набора используя dict.fromkeys(). Этот метод класса оптимизирован для предварительного размера словаря на основе заданного размера и может заполнять словарь без каких-либо новых вызовов __hash __():

>>> keys = {'red', 'green', 'blue', 'yellow', 'orange', 'pink', 'black'}
>>> d = dict.fromkeys(keys)  # dict is pre-sized to 32 empty slots

Если сокращение коллизий является вашей целью, вы можете запускать эксперименты по порядку вставки в словаре, чтобы минимизировать нагромождения. (Взгляните на вариацию Brent на алгоритм D в Knuth TAOCP, чтобы понять, как это делается).

Используя инструментарий чистой модели Python для словарей (например, этот), можно подсчитать средневзвешенное число зондов для альтернативный порядок вставки. Например, вставка dict.fromkeys([11100, 22200, 44400, 33300]) в среднем составляет 1,75 пробы на поиск. Это превосходит средние значения 2,25 для каждого поиска для dict.fromkeys([33300, 22200, 11100, 44400]).

Другой "трюк" заключается в увеличении яркости в полностью заполненном словаре путем обмана его в увеличение его размера без добавления нового ключа s:

 d = dict.fromkeys(['red', 'green', 'blue', 'yellow', 'orange'])
 d.update(dict(d))     # This makes room for additional keys
                       # and makes the set collision-free.

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