澳门1495

python 不可变的字典类。Python标准库之collections

九月 27th, 2018  |  澳门1495

问题

尝试楼python挑战赛1
兑现一个不可变的dict,数据只能由类初始化的下经过参数传递,修改、添加都见面丢来TypeError

引言

Python为咱提供了4种基本的数据结构:list, tuple, dict,
set,但是于处理数据量较充分的情况的时,这4种多少结构就明摆着过于单一了,比如list作为数组在少数情形插入的效率会比较低,有时候我们呢亟需保障一个平稳的dict。所以是时段我们将以Python标准库为我们提供的collections包了,它提供了差不多个有效的集合类,熟练掌握这些集合类,不仅可以给咱们于写来底代码更加Pythonic,也可以增进我们先后的周转效率。

缓解方法

继往开来ABCs中之MultiMapping, 复写其中的一部分方法即可。

defaultdict

defaultdict(default_factory)以平凡的dict之上添加了default_factory,使得key不存在时会自动生成相应项目的value,default_factory参数可以指定成list,
set, int等各种合法类型。

咱现在发出脚这样同样组list,虽然咱出5组数据,但是仔细察看后发现实际我们惟有发生3栽color,但是每一样种植color对许多单价。现在咱们纪念要拿此list转换成为一个dict,这个dict的key对许平等种植color,dict的value设置为一个list存放color对应之大半只价。我们得以行使defaultdict(list)来解决这个题目。

>>> from collections import defaultdict
>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
...     d[k].append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

如上等价于:

>>> d = {}
>>> for k, v in s:
...     d.setdefault(k, []).append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

如果我们不愿意含有更的要素,可以考虑使用defaultdict(set)。set相比list的不同之处在于set中莫允有一样的因素。

>>> from collections import defaultdict
>>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
>>> d = defaultdict(set)
>>> for k, v in s:
...     d[k].add(v)
...
>>> sorted(d.items())
[('blue', {2, 4}), ('red', {1, 3})]

代码

import collections


class ImmutableDict(collections.MutableMapping):
 def __init__(self, **kwargs):
     self.store = dict(**kwargs)
     self.error = TypeError("'ImmutableDict' objects are immutable")
     # self.update(dict(*args, **kwargs))

 def __setitem__(self, key, value):
     # 涉及到修改时会触发这个方法
     raise self.error

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

 def __delitem__(self, key):
     # 删除时触发
     raise self.error

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

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


class Get(object):
 def __init__(self):
     pass

 def __getitem__(self, item):
     return hash(item)


if __name__ == "__main__":
 test = ImmutableDict(name="sun", age=22, location="China")
 # test["name"] = "zhang"
 # test.pop("name")   TypeError will raised..
 # print(test.pop("name"))
 # for item in test:
     # print(item)
     #print(test[item])

MultiMapping 源码:

class MutableMapping(Mapping):

    @abstractmethod
    def __setitem__(self, key, value):
        raise KeyError

    @abstractmethod
    def __delitem__(self, key):
        raise KeyError

    __marker = object()

    def pop(self, key, default=__marker):
        try:
            value = self[key]
        except KeyError:
            if default is self.__marker:
                raise
            return default
        else:
            del self[key]
            return value

    def popitem(self):
        try:
            key = next(iter(self))
        except StopIteration:
            raise KeyError
        value = self[key]
        del self[key]
        return key, value

    def clear(self):
        try:
            while True:
                self.popitem()
        except KeyError:
            pass

    def update(self, other=(), **kwds):
        if isinstance(other, Mapping):
            for key in other:
                self[key] = other[key]
        elif hasattr(other, "keys"):
            for key in other.keys():
                self[key] = other[key]
        else:
            for key, value in other:
                self[key] = value
        for key, value in kwds.items():
            self[key] = value

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

MutableMapping.register(dict)

Mapping 源码:

class Mapping(Sized, Iterable, Container):

    @abstractmethod
    def __getitem__(self, key):
        raise KeyError

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

    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        else:
            return True

    def iterkeys(self):
        return iter(self)

    def itervalues(self):
        for key in self:
            yield self[key]

    def iteritems(self):
        for key in self:
            yield (key, self[key])

    def keys(self):
        return list(self)

    def items(self):
        return [(key, self[key]) for key in self]

    def values(self):
        return [self[key] for key in self]

    # Mappings are not hashable by default, but subclasses can change this
    __hash__ = None

    def __eq__(self, other):
        if not isinstance(other, Mapping):
            return NotImplemented
        return dict(self.items()) == dict(other.items())

    def __ne__(self, other):
        return not (self == other)

分析两只问题:

  • .get 的时候到底发生了哟?
  • .pop 的时节有了什么?

尝试进行断点调试:

尝试

get 跳反到了Mapping中的get

image.png

image.png

顾其中的self就是咱们实例化的immutableDict类

结论:
.get显示定义是当Mapping中,但是Mapping又拿此点子的实现丢掉给了子类,事实上,就是调用了
immutableDict.getitem遭遇的办法。
故我们以get 会触发我们在 immutableDict.getitem中定义的雅
pop 也就大类似了。

OrderedDict

Python3.6事先的dict是无序的,但是在少数情形我们要保障dict的有序性,这个时可以下OrderedDict,它是dict的一个subclass,但是在dict的基本功及维持了dict的有序型,下面我们来拘禁一下用到方式。

>>> # regular unsorted dictionary
>>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}

>>> # dictionary sorted by key
>>> OrderedDict(sorted(d.items(), key=lambda t: t[0]))
OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])

>>> # dictionary sorted by value
>>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

>>> # dictionary sorted by length of the key string
>>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

使用popitem(last=True)道好让咱们以LIFO(先进后出)的一一删除dict中的key-value,即除去最后一个安插的键值对,如果last=False就按照FIFO(先进先出)删除dict中key-value。

>>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}

>>> # dictionary sorted by key
>>> d = OrderedDict(sorted(d.items(), key=lambda t: t[0]))

>>> d
OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])

>>> d.popitem()
('pear', 1)

>>> d.popitem(last=False)
('apple', 4)

使用move_to_end(key, last=True)来改有序的OrderedDict对象的key-value顺序,通过者方式我们可以排序好的OrderedDict对象吃之自由一个key-value插入到字典的启幕或者结尾。

>>> d = OrderedDict.fromkeys('abcde')
>>> d
OrderedDict([('a', None), ('b', None), ('c', None), ('d', None), ('e', None)])

>>> d.move_to_end('b')
>>> d
OrderedDict([('a', None), ('c', None), ('d', None), ('e', None), ('b', None)])

>>> ''.join(d.keys())
'acdeb'
>>> d.move_to_end('b', last=False)
>>> ''.join(d.keys())
'bacde'

deque

list存储数据的优势在按索引查找元素会很快,但是插入和去元素就是死缓慢了,因为list是依据数组实现之。deque是为快速落实插入和去操作的双向列表,适合用于队列和货栈,而且线程安全。

list只提供了append和pop方法来起list的尾部插入/删除元素,deque新增了appendleft/popleft等办法允许我们迅速的当要素的开始来插入/删除元素。而且以deque在列两端append或pop元素的算法复杂度大约是O(1),但是对于list对象改变列表长度及数量位置的操作例如
pop(0)和insert(0, v)操作的复杂度高及O(n)

>>> from collections import deque
>>> dq = deque(range(10), maxlen=10)
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)

>>> dq.rotate(3)
>>> dq
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
>>> dq.rotate(-4)
>>> dq
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)

>>> dq.appendleft(-1)
>>> dq

deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.extend([11, 22, 33])
>>> dq
deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)

>>> dq.extendleft([10, 20, 30, 40])
>>> dq
deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

Counter

Count用来统计有关要素的出现次数。

>>> from collections import Counter
>>> ct = Counter('abracadabra')
>>> ct
Counter({'a': 5, 'r': 2, 'b': 2, 'd': 1, 'c': 1})
>>> ct.update('aaaaazzz')
>>> ct
Counter({'a': 10, 'z': 3, 'r': 2, 'b': 2, 'd': 1, 'c': 1})
>>> ct.most_common(2)
[('a', 10), ('z', 3)]
>>> ct.elements()
<itertools.chain object at 0x7fbaad4b44e0>

namedtuple

使用namedtuple(typename, field_names)命名tuple中之要素来要程序还有着可读性。

>>> from collections import namedtuple
>>> City = namedtuple('City', 'name country population coordinates')
>>> tokyo = City('Tokyo', 'JP', 36.933, (35.689722, 139.691667))
>>> tokyo
City(name='Tokyo', country='JP', population=36.933, coordinates=(35.689722, 139.691667))
>>> tokyo.population
36.933
>>> tokyo.coordinates
(35.689722, 139.691667)
>>> tokyo[1]
'JP'

>>> City._fields
('name', 'country', 'population', 'coordinates')
>>> LatLong = namedtuple('LatLong', 'lat long')
>>> delhi_data = ('Delhi NCR', 'IN', 21.935, LatLong(28.613889, 77.208889))
>>> delhi = City._make(delhi_data)
>>> delhi._asdict()
OrderedDict([('name', 'Delhi NCR'), ('country', 'IN'), ('population', 21.935),
            ('coordinates', LatLong(lat=28.613889, long=77.208889))])
>>> for key, value in delhi._asdict().items():
        print(key + ':', value)

name: Delhi NCR
country: IN
population: 21.935
coordinates: LatLong(lat=28.613889, long=77.208889)

ChainMap

ChainMap足就此来统一多单字典。

>>> from collections import ChainMap
>>> d = ChainMap({'zebra': 'black'}, {'elephant': 'blue'}, {'lion': 'yellow'})
>>> d['lion'] = 'orange'
>>> d['snake'] = 'red'
>>> d
ChainMap({'lion': 'orange', 'zebra': 'black', 'snake': 'red'},
         {'elephant': 'blue'}, {'lion': 'yellow'})

>>> del d['lion']
>>> del d['elephant']
Traceback (most recent call last):
  File "/usr/lib/python3.5/collections/__init__.py", line 929, in __delitem__
    del self.maps[0][key]
KeyError: 'elephant'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.5/collections/__init__.py", line 931, in __delitem__
    raise KeyError('Key not found in the first mapping: {!r}'.format(key))
KeyError: "Key not found in the first mapping: 'elephant'"

从上面del['elephant']的报错信息方可关押出来,对于反键值的操作ChainMap只见面在率先单字典self.maps[0][key]进展搜寻,新加的键值对啊都见面进入第一单字典,我们来改进一下ChainMap解决是题材:

class DeepChainMap(ChainMap):
    'Variant of ChainMap that allows direct updates to inner scopes'

    def __setitem__(self, key, value):
        for mapping in self.maps:
            if key in mapping:
                mapping[key] = value
                return
        self.maps[0][key] = value

    def __delitem__(self, key):
        for mapping in self.maps:
            if key in mapping:
                del mapping[key]
                return
        raise KeyError(key)

>>> d = DeepChainMap({'zebra': 'black'}, {'elephant': 'blue'}, {'lion': 'yellow'})
>>> d['lion'] = 'orange'         # update an existing key two levels down
>>> d['snake'] = 'red'           # new keys get added to the topmost dict
>>> del d['elephant']            # remove an existing key one level down
DeepChainMap({'zebra': 'black', 'snake': 'red'}, {}, {'lion': 'orange'})

可以下new_child来deepcopy一个ChainMap:

>>> from collections import ChainMap
>>> a = {'a': 'A', 'c': 'C'}
>>> b = {'b': 'B', 'c': 'D'}

>>> m = ChainMap({'a': 'A', 'c': 'C'}, {'b': 'B', 'c': 'D'})
>>> m
ChainMap({'a': 'A', 'c': 'C'}, {'b': 'B', 'c': 'D'})
>>> m['c']
'C'
>>> m.maps
[{'c': 'C', 'a': 'A'}, {'c': 'D', 'b': 'B'}]

>>> a['c'] = 'E'
>>> m['c']
'E'
>>> m
ChainMap({'c': 'E', 'a': 'A'}, {'c': 'D', 'b': 'B'})

>>> m2 = m.new_child()
>>> m2['c'] = 'f'
>>> m2
ChainMap({'c': 'f'}, {'c': 'E', 'a': 'A'}, {'c': 'D', 'b': 'B'})
>>> m
ChainMap({'c': 'E', 'a': 'A'}, {'c': 'D', 'b': 'B'})
>>> m2.parents
ChainMap({'c': 'E', 'a': 'A'}, {'c': 'D', 'b': 'B'})

UserDict

脚我们来改善一下字典,查询字典的时刻以key转换为str的款式:

class StrKeyDict0(dict):

    def __missing__(self, key):
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

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

    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()

解释一下上面这段先后:

  • 在__missing__中isinstance(key,
    str)是须要之,请想想一下为何?
    因为如果一个key不存的话,这会造成infinite recursion,self[str(key)]会晤还调用__getitem__。
  • __contains__啊是须兑现的,因为k in
    d的时刻会展开调用,但是注意就查找未果它吗非会见调用__missing__。关于__contains__还有一个细节就是:我们并无采取k in my_dict,因为str(key) in self的款式,因为这会造成递归调用__contains__。

这边尚强调一点,在Python2.x中dict.keys()会回去一个list,这代表k in
my_list必须全部历list。在Python3.x中针对dict.keys()做了优化,性能更胜,它见面回一个view如同set一样,详情参见官方文档。

上面这事例可以用UserDict改写,并且以具备的key都盖str的款式储存,而且这种写法更加常用简洁:

import collections


class StrKeyDict(collections.UserDict):

    def __missing__(self, key):
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):
        return str(key) in self.data

    def __setitem__(self, key, item):
        self.data[str(key)] = item

UserDict是MutableMapping和Mapping的子类,它继续了MutableMapping.update和Mapping.get两只基本点之主意,所以地方我们连没再写get方法,可以以源码被观看她的贯彻和我们地方的落实是大半的。

References

DOCUMENTATION-COLLECTIONS
FLUENT-PYTHON

Contact

GitHub:
https://github.com/ziwenxie
Blog:
https://www.ziwenxie.site

正文为作者原创,转载请给始明显处于声明博客出处
🙂

标签:, , , , ,

Your Comments

近期评论

    功能


    网站地图xml地图