logo标签列表

如何向OrderedDict添加一个元素

pythondictionarycollections
4

我有一个OrderedDict，需要在保持排序的同时添加一个元素

import sys
import bisect
from collections import OrderedDict

arr = {('a',1111),('b',2222),('f',3333)}
arr = OrderedDict(arr)

bisect.insort(arr,('c',4444))
#expectedly      arr = {('a',1111),('b',2222),('c',4444),('f',3333)}

#but actually     TypeError: collections.OrderedDict is not a sequence

更新：我需要按键排序存储项目，但是保持
import sys
import bisect
from collections import OrderedDict
from sortedcontainers import sorteddict
arr = {('a',1111),('b',2222),('f',3333)}
arr = OrderedDict(arr)
arr.update({'c':4444})   #or arr['c'] = 4444
print(arr)

有序字典(OrderedDict)：[('b', 2222), ('f', 3333), ('a', 1111), ('c', 4444)]

转换为OrderedDict后为：[('a', 1111), ('b', 2222), ('c', 4444), ('f', 3333)]

类似于C++中的Map。

1
arr['c'] = 4444 - 同时，arr是一组元组。 - modesitt
1
如果你使用的是 Python3.7 及以上版本，dict 默认是有序的（在规范中）。你可以简单地执行 arr = dict((('a',1111),('b',2222),('f',3333)))，从而插入一个有序字典。 - modesitt
1
由于您最初使用了“元组”的“集合”，因此没有任何保证的顺序。请参见这里。这意味着当您创建排序字典时，初始插入将不会被排序。您应该改用“列表”或“元组”。 - Alex
为什么需要按键排序字典？您打算如何使用它？ - Alex
@Alex 需要存储文本及其翻译，并按照文本进行排序。 - Artem072
你应该编辑你的帖子，使其成为一个 [mcve]。请给出在排序后使用字典的示例。 - Alex
2个回答
3

将新项添加到原始项中，进行排序，创建一个新字典：

>>> arr = {('a',1111),('b',2222),('f',3333)}
>>> arr = collections.OrderedDict(arr)
>>> new = ('c',4444)
>>> items = list(arr.items())
>>> items.append(new)
>>> items.sort()
>>> arr = collections.OrderedDict(items)
>>> arr
OrderedDict([('a', 1111), ('b', 2222), ('c', 4444), ('f', 3333)])

按顺序维护键的排序字典

或者稍微复杂一些的选项：

  • 子类化 collections.OrderedDict
  • 使用 move_to_end 方法作为指南，创建一个新方法将遍历双向链表；找到要插入的位置；然后插入新的键 - 可能可以在这里使用二分法或其他双向链表排序插入算法
  • 覆盖 __setitem__ 方法，并在其中调用新方法 - 或者使用前面一个项目中想出的算法来替换添加新键到末尾的代码。

保持键排序的排序字典

我无法弄清楚如何使有序字典子类起作用 - 它有许多被名称修饰的属性 - 只需要重写其中一两个方法，而我不想花时间弄清楚名称修饰方面的内容。

所以只需将整个有序字典类从源从这里 - 到这里复制到一个单独的模块中，以便您可以导入它，并包括这些导入。

from _weakref import proxy as _proxy
from collections import _Link, _OrderedDictKeysView
from collections import _OrderedDictItemsView, _OrderedDictValuesView
import _collections_abc
from _weakref import proxy as _proxy
from reprlib import recursive_repr as _recursive_repr
from operator import itemgetter as _itemgetter, eq as _eq
import bisect

然后在类中进行以下更改：

  • 将课程的类名更改为您喜欢的名称。类名后面是一个文档字符串和一些注释，描述了类的行为 - 这些应该更新。
    class SortOrderedDict(dict):
  • 重写__setitem__方法。以下使用bisect查找插入顺序。不知道是否真的有必要，它必须先制作一个字典键视图列表，但那部分应该是快速的C代码（？我在猜测）
    def __setitem__(self, key, value,
                    dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
        'od.__setitem__(i, y) <==> od[i]=y'
        # Setting a new item creates a new link in the linked list,
        # inserted at its key sorted position - uses less than comparisons,
        # and the inherited dictionary is updated with the new key/value pair.
        if key not in self:
            self.__map[key] = link = Link()
            root = self.__root
            last = root.prev
            link.key = key
            curr = root.next
            if curr is root:    # first item!
                link.prev, link.next = last, root
                last.next = link
                root.prev = proxy(link)
            elif link.key < root.next.key:    # at the beginning?
                #print(f'{link.key} before {root.next.key}')
                soft_link = root.next
                link.prev, link.next = root, soft_link
                soft_link.prev = link
                root.next = link
            elif root.prev.key < link.key:    # at the end?
                #print(f'{link.key} at the end after {root.prev.key}')
                soft_link = root.prev
                link.prev, link.next = soft_link, root
                soft_link.next = link
                root.prev = proxy(link)
            else:    # in the middle somewhere - use bisect
                keys = list(self.keys())
                i = bisect.bisect_left(keys,key)
                right = self.__map[keys[i]]
                #print(f'{link.key} between {right.prev.key} and {right.key}')
                soft_link = right.prev
                link.prev,link.next = soft_link,right
                right.prev = link
                soft_link.next = link

        dict_setitem(self, key, value)
  • 添加一个update方法 - 这个类是dict的子类，这将覆盖它的更新方法并强制使用__setitem__。
    def update(self,other):
        try:
            other = other.items()
        except AttributeError:
            pass
        for k,v in other:
            self[k] = v

将这一行 update = __update = _collections_abc.MutableMapping.update 改为：
    __update = update

在__reduce__方法中，将for k in vars(OrderedDict()):中的类名更改为您命名的类名。
    for k in vars(SortOrderedDict()):
  • 在__eq__方法中同样如此。将if isinstance(other, OrderedDict):更改为
    if isinstance(other, SortOrderedDict):

如果使用二分法不值得，那就遍历链表直到找到插入点。（上面列出的所有其他更改仍然适用）
    def __setitem__(self, key, value,
                    dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
        'od.__setitem__(i, y) <==> od[i]=y'
        # Setting a new item creates a new link in the linked list,
        # inserted at its key sorted position - uses less than comparisons,
        # and the inherited dictionary is updated with the new key/value pair.
        if key not in self:
            self.__map[key] = link = Link()
            root = self.__root
            last = root.prev
            link.key = key
            curr = root.next
            if curr is root:    # first item!
                link.prev, link.next = last, root
                last.next = link
                root.prev = proxy(link)
            # traverse the linked list; find sorted insertion point; insert
            while curr is not root:
                if link.key < curr.key:
                    soft_link = curr.prev
                    soft_link.next = link
                    link.prev = soft_link
                    link.next = curr
                    curr.prev = link
                    break
                elif curr.next is root:
                    link.prev, link.next = curr, root
                    curr.next = link
                    root.prev = proxy(link)
                    break
                curr = curr.next
        dict_setitem(self, key, value)

使用方法

>>> arr = {('a',1111),('f',3333),('b',2222)}
>>> arr = SortOrderedDict(arr)
>>> arr
SortOrderedDict([('a', 1111), ('b', 2222), ('f', 3333)])
>>> other = {k:v for k,v in zip('tvsnpqkl',range(8))}
>>> arr.update(other)
>>> arr
SortOrderedDict([('a', 1111), ('b', 2222), ('f', 3333), ('k', 6), ('l', 7), ('n', 3), ('p', 4), ('q', 5), ('s', 2), ('t', 0), ('v', 1)])
>>> b = SortOrderedDict((('a',1111),('f',3333),('b',2222)))
>>> b.update(other)
>>> arr == b
True
>>> b == arr
True
>>>
我需要不断添加元素，每次排序都很耗费资源。 - Artem072
1
@Artem072 - 那么也许你应该在检索时专注于对它们进行排序？OrderedDict仅维护插入顺序，因此要按排序顺序添加项目，您必须在排序之后每次制作一个新字典。也许子类或mixin会起作用。 - wwii
1
@Artem072 - 请查看编辑后的代码，其中包括一个保持有序的类。 - wwii
1

如果我理解正确，您希望按键对字典进行排序：

from collections import OrderedDict

arr = {('a',1111),('b',2222),('f',3333)}
arr = OrderedDict(arr)
arr['c'] = 4444
arr = OrderedDict(x for x in sorted(arr.items()))
一个按键排序迭代的Python字典：

class SortedDict(dict):
    def __iter__(self):
        yield from sorted(super().__iter__())

    def items(self):
        yield from sorted(super().items())

x = SortedDict({'d': 0, 'c': 9, 'b': 1, 'a': 3})
for k in x:
    print(k)
# a
# b
# c
# d
我需要不断添加元素，每次排序都很耗费资源。 - Artem072
那么，也许可以保留一份已排序的密钥副本，并使用它来访问字典？OrderedDict仅跟踪插入顺序。 - Alex
@Artem072 我写了一个小例子，展示了一个扩展的字典，它可以以任何顺序存储，但在循环遍历时会进行排序。 - Alex
1
@Artem072 还有sortedcontainers。它们可能更快，因为它们是用C编写的。 - Alex
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接