Python中按键排序的dict

Question

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

更确切地说,我正在寻找一个空间效率的实现int-to-float(或另一个用例的字符串到float)映射结构,其中:

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

我想出的最好的方法是粘贴一个字典和一个键列表,保留最后一个用bisect和insert命令.

有更好的想法吗？

Answer 1

"随机访问O(1)"是一个非常严格的要求,它基本上强加了一个底层哈希表 - 我希望你的意思只是随机READS,因为我认为它可以在数学上证明,而不是在一般情况下不可能有O (1)写入以及O(N)有序迭代.

我不认为你会找到一个适合你需要的预包装容器,因为它们非常极端--O(log N)访问当然会让世界变得与众不同.要获得读取和迭代所需的大O行为,您需要粘合两个数据结构,实质上是dict和堆(或排序列表或树),并使它们保持同步.虽然您没有指定,但我认为您只会得到您想要的那种摊销行为 - 除非您真的愿意为插入和删除支付任何性能命中,这是您表达的规范的字面含义但是似乎是一个非常不可能的现实生活要求.

对于O(1)读取和摊销的 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,只是重复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时代的"自然融合",在这方面是一个奇迹.

Answer 2

该sortedcontainers模块提供了SortedDict能满足你需求的类型.它基本上将SortedList和dict类型粘合在一起.dict提供O(1)查找,SortedList提供O(N)迭代(它非常快).整个模块是纯Python,并具有基准图来备份性能声明(快速实现C).SortedDict也经过全面测试,覆盖范围100%,压力小时.它与Python 2.6到3.4兼容.

Answer 3

这是我自己的实现:

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中)具有更聪明结构的东西？