Добавить ключи в словаре в отсортированном порядке

Question

Пусть у меня есть словарь

{1:5, 2:5, 4:5} 

Есть ли структура данных таким образом, что, если добавить пару ключ-значение 3:5, чтобы ввести его в словаре, так что ключи находятся в порядке сортировки? т.е.

{1:5, 2:5, 3:5, 4:5} 

Я отдаю себе отчет в collections.OrderedDict(), но это только хранит ключи в том порядке, в котором они были добавлены (который не является достаточным для меня в настоящее время).

Я не хочу использовать обычный словарь dic = {}, затем должен использовать sorted(dic)[0], чтобы захватить самый маленький ключ. Я бы предпочел бы функцию типа sorted_dict[0].
Причина в том, что если я использую обычный словарь, мне придется много раз вызывать сортировку, так как я постоянно добавляю пары в словарь.

EDIT: Я хотел бы упомянуть, это не только самые маленькие и крупные ключи я забочусь о, мне также нужно напечатать этот словарь через регулярные промежутки времени, а также ...

Answer 1

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

Если вы посмотрите на PyPI, вы найдете несколько вариантов. Моя рекомендация будет blist. Несмотря на то, что структура данных может быть не такой оптимальной, как некоторые из других (поскольку дерево B + намного шире, чем двоичное дерево), это, вероятно, достаточно для почти любого использования, с которым вы столкнетесь. И он имеет полный и проверенный интерфейс, включая проверенные гарантии производительности. И он используется совсем по другим серьезным проектам.

Если вы имеете дело с одним из редких случаев, когда производительность дерева действительно имеет решающее значение, вероятно, вам следует взглянуть на различные варианты красно-черного дерева, splay tree, skiplist и т. Д. Раньше я использовал bintrees, у которого отличный интерфейс (например, вы можете получить доступ к ключам и значениям по индексу и даже разрезать дерево, а также обрабатывать его как dict, и автор продумал и избегал всех потенциальные двусмысленности), но я серьезно не тестировал его.

Или, если ваши ключи и значения действительно являются маленькими целыми числами, вы можете захотеть использовать Cython для переноса C++ map<int, int> в интерфейс Pythonic. (Невозможно предоставить полный интерфейс поверх C++ map, но вам это вообще не нужно.) Или, альтернативно, измените одну из реализаций, например bintrees.FastRBTree, чтобы сохранить и сравнить long вместо PyObject*.

С другой стороны, если вы только собираетесь создать словарь сразу, а затем использовать его, есть гораздо более простой ответ. Сортируйте его и вставьте его в OrderedDict. Тогда вам ничего не нужно за пределами stdlib.

sorted_dict = collections.OrderedDict(sorted(d.iteritems())) 

---

Из комментария на другой ответ, вы говорите «я не имеют разрешения для установки новых модулей ...»

Во-первых, убедитесь, что это действительно так. Вероятно, у вас есть . имеют разрешение на установку модулей в каталоге сайта user-packages. Или, если установлено virtualenv и/или вы используете 3.3 со встроенным venv, еще лучше, у вас, вероятно, есть разрешение на создание venv и установка модулей в это.

Но если да, то вам нужно скопировать файлы с blist/bintrees/что угодно в ваш проект.

Проблема, с которой вы столкнулись, состоит в том, что большинство этих пакетов содержат модули расширения C, что означает, что вы должны иметь возможность их создавать (ну, build_ext -i их). Если в вашей системе нет файлов-разработчиков Python и установлена ​​цепочка инструментов компилятора, вы не сможете этого сделать. В этом случае вы ищете лучшее решение pure-Python. bintrees поставляется с реализацией pure-Python, которая идентична обычной реализации C-расширения, кроме более медленной. Конечно, все равно O (log N), просто постоянный коэффициент намного выше. Если N достаточно велико, это все равно огромная победа; если нет, может и не быть.

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

Answer 2

Попробуйте этот рецепт - http://code.activestate.com/recipes/576998-sorted-dictionary/

Сохраняет ключи, отсортированные по модулю stdlib bisect.

Answer 3

Больше чем на год поздно вечером, но я хотел бы предложить модуль sortedcontainers. Подобно blist и bintrees, он предоставляет тип данных SortedDict, который поддерживает ключи в отсортированном порядке. В отличие от этих модулей, он написан на чистом Python и на самом деле быстрее. SortedDict также поддерживает индексирование. Глядя на мин/макс, на самом деле происходит в O (1) раз.

Поскольку это чисто Python, установка с пип должен быть ветер:

pip install sortedcontainers 

Тогда вы можете просто импортировать SortedDict

In [1]: from sortedcontainers import SortedDict 

In [2]: d = SortedDict({1:5, 2:5, 4:5}) 

In [3]: d 
Out[3]: SortedDict({1: 5, 2: 5, 4: 5}) 

In [4]: d[3] = 5 

In [5]: d 
Out[5]: SortedDict({1: 5, 2: 5, 3: 5, 4: 5}) 

Если у вас есть трудности с установкой вещи, используя пип или может» t скопируйте файлы, которые необходимо будет компилировать, тогда вы можете просто вытащить файлы sortedlist.py и sorteddict.py из хранилища. Весь код: open source on github.

Модуль отсортированных контейнеров также предоставляет performance comparison самые популярные предложения, сравниваемые друг с другом.