如何在 python 3 中为 OrderedDict 实现插入
How to implement insert for OrderedDict in python 3
我想在 OrderedDict 的某个位置插入一个项目。
使用 gist of 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 属性来存储双向链表。那么我怎样才能正确访问这个属性呢？
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)])
我不确定在您的代码中使用单独的列表和命令是否会更好，但这里是对此类对象的纯 Python 实现的尝试。这将比 Python 3.5 中的实际 OrderedDict 慢一个数量级，正如我在评论 has been rewritten in 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 契约，因为 none 方法很长，但您可能不会使用所有方法。特别是 __eq__ 和 popitem 有点随意。我将您在 insert_* 方法上的签名更改为一个 4 参数的签名，这对我来说更自然一些。最后说明：仅在 Python 3.5 上测试。如果不进行一些（较小的）更改，肯定不会在 Python 2 上工作。
自 Python 3.2，move_to_end can be used to move items around in an 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)
可以进行明显的优化和改进，但这是总体思路。
在 3.7 中试用新的字典对象，我想我会尝试实现两位炼金术士对他的答案所做的，但只是覆盖了原生字典 class 因为在 3.7 中字典是有序的。
''' 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% inserting_after。在 100 万个循环的小测试中还不错。为了比较时间关系，我们将对此进行测试：
In: timeit('"-".join(map(str, range(100)))', number=1000000)
Out: 10.342204540997045
不是同类比较，但我希望这些测试能帮助您（reader 不一定是 OP）决定在您的 3.7 项目中使用或不使用此 class。
我想在 OrderedDict 的某个位置插入一个项目。 使用 gist of 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 属性来存储双向链表。那么我怎样才能正确访问这个属性呢？
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)])
我不确定在您的代码中使用单独的列表和命令是否会更好，但这里是对此类对象的纯 Python 实现的尝试。这将比 Python 3.5 中的实际 OrderedDict 慢一个数量级，正如我在评论 has been rewritten in 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 契约，因为 none 方法很长，但您可能不会使用所有方法。特别是 __eq__ 和 popitem 有点随意。我将您在 insert_* 方法上的签名更改为一个 4 参数的签名，这对我来说更自然一些。最后说明：仅在 Python 3.5 上测试。如果不进行一些（较小的）更改，肯定不会在 Python 2 上工作。
自 Python 3.2，move_to_end can be used to move items around in an 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)
可以进行明显的优化和改进，但这是总体思路。
在 3.7 中试用新的字典对象，我想我会尝试实现两位炼金术士对他的答案所做的，但只是覆盖了原生字典 class 因为在 3.7 中字典是有序的。
''' 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% inserting_after。在 100 万个循环的小测试中还不错。为了比较时间关系，我们将对此进行测试：
In: timeit('"-".join(map(str, range(100)))', number=1000000)
Out: 10.342204540997045
不是同类比较，但我希望这些测试能帮助您（reader 不一定是 OP）决定在您的 3.7 项目中使用或不使用此 class。