8

假设我有一本字典

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

是否有这样的数据结构，如果我添加键值对3:5，将其输入到字典中，以便键按排序顺序排列？IE

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

我知道collections.OrderedDict()，但这只会使键保持添加顺序（目前这对我来说还不够）。

我不想必须使用普通字典dic = {}，然后必须使用sorted(dic)[0]抓取最小的键。我宁愿有sorted_dict[0]类型功能。
这样做的原因是，如果我使用普通字典，我将不得不多次调用排序，因为我不断地将对添加到我的字典中。

编辑：我应该提到，这不仅是我关心的最小和最大键，我还需要定期打印这本字典......

4

3 回答 3

5

如果您打算连续地从字典中添加和删除键，那么您确实需要使用适当的数据结构来解决问题的东西——不是哈希表（或哈希表加列表，如SortedOrderedDict-type 配方），而是平衡树（或等价物，如跳过列表）。

如果您环顾一下 PyPI，您会发现许多选项。我的建议是blist。尽管它的数据结构可能不如其他一些结构那么优化（因为 B+Tree 比二叉树宽得多），但对于您遇到的几乎所有用例来说，它可能已经足够好了。并且它具有完整且经过良好测试的界面，包括经过良好测试的性能保证。它被其他严肃的项目大量使用。

如果您正在处理树性能确实很关键的罕见情况之一，您可能应该查看各种红黑树、展开树、跳过列表等实现。我以前用过bintrees，它有一个很棒的接口（例如，您可以通过索引访问键和值，甚至可以对树进行切片，以及将其视为 a dict，并且作者已经考虑并避免了所有潜在的歧义)，但我还没有认真地测试过它。

或者，如果您的键和值确实都是较小的整数，您可能需要考虑使用 Cython 将 C++ 包装map<int, int>在 Pythonic 接口中。（在 C++ 之上提供一个完整的接口是不太可能的map，但无论如何您通常都不需要它。）或者，或者，修改其中一个实现，例如bintrees.FastRBTree存储和比较long而不是PyObject*.

另一方面，如果您只是要一次创建所有字典然后使用它，则有一个更简单的答案。对其进行排序，并将其粘贴在OrderedDict. 那么你不需要标准库之外的任何东西。

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

从对另一个答案的评论中，您说“我无权安装新模块......”

首先，确保这是真的。您可能确实有权在用户站点包目录中安装模块。或者，如果virtualenv已安装和/或您使用 3.3 和 built-in venv，更好的是，您可能有权创建 venv 并将模块安装到其中。

但如果是这样，您需要做的就是将文件从blist/ bintrees/whatever 复制到您的项目中。

您可能遇到的问题是这些包中的大多数都包含 C 扩展模块，这意味着您必须能够构建它们（嗯，build_ext -i它们）。如果您的系统没有安装 Python 开发文件和编译器工具链，则不能这样做。在这种情况下，您正在寻找最好的纯 Python 解决方案。bintrees带有一个纯 Python 实现，它与普通的 C 扩展实现相同，但速度较慢。当然，它仍然是 O(log N)，只是常数因子要高得多。如果 N 足够大，它仍然是一个巨大的胜利；如果不是，它可能不是。

如果这听起来很合理，但是您需要帮助设置每个用户的站点包或虚拟环境，或者将模块复制到您的项目中，或者就地构建扩展等，您可能应该搜索对于现有问题，如果找不到问题，请提出新问题（如果没有其他原因，只是因为那些擅长安装问题的人不一定是数据结构方面的专家，甚至可能不会阅读本文问题）。

于 2013-03-19T05:29:59.227 回答
3

试试这个食谱——http: //code.activestate.com/recipes/576998-sorted-dictionary/

它使用 stdlib bisect模块对键进行排序。

于 2013-03-19T05:23:35.880 回答
1

晚了一年多，但我想推荐sortedcontainers模块。像 blist 和 bintrees 一样，它提供了一个SortedDict数据类型，以排序顺序维护键。与那些模块不同，它是用纯 Python 编写的，实际上速度更快。SortedDict 还支持索引。查找最小值/最大值实际上发生在 O(1) 时间内。

因为它是纯 Python，所以使用 pip 安装应该是轻而易举的事：

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})

如果您在使用 pip 安装东西时遇到困难或无法复制需要编译的文件，那么您可以将 sortedlist.py 和 sorteddict.py 文件从软件仓库中拉出。所有代码在 github 上都是开源的。

sortedcontainers 模块还提供了与最流行的建议进行性能比较的基准测试。

于 2014-09-23T06:36:45.323 回答