Нахождение минимального значения в словаре за O (1) раз Python

Question

Мне нужен способ найти минимальное значение в словаре, полном объектов Node, за O (1) время или действительно любое сублинейное время, если это возможно.

Вот пример того, что мне нужно :

'''
 Nodes have 4 attributes: 
  - stack
  - backwards
  - forwards
  - total_score
'''
dict = {str(Node1.stack): Node1, 
        str(Node2.stack): Node2, ... } # note that keys are the stacks as strings

key, smallest = min(frontier.items(), key=lambda pair: pair[1].total_score)
( ^^^ something better than this! ^^^ )

Последняя строка выше (ключ, наименьшее ...) - это то, что у меня есть. Работает нормально, но слишком медленно. Я читал в Интернете, что функция min () занимает время O (n). У меня много узлов для обработки, поэтому что-то более быстрое было бы удивительно.

edit Должно быть упомянуто ранее, но это выполняется внутри алгоритма A * - граница обновляется динамически. Мне нужно выполнить следующие операции:

1. Найти минимум в O (1) или, по крайней мере,
2. Обновить значения указанных элементов c быстро
3. легкий доступ к атрибутам

Answer 1

Невозможно получить минимальное значение из словаря за время O (1), потому что вы должны проверить каждое значение. Однако вы можете выполнить быстрый поиск, если храните данные в куче или отсортированном дереве, где данные сортируются по значению. Деревья обычно дают вам время вставки и поиска O (log n).

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

Answer 2

Невозможно получить наименьшее значение в словаре в O (1), это займет O (n).

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