Python中的键有序字典

Question

我正在寻找一个有力的有序关联数组实现，也就是有序字典。我想要根据键（key）排序，而不是插入顺序。

更精确地说，我正在寻找一种空间高效的整数到浮点数映射结构的实现（或者针对另一种用例的字符串到浮点数映射结构），满足以下要求：

• 有序迭代时间复杂度为O(n)
• 随机访问时间复杂度为O(1)

我想到的最好方法是将一个字典和一个键（key）列表粘合在一起，使用bisect和insert保持最后一个键列表有序。

还有更好的想法吗？

- LeMiz

---

你不能只按要求进行转换吗？你需要缓存结果以备后用吗？而性能要求是必需的，因为这已被发现是一个瓶颈？ - hughdbrown

你需要动态地改变内容吗？ - liori

抱歉，我没有提供上下文。我在内存中有大约10,000个这样的结构体。每个结构体包含10到5,000个键/值对。根据模式，我要么为每个映射查找一个精确的键，要么对其应用某些函数，该函数取决于顺序。我无法预先计算结果，因为它们取决于用户输入。分析显示，对字典进行排序确实是瓶颈。 - LeMiz

hughdbrown：他并没有缓存整型到浮点型的转换，而是在实现一个从整数到浮点数的映射。 - Ned Batchelder

@Ned：感谢您的澄清，我没有理解错。 - LeMiz

Answer 1

"Random access O(1)"这是一个非常严格的要求，基本上需要使用底层的哈希表--我希望你指的是随机读取，因为我认为在一般情况下无法同时实现O(1)写入和O(N)有序迭代，这个可以通过数学证明。

我认为你不会找到适合你需求的预打包容器，因为它们太极端了——当然，O(log N)访问会完全改变一切。要获得你想要的读取和迭代的大O效果，你需要将两个数据结构粘合起来，基本上是一个字典和一个堆（或排序列表或树），并保持它们同步。虽然你没有详细说明，但我认为你只能获得你想要的那种分摊行为-除非你真的愿意承担插入和删除的任何性能损失，这是你所表达的规范的字面含义，但似乎是一个相当不可能实际需求。

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

- Alex Martelli

---

我有几乎完全相同的东西，但是用的是__setitem__(self, k, v)： 如果k不在self.d中： idx = bisect.bisect(self.l, k) # log(n) self.l.insert(idx, k) # 保持列表排序 self.d[k] = v 这可以防止“脏”标志的出现。是否有一篇详细描述Python排序的论文（如果没有，我将阅读源代码）。 但我的问题实际上是关于防止键列表重复的技巧（例如，如果哈希值很短，只复制哈希值可能更可取，而不是长整数）。谢谢您对Python排序的见解。 - LeMiz

如果 (1) 消除 self.sorted (2) 如果未排序，则消除 self.L == None (3) self.L 从 iter() 中的键生成 (4) setitem 使 self.L 无效，将其设置为 None，这样怎么样？ - hughdbrown

Python源代码中有一个.txt文件，其中包含Tim Peters关于他的排序算法的非常好的文章；抱歉，我现在无法找到URL，因为我正在使用手机，没有WiFi。关键点在于将一个项目附加到已排序的列表中并再次排序是o(n)的，就像bisect然后插入一样，并且如果在排序之间附加了m远小于n个项目，则渐近地更好，这就是我希望解释的原因，为什么我提出的代码应该比评论中提到的其他替代方案更好。 - Alex Martelli

@LeMiz，不用担心大键的重复：self.L和self.d只是对同一键对象的引用集合，没有这些对象的副本。 - Alex Martelli

@LeMiz，不客气！一个引用本身在32位的Python构建中占用4个字节，在64位的构建中占用8个字节；除此之外，我认为提出一个新问题是明智的（例如：如何测量事物，当非常紧密时如何压缩等）。 - Alex Martelli

Answer 2

sortedcontainers模块提供了一个SortedDict类型，满足您的要求。它基本上将SortedList和字典类型粘合在一起。字典提供O(1)查找，而SortedList提供O(N)迭代（非常快）。整个模块是纯Python的，并且有基准测试图表来支持性能声明（快如C语言实现）。SortedDict也经过100%覆盖率的完全测试和数小时的压力测试。它兼容Python 2.6到3.4。

- GrantJ

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语言实现）？

- LeMiz

Answer 4

对于这种情况，有序树通常更好，但随机访问会是log(n)。您还应考虑插入和删除的成本...

- fortran

---

你有一个建议的实现方案吗（最好有良好的文档，特别是对于边缘情况）？ - LeMiz

这似乎是AVL排序树的一个有趣实现：http://pyavl.sourceforge.net/ - fortran

谢谢提供链接。我的第一反应是，如果我放弃了O(1)的随机访问时间的要求，那么使用它作为关联数组需要进行很多修改。 - LeMiz

Answer 5

你可以建立一个字典，通过在每个位置存储一对(value, next_key)来实现遍历。

随机访问：

my_dict[k][0]   # for a key k

遍历：

k = start_key   # stored somewhere
while k is not None:     # next_key is None at the end of the list
    v, k = my_dict[k]
    yield v

保持对start和end的指针，您将拥有高效的更新方式，适用于那些只需要在列表末尾添加的情况。

在中间插入显然是O(n)。如果需要更快的速度，可能可以在其上构建跳表。

- John Fouhy

---

显然，你也可以存储指向前一个元素的指针，这将使得在中间插入/删除更加容易，特别是如果你在其上实现跳表。 - John Fouhy

Answer 6

我在2007年实现的ordereddict包(http://anthon.home.xs4all.nl/Python/ordereddict/)包含了sorteddict。sorteddict是一个KSO（Key Sorted Order）字典，用C实现，非常节省空间，并且比纯Python实现快几倍。缺点是它只能与CPython一起使用。

>>> from _ordereddict import sorteddict
>>> x = sorteddict()
>>> x[1] = 1.0
>>> x[3] = 3.3
>>> x[2] = 2.2
>>> print x
sorteddict([(1, 1.0), (2, 2.2), (3, 3.3)])
>>> for i in x:
...    print i, x[i]
... 
1 1.0
2 2.2
3 3.3
>>> 

抱歉回复晚了，也许这个答案可以帮助其他人找到那个库。

- Anthon

Answer 7

我不确定你正在使用哪个Python版本，但是如果你想尝试一下，Python 3.1包含了一个官方实现的有序字典：

http://www.python.org/dev/peps/pep-0372/ http://docs.python.org/3.1/whatsnew/3.1.html#pep-372-ordered-dictionaries

- Santi

---

有序字典是根据键的插入顺序排序，而不是根据键的排序顺序排序，因此我认为LeMiz将无法使用此解决方案。 - SingleNegationElimination

Answer 8

这里有一个代码片段：我需要类似的东西。但请注意，此特定实现是不可变的，没有插入，一旦创建了实例：确切的性能并不完全符合您所要求的，查找是O(log n)，全扫描是O(n)。这是使用bisect模块在键/值（元组）对的元组上工作的。即使您无法精确使用它，您也可能会成功地将其适应您的需求。

import bisect

class dictuple(object):
    """
        >>> h0 = dictuple()
        >>> h1 = dictuple({"apples": 1, "bananas":2})
        >>> h2 = dictuple({"bananas": 3, "mangoes": 5})
        >>> h1+h2
        ('apples':1, 'bananas':3, 'mangoes':5)
        >>> h1 > h2
        False
        >>> h1 > 6
        False
        >>> 'apples' in h1
        True
        >>> 'apples' in h2
        False
        >>> d1 = {}
        >>> d1[h1] = "salad"
        >>> d1[h1]
        'salad'
        >>> d1[h2]
        Traceback (most recent call last):
        ...
        KeyError: ('bananas':3, 'mangoes':5)
   """


    def __new__(cls, *args, **kwargs):
        initial = {}
        args = [] if args is None else args
        for arg in args:
            initial.update(arg)
        initial.update(kwargs)

        instance = object.__new__(cls)
        instance.__items = tuple(sorted(initial.items(),key=lambda i:i[0]))
        return instance

    def __init__(self,*args, **kwargs):
        pass

    def __find(self,key):
        return bisect.bisect(self.__items, (key,))


    def __getitem__(self, key):
        ind = self.__find(key)
        if self.__items[ind][0] == key:
            return self.__items[ind][1]
        raise KeyError(key)
    def __repr__(self):
        return "({0})".format(", ".join(
                        "{0}:{1}".format(repr(item[0]),repr(item[1]))
                          for item in self.__items))
    def __contains__(self,key):
        ind = self.__find(key)
        return self.__items[ind][0] == key
    def __cmp__(self,other):

        return cmp(self.__class__.__name__, other.__class__.__name__
                  ) or cmp(self.__items, other.__items)
    def __eq__(self,other):
        return self.__items == other.__items
    def __format__(self,key):
        pass
    #def __ge__(self,key):
    #    pass
    #def __getattribute__(self,key):
    #    pass
    #def __gt__(self,key):
    #    pass
    __seed = hash("dictuple")
    def __hash__(self):
        return dictuple.__seed^hash(self.__items)
    def __iter__(self):
        return self.iterkeys()
    def __len__(self):
        return len(self.__items)
    #def __reduce__(self,key):
    #    pass
    #def __reduce_ex__(self,key):
    #    pass
    #def __sizeof__(self,key):
    #    pass

    @classmethod
    def fromkeys(cls,key,v=None):
        cls(dict.fromkeys(key,v))

    def get(self,key, default):
        ind = self.__find(key)
        return self.__items[ind][1] if self.__items[ind][0] == key else default

    def has_key(self,key):
        ind = self.__find(key)
        return self.__items[ind][0] == key

    def items(self):
        return list(self.iteritems())

    def iteritems(self):
        return iter(self.__items)

    def iterkeys(self):
        return (i[0] for i in self.__items)

    def itervalues(self):
        return (i[1] for i in self.__items)

    def keys(self):
        return list(self.iterkeys())

    def values(self):
        return list(self.itervalues())
    def __add__(self, other):
        _sum = dict(self.__items)
        _sum.update(other.__items)
        return self.__class__(_sum)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

- SingleNegationElimination

Answer 9

对于“字符串转浮点数”的问题，你可以使用 Trie 数据结构 - 它提供 O(1) 的访问时间和 O(n) 的排序迭代。这里的“排序”是指按照键值字母顺序进行排序 - 问题似乎暗示了这一点。

以下是一些实现方式（每种方式都有其优点和缺点）：

• https://github.com/biopython/biopython 包含了一个功能齐全的 Trie 模块 Bio.trie；其他的 Trie 包更加节省内存；
• https://github.com/kmike/datrie - 随机插入可能会很慢，键字母表必须事先知道；
• https://github.com/kmike/hat-trie - 所有操作都很快，但许多字典方法未实现；底层 C 库支持排序迭代，但在包装器中未实现；
• https://github.com/kmike/marisa-trie - 内存非常高效，但不支持插入；默认情况下迭代不是排序的，但可以使其排序（文档中有示例）；
• https://github.com/kmike/DAWG - 可以看作是最小化的 Trie；非常快速和内存高效，但不支持插入；有大小限制（几 GB 的数据）

- Mikhail Korobov

Answer 10

这里有一个其他答案中没有提到的选项：

• 使用二叉搜索树（Tree/AVL/RB）来保留映射关系。
• 同时使用哈希表（又称字典）来保留相同的映射关系。

这将提供O(n)有序遍历（通过树），O(1)随机访问（通过哈希表）和O(log n)插入/删除（因为你需要同时更新树和哈希表）。

不足之处在于需要将所有数据存储两次，然而，建议将键列表与哈希表一起保存的替代方法在这方面也不太好。

- KT.