【2017-08-31】数据结构与算法（二）

字典

• 字典中的键映射多个值
  通常情况下，一个键对应一个值，如果想要一个键对应多个值，那么需要将多个值放入其他容器中，如列表、集合，选择什么样的容器，取决的想要保留什么样的值。列表，能保持插入的顺序，元素可重复；集合，无序，元素唯一性。
     一方面可以自己实现，另一方面可以使用collections 模块中的 defaultdict 来构造这样的字典。defaultdict 的一个特征是它会自动初始化每个 key 刚开始对应的值，key对应的多个值需要什么容器由参数指定。需要注意的是，defaultdict 会自动为将要访问的键 (就算目前字典中并不存在这样的键) 创建映射实体。
     Defaultdict（）不传参数，说明内部存储值的容器默认是key与value是一对一的字典类型
     Defaultdict（list）传列表类型，说明内部存储值的容器是list。直接使用append方法给关键字添加值
     Defaultdict（set）传集合类型，说明内部存储值的容器是set。直接使用add方法给关键字添加值
    Defaultdict（）除了接受类型参数外，也可以接受无参数的调用函数
  简单看看defaultdict方法返回结果

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import defaultdict

default1=defaultdict(set)
print(default1)
#结果
>>defaultdict(<type 'set'>, {})

default1['a'].add(1)
default1['a'].add(1)
default1['a'].add(2)
print(default1)
#结果
>>defaultdict(<type 'set'>, {'a': set([1, 2])})

default2=defaultdict()
print(default2)
#结果
>>defaultdict(None, {})

default2['a']=1
default2['a']=2
print(default2)
#结果
>>defaultdict(None, {'a': 2})

实例一：将某些重复项按照键归档

from collections import defaultdict
pairs=[("name","ld"),("sex",1),("number","123456789"),("number","9999999")]
d=defaultdict(list)
for key,value in pairs:
       d[key].append(value)#如果自己实现，需要判断键是否存在
print(d)
#结果
>>defaultdict(<type 'list'>, {'number': ['123456789', '9999999'], 'name': ['ld'], 'sex': [1]})

实例二:统计单词出现的次数

from collections import defaultdict
strings=("hi","python","word","python","sweet","honey","hi","python")
counts=defaultdict(lambda :0)
for iterm in strings:
       counts[iterm]+=1
print(counts)
#结果
>>defaultdict(<function <lambda> at 0x01A93CF0>, {'python': 3, 'sweet': 1, 'honey': 1, 'hi': 2, 'word': 1})

• 字典排序
  通常下字典是无序的，不管添加的先后顺序（python3.6可以有序）
  如果要保持添加的顺序，可使用collections 模块中的OrderedDict 类。

from collections import OrderedDict
dicts={}
dicts["d"]=4
dicts["c"]=3
dicts["a"]=1
dicts["b"]=2
print(dicts)
#结果
>>{'a': 1, 'c': 3, 'b': 2, 'd': 4}
orderdict= OrderedDict()
orderdict["d"]=4
orderdict["c"]=3
orderdict["a"]=1
orderdict["b"]=2
print(orderdict)
#结果
>>OrderedDict([('d', 4), ('c', 3), ('a', 1), ('b', 2)])

   OrderedDict 内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候，它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。需要注意的是，一个 OrderedDict的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。所以使用时需要结合内存的消耗情况权衡是否使用OrderedDict