Python 中的键排序字典

36 投票

10 回答

14654 浏览

数据工程师

提问于 2025-04-15 13:49

我在寻找一个可靠的有序关联数组实现，也就是一个有序字典。我希望这个字典是根据键的顺序来排序，而不是根据插入的顺序。

更具体来说，我想要一个节省空间的实现，用于将整数映射到浮点数（或者在另一个用例中，将字符串映射到浮点数）的结构，要求如下：

有序遍历的时间复杂度是 O(n)
随机访问的时间复杂度是 O(1)

我想到的最好办法是把一个字典和一个键的列表结合起来，并用二分查找和插入保持键的顺序。

有没有更好的想法呢？

数据结构随机访问时间复杂度空间复杂度二分查找键排序有序字典

10 个回答

这是我自己的实现方式：

import bisect
class KeyOrderedDict(object):
   __slots__ = ['d', 'l']
   def __init__(self, *args, **kwargs):
      self.l = sorted(kwargs)
      self.d = kwargs

   def __setitem__(self, k, v):
      if not k in self.d:
         idx = bisect.bisect(self.l, k)
         self.l.insert(idx, k)
       self.d[k] = v

   def __getitem__(self, k):
      return self.d[k]

   def __delitem__(self, k):
      idx = bisect.bisect_left(self.l, k)
      del self.l[idx]
      del self.d[k]

   def __iter__(self):
      return iter(self.l)

   def __contains__(self, k):
      return k in self.d

使用bisect可以保持self.l的顺序，而插入操作的时间复杂度是O(n)（因为要插入，但在我的情况下影响不大，因为我添加的次数远远多于真正的插入，所以通常情况下是摊销为O(1)）。访问的时间复杂度是O(1)，而遍历的时间复杂度是O(n)。不过，也许有人在C语言中发明了更聪明的结构？

回答于 2025-04-15 由 Python大师

分享举报

sortedcontainers模块提供了一种叫做SortedDict的类型，正好符合你的需求。它基本上是把SortedList和字典（dict）结合在一起。字典的查找速度是O(1)，也就是说查找非常快，而SortedList的遍历速度是O(N)，这也是非常快的。整个模块是用纯Python写的，并且有性能基准图来支持它的性能声明（速度和C语言实现一样快）。SortedDict经过了全面的测试，覆盖率达到100%，并且经过了长时间的压力测试。它兼容Python 2.6到3.4版本。

回答于 2025-04-15 由 Python大师

分享举报

"随机访问 O(1)" 是一个非常严格的要求，这基本上意味着你需要使用哈希表。我希望你指的是随机读取，因为我认为可以数学证明，在一般情况下，写入操作也达到 O(1) 是不可能的，同时还要支持 O(N) 的有序遍历。

我觉得你找不到一个现成的容器来满足你的需求，因为这些要求实在太极端了——如果能做到 O(log N) 的访问，那就会有很大的不同。为了实现你想要的读取和遍历的性能，你需要把两种数据结构结合起来，基本上就是一个字典和一个堆（或者有序列表或树），并保持它们的同步。虽然你没有具体说明，但我认为你得到的只会是你想要的那种摊销性能——除非你真的愿意为插入和删除付出性能上的代价，这正是你所表达的要求，但在现实生活中似乎不太可能。

如果你想要 O(1) 的读取和摊销 O(N) 的有序遍历，可以在字典旁边保持一个所有键的列表。例如：

class Crazy(object):
  def __init__(self):
    self.d = {}
    self.L = []
    self.sorted = True
  def __getitem__(self, k):
    return self.d[k]
  def __setitem__(self, k, v):
    if k not in self.d:
      self.L.append(k)
      self.sorted = False
    self.d[k] = v
  def __delitem__(self, k):
    del self.d[k]
    self.L.remove(k)
  def __iter__(self):
    if not self.sorted:
      self.L.sort()
      self.sorted = True
    return iter(self.L)

如果你不喜欢“摊销 O(N) 的顺序”，你可以去掉 self.sorted，然后在 __setitem__ 中重复 self.L.sort()。这样写入的复杂度就变成 O(N log N) 了（而我之前的写入是 O(1)）。这两种方法都是可行的，很难说哪一种本质上更优。如果你倾向于先进行一堆写入，然后再进行一堆遍历，那么上面的代码方法是最好的；如果通常是一次写入，一次遍历，再一次写入，再一次遍历，那么两者的性能差不多。

顺便说一下，这种方法充分利用了 Python 排序的独特（而且很棒的）性能特性（也叫“timsort”）：其中之一是，对一个大部分已经排序的列表进行排序，但在末尾加上几个额外的项目，基本上是 O(N) 的（前提是这些额外的项目相对于已排序部分来说数量足够少）。我听说 Java 也快要引入这种排序算法，因为 Josh Block 对 Python 排序的技术讲座印象深刻，于是当场就在他的笔记本上开始为 JVM 编写这个算法。目前大多数系统（包括我认为的 Jython 和 IronPython）基本上都是将排序视为 O(N log N) 的操作，而没有利用“基本有序”的输入；Tim Peters 将“自然归并排序”发展成了今天 Python 的 timsort，这在这方面真是个奇迹。

回答于 2025-04-15 由 Python大师

分享举报

Python 中的键排序字典

10 个回答

撰写回答