1 class Counter(dict):  2     ‘‘‘Dict subclass for counting hashable items.  Sometimes called a bag  3     or multiset.  Elements are stored as dictionary keys and their counts  4     are stored as dictionary values.  5   6     >>> c = Counter(‘abcdeabcdabcaba‘)  # count elements from a string  7   8     >>> c.most_common(3)                # three most common elements  9     [(‘a‘, 5), (‘b‘, 4), (‘c‘, 3)] 10     >>> sorted(c)                       # list all unique elements 11     [‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘] 12     >>> ‘‘.join(sorted(c.elements()))   # list elements with repetitions 13     ‘aaaaabbbbcccdde‘ 14     >>> sum(c.values())                 # total of all counts 15     15 16  17     >>> c[‘a‘]                          # count of letter ‘a‘ 18     5 19     >>> for elem in ‘shazam‘:           # update counts from an iterable 20     ...     c[elem] += 1                # by adding 1 to each element‘s count 21     >>> c[‘a‘]                          # now there are seven ‘a‘ 22     7 23     >>> del c[‘b‘]                      # remove all ‘b‘ 24     >>> c[‘b‘]                          # now there are zero ‘b‘ 25     0 26  27     >>> d = Counter(‘simsalabim‘)       # make another counter 28     >>> c.update(d)                     # add in the second counter 29     >>> c[‘a‘]                          # now there are nine ‘a‘ 30     9 31  32     >>> c.clear()                       # empty the counter 33     >>> c 34     Counter() 35  36     Note:  If a count is set to zero or reduced to zero, it will remain 37     in the counter until the entry is deleted or the counter is cleared: 38  39     >>> c = Counter(‘aaabbc‘) 40     >>> c[‘b‘] -= 2                     # reduce the count of ‘b‘ by two 41     >>> c.most_common()                 # ‘b‘ is still in, but its count is zero 42     [(‘a‘, 3), (‘c‘, 1), (‘b‘, 0)] 43  44     ‘‘‘ 45     # References: 46     #   http://en.wikipedia.org/wiki/Multiset 47     #   http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html 48     #   http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm 49     #   http://code.activestate.com/recipes/259174/ 50     #   Knuth, TAOCP Vol. II section 4.6.3 51  52     def __init__(*args, **kwds): 53         ‘‘‘Create a new, empty Counter object.  And if given, count elements 54         from an input iterable.  Or, initialize the count from another mapping 55         of elements to their counts. 56  57         >>> c = Counter()                           # a new, empty counter 58         >>> c = Counter(‘gallahad‘)                 # a new counter from an iterable 59         >>> c = Counter({‘a‘: 4, ‘b‘: 2})           # a new counter from a mapping 60         >>> c = Counter(a=4, b=2)                   # a new counter from keyword args 61  62         ‘‘‘ 63         if not args: 64             raise TypeError("descriptor ‘__init__‘ of ‘Counter‘ object " 65                             "needs an argument") 66         self = args[0] 67         args = args[1:] 68         if len(args) > 1: 69             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args)) 70         super(Counter, self).__init__() 71         self.update(*args, **kwds) 72  73     def __missing__(self, key): 74         ‘The count of elements not in the Counter is zero.‘ 75         # Needed so that self[missing_item] does not raise KeyError 76         return 0 77  78     def most_common(self, n=None): 79         ‘‘‘List the n most common elements and their counts from the most 80         common to the least.  If n is None, then list all element counts. 81  82         >>> Counter(‘abcdeabcdabcaba‘).most_common(3) 83         [(‘a‘, 5), (‘b‘, 4), (‘c‘, 3)] 84  85         ‘‘‘ 86         # Emulate Bag.sortedByCount from Smalltalk 87         if n is None: 88             return sorted(self.iteritems(), key=_itemgetter(1), reverse=True) 89         return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1)) 90  91     def elements(self): 92         ‘‘‘Iterator over elements repeating each as many times as its count. 93  94         >>> c = Counter(‘ABCABC‘) 95         >>> sorted(c.elements()) 96         [‘A‘, ‘A‘, ‘B‘, ‘B‘, ‘C‘, ‘C‘] 97  98         # Knuth‘s example for prime factors of 1836:  2**2 * 3**3 * 17**1 99         >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})100         >>> product = 1101         >>> for factor in prime_factors.elements():     # loop over factors102         ...     product *= factor                       # and multiply them103         >>> product104         1836105 106         Note, if an element‘s count has been set to zero or is a negative107         number, elements() will ignore it.108 109         ‘‘‘110         # Emulate Bag.do from Smalltalk and Multiset.begin from C++.111         return _chain.from_iterable(_starmap(_repeat, self.iteritems()))112 113     # Override dict methods where necessary114 115     @classmethod116     def fromkeys(cls, iterable, v=None):117         # There is no equivalent method for counters because setting v=1118         # means that no element can have a count greater than one.119         raise NotImplementedError(120             ‘Counter.fromkeys() is undefined.  Use Counter(iterable) instead.‘)121 122     def update(*args, **kwds):123         ‘‘‘Like dict.update() but add counts instead of replacing them.124 125         Source can be an iterable, a dictionary, or another Counter instance.126 127         >>> c = Counter(‘which‘)128         >>> c.update(‘witch‘)           # add elements from another iterable129         >>> d = Counter(‘watch‘)130         >>> c.update(d)                 # add elements from another counter131         >>> c[‘h‘]                      # four ‘h‘ in which, witch, and watch132         4133 134         ‘‘‘135         # The regular dict.update() operation makes no sense here because the136         # replace behavior results in the some of original untouched counts137         # being mixed-in with all of the other counts for a mismash that138         # doesn‘t have a straight-forward interpretation in most counting139         # contexts.  Instead, we implement straight-addition.  Both the inputs140         # and outputs are allowed to contain zero and negative counts.141 142         if not args:143             raise TypeError("descriptor ‘update‘ of ‘Counter‘ object "144                             "needs an argument")145         self = args[0]146         args = args[1:]147         if len(args) > 1:148             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args))149         iterable = args[0] if args else None150         if iterable is not None:151             if isinstance(iterable, Mapping):152                 if self:153                     self_get = self.get154                     for elem, count in iterable.iteritems():155                         self[elem] = self_get(elem, 0) + count156                 else:157                     super(Counter, self).update(iterable) # fast path when counter is empty158             else:159                 self_get = self.get160                 for elem in iterable:161                     self[elem] = self_get(elem, 0) + 1162         if kwds:163             self.update(kwds)164 165     def subtract(*args, **kwds):166         ‘‘‘Like dict.update() but subtracts counts instead of replacing them.167         Counts can be reduced below zero.  Both the inputs and outputs are168         allowed to contain zero and negative counts.169 170         Source can be an iterable, a dictionary, or another Counter instance.171 172         >>> c = Counter(‘which‘)173         >>> c.subtract(‘witch‘)             # subtract elements from another iterable174         >>> c.subtract(Counter(‘watch‘))    # subtract elements from another counter175         >>> c[‘h‘]                          # 2 in which, minus 1 in witch, minus 1 in watch176         0177         >>> c[‘w‘]                          # 1 in which, minus 1 in witch, minus 1 in watch178         -1179 180         ‘‘‘181         if not args:182             raise TypeError("descriptor ‘subtract‘ of ‘Counter‘ object "183                             "needs an argument")184         self = args[0]185         args = args[1:]186         if len(args) > 1:187             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args))188         iterable = args[0] if args else None189         if iterable is not None:190             self_get = self.get191             if isinstance(iterable, Mapping):192                 for elem, count in iterable.items():193                     self[elem] = self_get(elem, 0) - count194             else:195                 for elem in iterable:196                     self[elem] = self_get(elem, 0) - 1197         if kwds:198             self.subtract(kwds)199 200     def copy(self):201         ‘Return a shallow copy.‘202         return self.__class__(self)203 204     def __reduce__(self):205         return self.__class__, (dict(self),)206 207     def __delitem__(self, elem):208         ‘Like dict.__delitem__() but does not raise KeyError for missing values.‘209         if elem in self:210             super(Counter, self).__delitem__(elem)211 212     def __repr__(self):213         if not self:214             return ‘%s()‘ % self.__class__.__name__215         items = ‘, ‘.join(map(‘%r: %r‘.__mod__, self.most_common()))216         return ‘%s({%s})‘ % (self.__class__.__name__, items)217 218     # Multiset-style mathematical operations discussed in:219     #       Knuth TAOCP Volume II section 4.6.3 exercise 19220     #       and at http://en.wikipedia.org/wiki/Multiset221     #222     # Outputs guaranteed to only include positive counts.223     #224     # To strip negative and zero counts, add-in an empty counter:225     #       c += Counter()226 227     def __add__(self, other):228         ‘‘‘Add counts from two counters.229 230         >>> Counter(‘abbb‘) + Counter(‘bcc‘)231         Counter({‘b‘: 4, ‘c‘: 2, ‘a‘: 1})232 233         ‘‘‘234         if not isinstance(other, Counter):235             return NotImplemented236         result = Counter()237         for elem, count in self.items():238             newcount = count + other[elem]239             if newcount > 0:240                 result[elem] = newcount241         for elem, count in other.items():242             if elem not in self and count > 0:243                 result[elem] = count244         return result245 246     def __sub__(self, other):247         ‘‘‘ Subtract count, but keep only results with positive counts.248 249         >>> Counter(‘abbbc‘) - Counter(‘bccd‘)250         Counter({‘b‘: 2, ‘a‘: 1})251 252         ‘‘‘253         if not isinstance(other, Counter):254             return NotImplemented255         result = Counter()256         for elem, count in self.items():257             newcount = count - other[elem]258             if newcount > 0:259                 result[elem] = newcount260         for elem, count in other.items():261             if elem not in self and count < 0:262                 result[elem] = 0 - count263         return result264 265     def __or__(self, other):266         ‘‘‘Union is the maximum of value in either of the input counters.267 268         >>> Counter(‘abbb‘) | Counter(‘bcc‘)269         Counter({‘b‘: 3, ‘c‘: 2, ‘a‘: 1})270 271         ‘‘‘272         if not isinstance(other, Counter):273             return NotImplemented274         result = Counter()275         for elem, count in self.items():276             other_count = other[elem]277             newcount = other_count if count < other_count else count278             if newcount > 0:279                 result[elem] = newcount280         for elem, count in other.items():281             if elem not in self and count > 0:282                 result[elem] = count283         return result284 285     def __and__(self, other):286         ‘‘‘ Intersection is the minimum of corresponding counts.287 288         >>> Counter(‘abbb‘) & Counter(‘bcc‘)289         Counter({‘b‘: 1})290 291         ‘‘‘292         if not isinstance(other, Counter):293             return NotImplemented294         result = Counter()295         for elem, count in self.items():296             other_count = other[elem]297             newcount = count if count < other_count else other_count298             if newcount > 0:299                 result[elem] = newcount300         return result301 302 303 if __name__ == ‘__main__‘:304     # verify that instances can be pickled305     from cPickle import loads, dumps306     Point = namedtuple(‘Point‘, ‘x, y‘, True)307     p = Point(x=10, y=20)308     assert p == loads(dumps(p))309 310     # test and demonstrate ability to override methods311     class Point(namedtuple(‘Point‘, ‘x y‘)):312         __slots__ = ()313         @property314         def hypot(self):315             return (self.x ** 2 + self.y ** 2) ** 0.5316         def __str__(self):317             return ‘Point: x=%6.3f  y=%6.3f  hypot=%6.3f‘ % (self.x, self.y, self.hypot)318 319     for p in Point(3, 4), Point(14, 5/7.):320         print p321 322     class Point(namedtuple(‘Point‘, ‘x y‘)):323         ‘Point class with optimized _make() and _replace() without error-checking‘324         __slots__ = ()325         _make = classmethod(tuple.__new__)326         def _replace(self, _map=map, **kwds):327             return self._make(_map(kwds.get, (‘x‘, ‘y‘), self))328 329     print Point(11, 22)._replace(x=100)330 331     Point3D = namedtuple(‘Point3D‘, Point._fields + (‘z‘,))332     print Point3D.__doc__333 334     import doctest335     TestResults = namedtuple(‘TestResults‘, ‘failed attempted‘)336     print TestResults(*doctest.testmod())

 1 >>> import collections 2 >>> c1 = collections.Counter(‘aabbccddww‘) 3 >>> c1 4 Counter({‘a‘: 2, ‘c‘: 2, ‘b‘: 2, ‘d‘: 2, ‘w‘: 2}) 5 >>> c1.most_common(3)  取出前三个 6 [(‘a‘, 2), (‘c‘, 2), (‘b‘, 2)] 7 >>> c2 = collections.Counter(‘aabbttyy‘) 8 >>> c2 9 Counter({‘a‘: 2, ‘y‘: 2, ‘b‘: 2, ‘t‘: 2})10 >>> c1.update(c2)  合并，c2的元素合并到了c111 >>> c112 Counter({‘a‘: 4, ‘b‘: 4, ‘c‘: 2, ‘d‘: 2, ‘t‘: 2, ‘w‘: 2, ‘y‘: 13 14 2})15 >>> c1[‘a‘]       取出计数器中的元素，没有返回016 417 >>> c1[‘g‘]18 019 >>> c2.clear()  清除20 >>> c1.elements()  返回一个迭代器21 <itertools.chain object at 0x015A63F0>22 >>> for item in c1.elements():23 ...     print item24 ...25 a26 a27 a28 a29 c30 c31 b32 b33 b34 b35 d36 d37 t38 t39 w40 w41 y42 y

  1 class OrderedDict(dict):  2     ‘Dictionary that remembers insertion order‘  3     # An inherited dict maps keys to values.  4     # The inherited dict provides __getitem__, __len__, __contains__, and get.  5     # The remaining methods are order-aware.  6     # Big-O running times for all methods are the same as regular dictionaries.  7   8     # The internal self.__map dict maps keys to links in a doubly linked list.  9     # The circular doubly linked list starts and ends with a sentinel element. 10     # The sentinel element never gets deleted (this simplifies the algorithm). 11     # Each link is stored as a list of length three:  [PREV, NEXT, KEY]. 12  13     def __init__(*args, **kwds): 14         ‘‘‘Initialize an ordered dictionary.  The signature is the same as 15         regular dictionaries, but keyword arguments are not recommended because 16         their insertion order is arbitrary. 17  18         ‘‘‘ 19         if not args: 20             raise TypeError("descriptor ‘__init__‘ of ‘OrderedDict‘ object " 21                             "needs an argument") 22         self = args[0] 23         args = args[1:] 24         if len(args) > 1: 25             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args)) 26         try: 27             self.__root 28         except AttributeError: 29             self.__root = root = []                     # sentinel node 30             root[:] = [root, root, None] 31             self.__map = {} 32         self.__update(*args, **kwds) 33  34     def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 35         ‘od.__setitem__(i, y) <==> od[i]=y‘ 36         # Setting a new item creates a new link at the end of the linked list, 37         # and the inherited dictionary is updated with the new key/value pair. 38         if key not in self: 39             root = self.__root 40             last = root[0] 41             last[1] = root[0] = self.__map[key] = [last, root, key] 42         return dict_setitem(self, key, value) 43  44     def __delitem__(self, key, dict_delitem=dict.__delitem__): 45         ‘od.__delitem__(y) <==> del od[y]‘ 46         # Deleting an existing item uses self.__map to find the link which gets 47         # removed by updating the links in the predecessor and successor nodes. 48         dict_delitem(self, key) 49         link_prev, link_next, _ = self.__map.pop(key) 50         link_prev[1] = link_next                        # update link_prev[NEXT] 51         link_next[0] = link_prev                        # update link_next[PREV] 52  53     def __iter__(self): 54         ‘od.__iter__() <==> iter(od)‘ 55         # Traverse the linked list in order. 56         root = self.__root 57         curr = root[1]                                  # start at the first node 58         while curr is not root: 59             yield curr[2]                               # yield the curr[KEY] 60             curr = curr[1]                              # move to next node 61  62     def __reversed__(self): 63         ‘od.__reversed__() <==> reversed(od)‘ 64         # Traverse the linked list in reverse order. 65         root = self.__root 66         curr = root[0]                                  # start at the last node 67         while curr is not root: 68             yield curr[2]                               # yield the curr[KEY] 69             curr = curr[0]                              # move to previous node 70  71     def clear(self): 72         ‘od.clear() -> None.  Remove all items from od.‘ 73         root = self.__root 74         root[:] = [root, root, None] 75         self.__map.clear() 76         dict.clear(self) 77  78     # -- the following methods do not depend on the internal structure -- 79  80     def keys(self): 81         ‘od.keys() -> list of keys in od‘ 82         return list(self) 83  84     def values(self): 85         ‘od.values() -> list of values in od‘ 86         return [self[key] for key in self] 87  88     def items(self): 89         ‘od.items() -> list of (key, value) pairs in od‘ 90         return [(key, self[key]) for key in self] 91  92     def iterkeys(self): 93         ‘od.iterkeys() -> an iterator over the keys in od‘ 94         return iter(self) 95  96     def itervalues(self): 97         ‘od.itervalues -> an iterator over the values in od‘ 98         for k in self: 99             yield self[k]100 101     def iteritems(self):102         ‘od.iteritems -> an iterator over the (key, value) pairs in od‘103         for k in self:104             yield (k, self[k])105 106     update = MutableMapping.update107 108     __update = update # let subclasses override update without breaking __init__109 110     __marker = object()111 112     def pop(self, key, default=__marker):113         ‘‘‘od.pop(k[,d]) -> v, remove specified key and return the corresponding114         value.  If key is not found, d is returned if given, otherwise KeyError115         is raised.116 117         ‘‘‘118         if key in self:119             result = self[key]120             del self[key]121             return result122         if default is self.__marker:123             raise KeyError(key)124         return default125 126     def setdefault(self, key, default=None):127         ‘od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od‘128         if key in self:129             return self[key]130         self[key] = default131         return default132 133     def popitem(self, last=True):134         ‘‘‘od.popitem() -> (k, v), return and remove a (key, value) pair.135         Pairs are returned in LIFO order if last is true or FIFO order if false.136 137         ‘‘‘138         if not self:139             raise KeyError(‘dictionary is empty‘)140         key = next(reversed(self) if last else iter(self))141         value =http://www.mamicode.com/ self.pop(key)142         return key, value143 144     def __repr__(self, _repr_running={}):145         ‘od.__repr__() <==> repr(od)‘146         call_key = id(self), _get_ident()147         if call_key in _repr_running:148             return ‘...‘149         _repr_running[call_key] = 1150         try:151             if not self:152                 return ‘%s()‘ % (self.__class__.__name__,)153             return ‘%s(%r)‘ % (self.__class__.__name__, self.items())154         finally:155             del _repr_running[call_key]156 157     def __reduce__(self):158         ‘Return state information for pickling‘159         items = [[k, self[k]] for k in self]160         inst_dict = vars(self).copy()161         for k in vars(OrderedDict()):162             inst_dict.pop(k, None)163         if inst_dict:164             return (self.__class__, (items,), inst_dict)165         return self.__class__, (items,)166 167     def copy(self):168         ‘od.copy() -> a shallow copy of od‘169         return self.__class__(self)170 171     @classmethod172     def fromkeys(cls, iterable, value=http://www.mamicode.com/None):173         ‘‘‘OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.174         If not specified, the value defaults to None.175 176         ‘‘‘177         self = cls()178         for key in iterable:179             self[key] = value180         return self181 182     def __eq__(self, other):183         ‘‘‘od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive184         while comparison to a regular mapping is order-insensitive.185 186         ‘‘‘187         if isinstance(other, OrderedDict):188             return dict.__eq__(self, other) and all(_imap(_eq, self, other))189         return dict.__eq__(self, other)190 191     def __ne__(self, other):192         ‘od.__ne__(y) <==> od!=y‘193         return not self == other194 195     # -- the following methods support python 3.x style dictionary views --196 197     def viewkeys(self):198         "od.viewkeys() -> a set-like object providing a view on od‘s keys"199         return KeysView(self)200 201     def viewvalues(self):202         "od.viewvalues() -> an object providing a view on od‘s values"203         return ValuesView(self)204 205     def viewitems(self):206         "od.viewitems() -> a set-like object providing a view on od‘s items"207         return ItemsView(self)208 209 210 ################################################################################211 ### namedtuple212 ################################################################################213 214 _class_template = ‘‘‘215 class {typename}(tuple):216     ‘{typename}({arg_list})‘217 218     __slots__ = ()219 220     _fields = {field_names!r}221 222     def __new__(_cls, {arg_list}):223         ‘Create new instance of {typename}({arg_list})‘224         return _tuple.__new__(_cls, ({arg_list}))225 226     @classmethod227     def _make(cls, iterable, new=tuple.__new__, len=len):228         ‘Make a new {typename} object from a sequence or iterable‘229         result = new(cls, iterable)230         if len(result) != {num_fields:d}:231             raise TypeError(‘Expected {num_fields:d} arguments, got %d‘ % len(result))232         return result233 234     def __repr__(self):235         ‘Return a nicely formatted representation string‘236         return ‘{typename}({repr_fmt})‘ % self237 238     def _asdict(self):239         ‘Return a new OrderedDict which maps field names to their values‘240         return OrderedDict(zip(self._fields, self))241 242     def _replace(_self, **kwds):243         ‘Return a new {typename} object replacing specified fields with new values‘244         result = _self._make(map(kwds.pop, {field_names!r}, _self))245         if kwds:246             raise ValueError(‘Got unexpected field names: %r‘ % kwds.keys())247         return result248 249     def __getnewargs__(self):250         ‘Return self as a plain tuple.  Used by copy and pickle.‘251         return tuple(self)252 253     __dict__ = _property(_asdict)254 255     def __getstate__(self):256         ‘Exclude the OrderedDict from pickling‘257         pass258 259 {field_defs}260 ‘‘‘261 262 _repr_template = ‘{name}=%r‘263 264 _field_template = ‘‘‘265     {name} = _property(_itemgetter({index:d}), doc=‘Alias for field number {index:d}‘)266 ‘‘‘267 268 def namedtuple(typename, field_names, verbose=False, rename=False):269     """Returns a new subclass of tuple with named fields.270 271     >>> Point = namedtuple(‘Point‘, [‘x‘, ‘y‘])272     >>> Point.__doc__                   # docstring for the new class273     ‘Point(x, y)‘274     >>> p = Point(11, y=22)             # instantiate with positional args or keywords275     >>> p[0] + p[1]                     # indexable like a plain tuple276     33277     >>> x, y = p                        # unpack like a regular tuple278     >>> x, y279     (11, 22)280     >>> p.x + p.y                       # fields also accessable by name281     33282     >>> d = p._asdict()                 # convert to a dictionary283     >>> d[‘x‘]284     11285     >>> Point(**d)                      # convert from a dictionary286     Point(x=11, y=22)287     >>> p._replace(x=100)               # _replace() is like str.replace() but targets named fields288     Point(x=100, y=22)289 290     """291 292     # Validate the field names.  At the user‘s option, either generate an error293     # message or automatically replace the field name with a valid name.294     if isinstance(field_names, basestring):295         field_names = field_names.replace(‘,‘, ‘ ‘).split()296     field_names = map(str, field_names)297     typename = str(typename)298     if rename:299         seen = set()300         for index, name in enumerate(field_names):301             if (not all(c.isalnum() or c==‘_‘ for c in name)302                 or _iskeyword(name)303                 or not name304                 or name[0].isdigit()305                 or name.startswith(‘_‘)306                 or name in seen):307                 field_names[index] = ‘_%d‘ % index308             seen.add(name)309     for name in [typename] + field_names:310         if type(name) != str:311             raise TypeError(‘Type names and field names must be strings‘)312         if not all(c.isalnum() or c==‘_‘ for c in name):313             raise ValueError(‘Type names and field names can only contain ‘314                              ‘alphanumeric characters and underscores: %r‘ % name)315         if _iskeyword(name):316             raise ValueError(‘Type names and field names cannot be a ‘317                              ‘keyword: %r‘ % name)318         if name[0].isdigit():319             raise ValueError(‘Type names and field names cannot start with ‘320                              ‘a number: %r‘ % name)321     seen = set()322     for name in field_names:323         if name.startswith(‘_‘) and not rename:324             raise ValueError(‘Field names cannot start with an underscore: ‘325                              ‘%r‘ % name)326         if name in seen:327             raise ValueError(‘Encountered duplicate field name: %r‘ % name)328         seen.add(name)329 330     # Fill-in the class template331     class_definition = _class_template.format(332         typename = typename,333         field_names = tuple(field_names),334         num_fields = len(field_names),335         arg_list = repr(tuple(field_names)).replace("‘", "")[1:-1],336         repr_fmt = ‘, ‘.join(_repr_template.format(name=name)337                              for name in field_names),338         field_defs = ‘\n‘.join(_field_template.format(index=index, name=name)339                                for index, name in enumerate(field_names))340     )341     if verbose:342         print class_definition343 344     # Execute the template string in a temporary namespace and support345     # tracing utilities by setting a value for frame.f_globals[‘__name__‘]346     namespace = dict(_itemgetter=_itemgetter, __name__=‘namedtuple_%s‘ % typename,347                      OrderedDict=OrderedDict, _property=property, _tuple=tuple)348     try:349         exec class_definition in namespace350     except SyntaxError as e:351         raise SyntaxError(e.message + ‘:\n‘ + class_definition)352     result = namespace[typename]353 354     # For pickling to work, the __module__ variable needs to be set to the frame355     # where the named tuple is created.  Bypass this step in environments where356     # sys._getframe is not defined (Jython for example) or sys._getframe is not357     # defined for arguments greater than 0 (IronPython).358     try:359         result.__module__ = _sys._getframe(1).f_globals.get(‘__name__‘, ‘__main__‘)360     except (AttributeError, ValueError):361         pass362 363     return result364 365 366 ########################################################################367 ###  Counter368 ########################################################################369 370 class Counter(dict):371     ‘‘‘Dict subclass for counting hashable items.  Sometimes called a bag372     or multiset.  Elements are stored as dictionary keys and their counts373     are stored as dictionary values.374 375     >>> c = Counter(‘abcdeabcdabcaba‘)  # count elements from a string376 377     >>> c.most_common(3)                # three most common elements378     [(‘a‘, 5), (‘b‘, 4), (‘c‘, 3)]379     >>> sorted(c)                       # list all unique elements380     [‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘]381     >>> ‘‘.join(sorted(c.elements()))   # list elements with repetitions382     ‘aaaaabbbbcccdde‘383     >>> sum(c.values())                 # total of all counts384     15385 386     >>> c[‘a‘]                          # count of letter ‘a‘387     5388     >>> for elem in ‘shazam‘:           # update counts from an iterable389     ...     c[elem] += 1                # by adding 1 to each element‘s count390     >>> c[‘a‘]                          # now there are seven ‘a‘391     7392     >>> del c[‘b‘]                      # remove all ‘b‘393     >>> c[‘b‘]                          # now there are zero ‘b‘394     0395 396     >>> d = Counter(‘simsalabim‘)       # make another counter397     >>> c.update(d)                     # add in the second counter398     >>> c[‘a‘]                          # now there are nine ‘a‘399     9400 401     >>> c.clear()                       # empty the counter402     >>> c403     Counter()404 405     Note:  If a count is set to zero or reduced to zero, it will remain406     in the counter until the entry is deleted or the counter is cleared:407 408     >>> c = Counter(‘aaabbc‘)409     >>> c[‘b‘] -= 2                     # reduce the count of ‘b‘ by two410     >>> c.most_common()                 # ‘b‘ is still in, but its count is zero411     [(‘a‘, 3), (‘c‘, 1), (‘b‘, 0)]412 413     ‘‘‘414     # References:415     #   http://en.wikipedia.org/wiki/Multiset416     #   http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html417     #   http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm418     #   http://code.activestate.com/recipes/259174/419     #   Knuth, TAOCP Vol. II section 4.6.3420 421     def __init__(*args, **kwds):422         ‘‘‘Create a new, empty Counter object.  And if given, count elements423         from an input iterable.  Or, initialize the count from another mapping424         of elements to their counts.425 426         >>> c = Counter()                           # a new, empty counter427         >>> c = Counter(‘gallahad‘)                 # a new counter from an iterable428         >>> c = Counter({‘a‘: 4, ‘b‘: 2})           # a new counter from a mapping429         >>> c = Counter(a=4, b=2)                   # a new counter from keyword args430 431         ‘‘‘432         if not args:433             raise TypeError("descriptor ‘__init__‘ of ‘Counter‘ object "434                             "needs an argument")435         self = args[0]436         args = args[1:]437         if len(args) > 1:438             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args))439         super(Counter, self).__init__()440         self.update(*args, **kwds)441 442     def __missing__(self, key):443         ‘The count of elements not in the Counter is zero.‘444         # Needed so that self[missing_item] does not raise KeyError445         return 0446 447     def most_common(self, n=None):448         ‘‘‘List the n most common elements and their counts from the most449         common to the least.  If n is None, then list all element counts.450 451         >>> Counter(‘abcdeabcdabcaba‘).most_common(3)452         [(‘a‘, 5), (‘b‘, 4), (‘c‘, 3)]453 454         ‘‘‘455         # Emulate Bag.sortedByCount from Smalltalk456         if n is None:457             return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)458         return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))459 460     def elements(self):461         ‘‘‘Iterator over elements repeating each as many times as its count.462 463         >>> c = Counter(‘ABCABC‘)464         >>> sorted(c.elements())465         [‘A‘, ‘A‘, ‘B‘, ‘B‘, ‘C‘, ‘C‘]466 467         # Knuth‘s example for prime factors of 1836:  2**2 * 3**3 * 17**1468         >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})469         >>> product = 1470         >>> for factor in prime_factors.elements():     # loop over factors471         ...     product *= factor                       # and multiply them472         >>> product473         1836474 475         Note, if an element‘s count has been set to zero or is a negative476         number, elements() will ignore it.477 478         ‘‘‘479         # Emulate Bag.do from Smalltalk and Multiset.begin from C++.480         return _chain.from_iterable(_starmap(_repeat, self.iteritems()))481 482     # Override dict methods where necessary483 484     @classmethod485     def fromkeys(cls, iterable, v=None):486         # There is no equivalent method for counters because setting v=1487         # means that no element can have a count greater than one.488         raise NotImplementedError(489             ‘Counter.fromkeys() is undefined.  Use Counter(iterable) instead.‘)490 491     def update(*args, **kwds):492         ‘‘‘Like dict.update() but add counts instead of replacing them.493 494         Source can be an iterable, a dictionary, or another Counter instance.495 496         >>> c = Counter(‘which‘)497         >>> c.update(‘witch‘)           # add elements from another iterable498         >>> d = Counter(‘watch‘)499         >>> c.update(d)                 # add elements from another counter500         >>> c[‘h‘]                      # four ‘h‘ in which, witch, and watch501         4502 503         ‘‘‘504         # The regular dict.update() operation makes no sense here because the505         # replace behavior results in the some of original untouched counts506         # being mixed-in with all of the other counts for a mismash that507         # doesn‘t have a straight-forward interpretation in most counting508         # contexts.  Instead, we implement straight-addition.  Both the inputs509         # and outputs are allowed to contain zero and negative counts.510 511         if not args:512             raise TypeError("descriptor ‘update‘ of ‘Counter‘ object "513                             "needs an argument")514         self = args[0]515         args = args[1:]516         if len(args) > 1:517             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args))518         iterable = args[0] if args else None519         if iterable is not None:520             if isinstance(iterable, Mapping):521                 if self:522                     self_get = self.get523                     for elem, count in iterable.iteritems():524                         self[elem] = self_get(elem, 0) + count525                 else:526                     super(Counter, self).update(iterable) # fast path when counter is empty527             else:528                 self_get = self.get529                 for elem in iterable:530                     self[elem] = self_get(elem, 0) + 1531         if kwds:532             self.update(kwds)533 534     def subtract(*args, **kwds):535         ‘‘‘Like dict.update() but subtracts counts instead of replacing them.536         Counts can be reduced below zero.  Both the inputs and outputs are537         allowed to contain zero and negative counts.538 539         Source can be an iterable, a dictionary, or another Counter instance.540 541         >>> c = Counter(‘which‘)542         >>> c.subtract(‘witch‘)             # subtract elements from another iterable543         >>> c.subtract(Counter(‘watch‘))    # subtract elements from another counter544         >>> c[‘h‘]                          # 2 in which, minus 1 in witch, minus 1 in watch545         0546         >>> c[‘w‘]                          # 1 in which, minus 1 in witch, minus 1 in watch547         -1548 549         ‘‘‘550         if not args:551             raise TypeError("descriptor ‘subtract‘ of ‘Counter‘ object "552                             "needs an argument")553         self = args[0]554         args = args[1:]555         if len(args) > 1:556             raise TypeError(‘expected at most 1 arguments, got %d‘ % len(args))557         iterable = args[0] if args else None558         if iterable is not None:559             self_get = self.get560             if isinstance(iterable, Mapping):561                 for elem, count in iterable.items():562                     self[elem] = self_get(elem, 0) - count563             else:564                 for elem in iterable:565                     self[elem] = self_get(elem, 0) - 1566         if kwds:567             self.subtract(kwds)568 569     def copy(self):570         ‘Return a shallow copy.‘571         return self.__class__(self)572 573     def __reduce__(self):574         return self.__class__, (dict(self),)575 576     def __delitem__(self, elem):577         ‘Like dict.__delitem__() but does not raise KeyError for missing values.‘578         if elem in self:579             super(Counter, self).__delitem__(elem)580 581     def __repr__(self):582         if not self:583             return ‘%s()‘ % self.__class__.__name__584         items = ‘, ‘.join(map(‘%r: %r‘.__mod__, self.most_common()))585         return ‘%s({%s})‘ % (self.__class__.__name__, items)586 587     # Multiset-style mathematical operations discussed in:588     #       Knuth TAOCP Volume II section 4.6.3 exercise 19589     #       and at http://en.wikipedia.org/wiki/Multiset590     #591     # Outputs guaranteed to only include positive counts.592     #593     # To strip negative and zero counts, add-in an empty counter:594     #       c += Counter()595 596     def __add__(self, other):597         ‘‘‘Add counts from two counters.598 599         >>> Counter(‘abbb‘) + Counter(‘bcc‘)600         Counter({‘b‘: 4, ‘c‘: 2, ‘a‘: 1})601 602         ‘‘‘603         if not isinstance(other, Counter):604             return NotImplemented605         result = Counter()606         for elem, count in self.items():607             newcount = count + other[elem]608             if newcount > 0:609                 result[elem] = newcount610         for elem, count in other.items():611             if elem not in self and count > 0:612                 result[elem] = count613         return result614 615     def __sub__(self, other):616         ‘‘‘ Subtract count, but keep only results with positive counts.617 618         >>> Counter(‘abbbc‘) - Counter(‘bccd‘)619         Counter({‘b‘: 2, ‘a‘: 1})620 621         ‘‘‘622         if not isinstance(other, Counter):623             return NotImplemented624         result = Counter()625         for elem, count in self.items():626             newcount = count - other[elem]627             if newcount > 0:628                 result[elem] = newcount629         for elem, count in other.items():630             if elem not in self and count < 0:631                 result[elem] = 0 - count632         return result633 634     def __or__(self, other):635         ‘‘‘Union is the maximum of value in either of the input counters.636 637         >>> Counter(‘abbb‘) | Counter(‘bcc‘)638         Counter({‘b‘: 3, ‘c‘: 2, ‘a‘: 1})639 640         ‘‘‘641         if not isinstance(other, Counter):642             return NotImplemented643         result = Counter()644         for elem, count in self.items():645             other_count = other[elem]646             newcount = other_count if count < other_count else count647             if newcount > 0:648                 result[elem] = newcount649         for elem, count in other.items():650             if elem not in self and count > 0:651                 result[elem] = count652         return result653 654     def __and__(self, other):655         ‘‘‘ Intersection is the minimum of corresponding counts.656 657         >>> Counter(‘abbb‘) & Counter(‘bcc‘)658         Counter({‘b‘: 1})659 660         ‘‘‘661         if not isinstance(other, Counter):662             return NotImplemented663         result = Counter()664         for elem, count in self.items():665             other_count = other[elem]666             newcount = count if count < other_count else other_count667             if newcount > 0:668                 result[elem] = newcount669         return result670 671 672 if __name__ == ‘__main__‘:673     # verify that instances can be pickled674     from cPickle import loads, dumps675     Point = namedtuple(‘Point‘, ‘x, y‘, True)676     p = Point(x=10, y=20)677     assert p == loads(dumps(p))678 679     # test and demonstrate ability to override methods680     class Point(namedtuple(‘Point‘, ‘x y‘)):681         __slots__ = ()682         @property683         def hypot(self):684             return (self.x ** 2 + self.y ** 2) ** 0.5685         def __str__(self):686             return ‘Point: x=%6.3f  y=%6.3f  hypot=%6.3f‘ % (self.x, self.y, self.hypot)687 688     for p in Point(3, 4), Point(14, 5/7.):689         print p690 691     class Point(namedtuple(‘Point‘, ‘x y‘)):692         ‘Point class with optimized _make() and _replace() without error-checking‘693         __slots__ = ()694         _make = classmethod(tuple.__new__)695         def _replace(self, _map=map, **kwds):696             return self._make(_map(kwds.get, (‘x‘, ‘y‘), self))697 698     print Point(11, 22)._replace(x=100)699 700     Point3D = namedtuple(‘Point3D‘, Point._fields + (‘z‘,))701     print Point3D.__doc__702 703     import doctest704     TestResults = namedtuple(‘TestResults‘, ‘failed attempted‘)705     print TestResults(*doctest.testmod())

 1 >>> import collections 2 >>> c1 = collections.OrderedDict() 3 >>> c1[‘k1‘] = 1 4 >>> c1[‘k2‘] = 2 5 >>> c1[‘k3‘] = 3 6 >>> c1 7 OrderedDict([(‘k1‘, 1), (‘k2‘, 2), (‘k3‘, 3)])  有序 8 >>> c2 = {} 9 >>> c2[‘k1‘] = 110 >>> c2[‘k2‘] = 211 >>> c2[‘k3‘] = 312 >>> c213 {‘k3‘: 3, ‘k2‘: 2, ‘k1‘: 1}   无序