Какой тип ключа для словарей самый быстрый в python? кортеж, фрозенсет ...?

Question

Контекст: я пытаюсь ускорить время выполнения k-средних. Для этого я предварительно вычисляю средние перед выполнением k-средних. Эти средние значения хранятся в словаре means_dict, который имеет в качестве ключа последовательность идентификаторов точек, упорядоченных в порядке возрастания и затем соединяющихся подчеркиванием, а в качестве значения - среднее значение этих точек. Когда я хочу получить доступ к среднему значению заданных точек в словаре dict_mean во время выполнения k-средних, я должен сгенерировать ключ этого набора точек, то есть упорядочить точки идентификаторов в порядке возрастания и соединить их подчеркиванием. Инструкция генерации ключа занимает много времени, потому что ключ может содержать тысячи целых чисел.

У меня есть для каждого ключа последовательность целых чисел, разделенных подчеркиванием "-" в словаре. Я должен отсортировать последовательность целых чисел, прежде чем соединять их подчеркиванием, чтобы сделать ключ уникальным, и в итоге я получаю строковый ключ. Проблема в том, что этот процесс так долго. Я хочу использовать другой тип ключа, который позволяет избежать сортировки последовательности, и этот тип ключа должен быть быстрее, чем тип строки с точки зрения доступа, сравнения и поиска.

 # means_dict is the dictionary containing as a key a string (sequence of 
 # integers joined by underscore "-", for example key="3-76-45-78-344")
 # points is a dictionary containing for each value a list of integers
 for k in keys:
     # this joining instruction is so long       
     key = "_".join([ str(c) for c in sorted(points[k])])        
     if( key in means_dict ):
         newmu.append( means_dict[key] )

Answer 1

Вычисление средств дешево.

Вы профилировали свою программу? Сколько времени он тратит на перерасчет, который он имеет в виду? С правильными массивами numpy вместо упакованных в Python массивов это должно быть чрезвычайно дешево - определенно дешевле, чем создание любого такого ключа!

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

Можно даже использовать подход MacQueens для обновления , а не пересчитывать их. Но даже это часто медленнее, чем их пересчет.

Я не удивлюсь, если ваш подход окажется в 10 раз медленнее, чем обычные k-средства ... И, вероятно, в 1000 раз медленнее, чем умные алгоритмы kmeans, такие как Хартиган и Вонг.