python - Python中的键序字典

Question

我正在寻找有序关联数组(即有序字典)的可靠实现。我希望按键排序，而不是按插入顺序。

更准确地说，我正在寻找一种节省空间的 int-to-float(或另一个用例的 string-to-float)映射结构的实现:

• 有序迭代是 O(n)
• 随机访问是 O(1)

我想出的最好的方法是粘合一个字典和一个键列表，用 bisect 和 insert 保持最后一个排序。

有更好的想法吗？

Answer 1

“随机访问 O(1)”是一个非常严格的要求，它基本上强加了一个底层哈希表——我希望你的意思只是随机读取，因为我认为它可以在数学上得到证明，而不是在一般情况下是不可能的进行 O(1) 次写入以及 O(N) 次有序迭代。

我认为您不会找到适合您需求的预打包容器，因为它们是如此极端—— O(log N) 访问当然会在世界上产生巨大的影响。要获得读取和迭代所需的 big-O 行为，您需要粘合两个数据结构，本质上是一个 dict 和一个堆(或排序列表或树)，并使它们保持同步。尽管您没有指定，但我认为您只会获得您想要的那种 amortized 行为 - 除非您真的愿意为插入和删除支付任何性能损失，这就是字面意思您表达的规范，但似乎不太可能是现实生活中的要求。

对于 O(1) 读取和 amortized O(N) 有序迭代，只需将所有键的列表保留在 dict 的一侧。例如:

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，在这方面是一个奇迹。