Python中的键顺序字典

Question

我正在寻找一个有序的关联数组，即有序的字典的可靠实现。我想要按键而不是插入顺序排序。

更准确地说，我正在寻找一种int-to-float（或另一种用例是string-to-float）映射结构的节省空间的实现，该结构的结构是：

• 有序迭代为O（n）
• 随机访问为O（1）

我想到的最好的方法是将字典和键列表粘合在一起，使最后一个键按等分和插入顺序排列。

还有更好的主意吗？

Answer 1

“随机访问O（1）”是一个非常严格的要求，基本上要求一个基础哈希表-我希望您只表示随机READS，因为我认为它可以通过数学证明，而在一般情况下不可能拥有O
（1）编写以及O（N）有序的迭代。

我认为您不会找到适合您需求的预包装容器，因为它们是如此极端-O（log N）访问当然会改变世界。为了获得您要进行读取和迭代的big-
O行为，您需要粘合两个数据结构，本质上是一个dict和一个堆（或排序列表或树），并使它们保持同步。尽管您没有指定，但我认为您只会得到想要的 摊销 行为-
除非您真正愿意为插入和删除付出任何性能上的损失，这实际上是您表达的规范的涵义，但确实似乎不太可能是现实生活中的要求。

对于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，只是重复self.L.sort()的__setitem__本身。当然，这使写操作为O（N
log
N）（尽管我仍然在O（1）上进行写操作）。每种方法都是可行的，并且很难认为一种方法本质上优于另一种方法。如果您倾向于写一堆，然后进行一堆迭代，那么上面代码中的方法是最好的。如果通常是一次写入，一次迭代，另一次写入，另一次迭代，那么就差不多了。

顺便说一句，这利用了Python排序（又称“
timsort”）的异常（和出色；-）性能特征的无耻优势：在其中，排序一个列表，该列表大部分已排序，但最后附加了一些其他项目，基本上是O
（N）（如果与排序的前缀部分相比，粘贴的项目足够少）。我听说Java很快就会获得这种收益，因为Josh
Block对Python的技术演讲印象深刻，以至于他开始在随处的笔记本电脑上为JVM进行编码。大多数系统（包括我相信今天的Jython和IronPython在内）基本上都以O（N
log N）操作进行排序，而没有利用“大多数有序”输入；在这方面，蒂姆·彼得斯（Tim
Peters）塑造成如今的Python风格的“自然合并排序”是一个奇迹。