如何在Python 3中实现有序字典(OrderedDict)的插入操作

Question

我希望能在有序字典中的特定位置插入一个项目。 使用gist的this SO答案，我遇到了它在Python 3上无法运行的问题。

这是使用的实现。

from collections import OrderedDict

class ListDict(OrderedDict):

    def __init__(self, *args, **kwargs):
        super(ListDict, self).__init__(*args, **kwargs)

    def __insertion(self, link_prev, key_value):
        key, value = key_value
        if link_prev[2] != key:
            if key in self:
                del self[key]
            link_next = link_prev[1]
            self._OrderedDict__map[key] = link_prev[1] = link_next[0] = [link_prev, link_next, key]
        dict.__setitem__(self, key, value)

    def insert_after(self, existing_key, key_value):
        self.__insertion(self._OrderedDict__map[existing_key], key_value)

    def insert_before(self, existing_key, key_value):
        self.__insertion(self._OrderedDict__map[existing_key][0], key_value)

使用它的方式如下：

ld = ListDict([(1,1), (2,2), (3,3)])
ld.insert_before(2, (1.5, 1.5))

提供

File "...", line 35, in insert_before
    self.__insertion(self._OrderedDict__map[existing_key][0], key_value)
AttributeError: 'ListDict' object has no attribute '_OrderedDict__map'

它适用于Python 2.7。它在Python 3中失败的原因是什么？ 检查OrderedDict实现的源代码显示使用self.__map而不是self._OrderedDict__map。将代码更改为使用self.__map会得到

AttributeError: 'ListDict' object has no attribute '_ListDict__map'

我该怎么做？如何在Python 3中实现？OrderedDict使用内部的__map属性来存储双向链表。那么我该如何正确地访问这个属性？

- maggie

---

如果你想知道为什么 self.__map 不起作用，请参考这个问题。至于为什么这段代码在 Python2 中可以工作但在 Python3 中不行，我不知道。 - Aran-Fey

非常有帮助，谢谢。我不知道这个双下划线规则。但它并没有回答问题。 - maggie

我相信OrderedDict在Python 3.5中进行了重构，以便使用C而不是Python（https://bugs.python.org/issue16991），因此以前的私有结构`self.__map`可能在Python中不再可访问。这就是为什么当开发人员使用他们所拥有的一点点东西来表达某些东西在Python中不应该被搞乱时，你应该听取并且不要在你的子类中尝试依赖它的原因。 - Two-Bit Alchemist

当你搞乱了实现细节时，就会发生这种情况。实现细节改变了，你就会受到影响。 - user2357112

Answer 1

我不确定你是否最好在代码中保持单独的列表和字典，但这里提供了一个纯Python实现该对象的尝试。这将比Python 3.5中实际的OrderedDict慢一个数量级，正如我在我的评论中指出的那样已被重写为C语言。

"""
A list/dict hybrid; like OrderedDict with insert_before and insert_after
"""
import collections.abc


class MutableOrderingDict(collections.abc.MutableMapping):
    def __init__(self, iterable_or_mapping=None, **kw):
        # This mimics dict's initialization and accepts the same arguments
        # Of course, you have to pass an ordered iterable or mapping unless you
        # want the order to be arbitrary. Garbage in, garbage out and all :)
        self.__data = {}
        self.__keys = []
        if iterable_or_mapping is not None:
            try:
                iterable = iterable_or_mapping.items()
            except AttributeError:
                iterable = iterable_or_mapping
            for key, value in iterable:
                self.__keys.append(key)
                self.__data[key] = value
        for key, value in kw.items():
            self.__keys.append(key)
            self.__data[key] = value

    def insert_before(self, key, new_key, value):
        try:
            self.__keys.insert(self.__keys.index(key), new_key)
        except ValueError:
            raise KeyError(key) from ValueError
        else:
            self.__data[new_key] = value

    def insert_after(self, key, new_key, value):
        try:
            self.__keys.insert(self.__keys.index(key) + 1, new_key)
        except ValueError:
            raise KeyError(key) from ValueError
        else:
            self.__data[new_key] = value

    def __getitem__(self, key):
        return self.__data[key]

    def __setitem__(self, key, value):
        self.__keys.append(key)
        self.__data[key] = value

    def __delitem__(self, key):
        del self.__data[key]
        self.__keys.remove(key)

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

    def __len__(self):
        return len(self.__keys)

    def __contains__(self, key):
        return key in self.__keys

    def __eq__(self, other):
        try:
            return (self.__data == dict(other.items()) and
                    self.__keys == list(other.keys()))
        except AttributeError:
            return False

    def keys(self):
        for key in self.__keys:
            yield key

    def items(self):
        for key in self.__keys:
            yield key, self.__data[key]

    def values(self):
        for key in self.__keys:
            yield self.__data[key]

    def get(self, key, default=None):
        try:
            return self.__data[key]
        except KeyError:
            return default

    def pop(self, key, default=None):
        value = self.get(key, default)
        self.__delitem__(key)
        return value

    def popitem(self):
        try:
            return self.__data.pop(self.__keys.pop())
        except IndexError:
            raise KeyError('%s is empty' % self.__class__.__name__)


    def clear(self):
        self.__keys = []
        self.__data = {}

    def update(self, mapping):
        for key, value in mapping.items():
            self.__keys.append(key)
            self.__data[key] = value

    def setdefault(self, key, default):
        try:
            return self[key]
        except KeyError:
            self[key] = default
            return self[key]

    def __repr__(self):
        return 'MutableOrderingDict(%s)' % ', '.join(('%r: %r' % (k, v)
                                                      for k, v in self.items()))

我最终实现了整个collections.abc.MutableMapping合约，因为这些方法都不是很长，但你可能不会使用所有的方法。特别是__eq__和popitem有点任意。我将insert_*方法的签名更改为4个参数，这样感觉更自然。最后注意：仅在Python 3.5上进行了测试。在Python 2上肯定无法工作，需要进行一些（小）修改。

- Two-Bit Alchemist

---

感谢您提供这个完整的代码片段！我尝试在我的问题中使用Python的有序字典__init__文件的实现，并在那里重新实现了insert_*方法。有趣的是，性能基准测试显示它比您或“从修改后的列表创建新的有序字典”实现慢3倍（对于小字典）。我只是希望看到更容易地子类化OrderedDict... - maggie

Answer 2

我在尝试使用Python 3.7中新的dict对象，并尝试实现Two-Bit Alchemist回答中所做的事情，但是只是覆盖原生dict类，因为在Python 3.7中dict是有序的。

''' Script that extends python3.7 dictionary to include insert_before and insert_after methods. '''
from sys import exit as sExit

class MutableDict(dict):
    ''' Class that extends python3.7 dictionary to include insert_before and insert_after methods. '''

    def insert_before(self, key, newKey, val):
        ''' Insert newKey:value into dict before key'''
        try:
            __keys = list(self.keys())
            __vals = list(self.values())

            insertAt = __keys.index(key)

            __keys.insert(insertAt, newKey)
            __vals.insert(insertAt, val)

            self.clear()
            self.update({x: __vals[i] for i, x in enumerate(__keys)})

        except ValueError as e:
            sExit(e)

    def insert_after(self, key, newKey, val):
        ''' Insert newKey:value into dict after key'''
        try:
            __keys = list(self.keys())
            __vals = list(self.values())

            insertAt = __keys.index(key) + 1

            if __keys[-1] != key:
                __keys.insert(insertAt, newKey)
                __vals.insert(insertAt, val)
                self.clear()
                self.update({x: __vals[i] for i, x in enumerate(__keys)})
            else:
                self.update({newKey: val})

        except ValueError as e:
            sExit(e)

一些测试：

 In: v = MutableDict([('a', 1), ('b', 2), ('c', 3)])
Out: {'a': 1, 'b': 2, 'c': 3}

 In: v.insert_before('a', 'g', 5)
Out: {'g': 5, 'a': 1, 'b': 2, 'c': 3}

 In: v.insert_after('b', 't', 5)
Out: {'g': 5, 'a': 1, 'b': 2, 't': 5, 'c': 3}

编辑：我决定进行一次小型基准测试，以了解这会带来什么样的性能损失。我将使用from timeit import timeit。

获取一个基准。创建一个包含任意值的字典。

 In: timeit('{x: ord(x) for x in string.ascii_lowercase[:27]}', setup='import string', number=1000000)
Out: 1.8214202160015702

看看使用相同的任意值初始化MutableDict需要多长时间。

 In: timeit('MD({x: ord(x) for x in string.ascii_lowercase[:27]})', setup='import string; from MutableDict import MutableDict as MD', number=1000000)
Out: 2.382507269998314

1.82 / 2.38 = 0.76。因此如果我理解正确，MutableDict 的创建速度要慢24%。

接下来看看插入操作需要多长时间。在这个测试中，我将使用 insert_after 方法，因为它稍微更大一些。还会寻找一个靠近末尾的键进行插入。在这种情况下是“t”。

 In: timeit('v.insert_after("t", "zzrr", ord("z"))', setup='import string; from MutableDict import MutableDict as MD; v = MD({x: ord(x) for x in string.ascii_lowercase[:27]})' ,number=1000000)
Out: 3.9161406760104

2.38 / 3.91 = 0.60，插入节点比初始化慢40%。在1百万次循环的小型测试中表现不错。为了比较时间关系，我们将进行以下测试：

 In: timeit('"-".join(map(str, range(100)))', number=1000000)
Out: 10.342204540997045

这并非完全可比的比较，但我希望这些测试可以帮助您（不一定是原帖作者）决定是否在您的3.7项目中使用此类。

- tldr

Answer 3

自Python 3.2起，move_to_end 可用于在 OrderedDict 中移动项目。以下代码将通过将提供的索引后面的所有项目移动到末尾来实现 insert 功能。

请注意，这不是非常高效的，应谨慎使用（如果使用）。

def ordered_dict_insert(ordered_dict, index, key, value):
    if key in ordered_dict:
        raise KeyError("Key already exists")
    if index < 0 or index > len(ordered_dict):
        raise IndexError("Index out of range")

    keys = list(ordered_dict.keys())[index:]
    ordered_dict[key] = value
    for k in keys:
        ordered_dict.move_to_end(k)

有明显的优化和改进可以进行，但这是一般的想法。

- pR0Ps

Answer 4

from collections import OrderedDict

od1 = OrderedDict([
    ('a', 1),
    ('b', 2),
    ('d', 4),
])

items = od1.items()
items.insert(2, ('c', 3))
od2 = OrderedDict(items)

print(od2)  # OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])

- Zac Crites

---

这并没有在 OrderedDict 上实现插入。而是创建了一个全新的 OrderedDict。 - Two-Bit Alchemist