python数据结构(一) 内置类型

1. tuple

tuple是一种可以按照顺序存储一定数量其他对象的对象，它是不可变的。通常来说，tuple应该存储彼此不同的值，将不同数据整合到一个容器中。

1) 其他版本

• namedtuple
  如果我们希望知道tuple中每个元素的名字，提前知道我们要存储哪些数据，但是又不需要给对象添加行为，就可以用命名元组（namedtuple），这是组合只读数据的很好的方法。

from collections import namedtuple
Stock = nametuple("Stock", "symbol current high low")
stock = Stock("FB", 75, high=75.03, low=74.90)
>>> stock.high
75.03
>>> s, c, h, l = current
>>> s
FB

第一个参数是该命名元组的名城，第二个是由空格分隔的属性的字符串，即该命名元组属性（逗号也可以）。命名元组也可以被打包和解包。

命名元组的问题就是，一旦设置了元素值，就不能再更改了。如果要存储可修改的数据，用dict更合适一些。

2. dict

dict中每个键值都通过哈希算法映射成为一个整数值，因此dict内部是无序的，dict的键值也是不能修改的，比如tuple，str等。list和dict就不能作为dict的键值。

dict有很多用途，最常见的有：1）将其键用作小型对象的实例。2）每个键代表某种结构的一方面。这种情况下用namedtuple也是可以的，但如果我们需要不停往里添加键值，就要用dict了。

1）常用方法

• get(): 第一个参数为key，第二个可选参数为key不存在时返回的默认值

>>> dict = {'a': 5}
>>> dict.get('a', 'invalid')
5
>>> dict.get('b', 'invalid')
invalid

• setdefault(): 如果键名存在于dict中，返回对应值；否则，返回默认值，并将该键名对应value设为默认值。

>>> dict.setdefault('a', 0)
5
>>> dict.setdefault('b', 0)
0
>>> dict['b']
0

• keys(), values(), items(): 迭代器

2)其他版本

• defaultdict
  collections中对内置类型进行了很多针对性的扩展，从而可以在内置类型的基础上实现不同的功能，defaultdict就是对dict进行扩展的一种数据类型， 其构造函数需要传入一个函数作为参数，当不存在该键值时，调用该函数将其value设为默认值。

>>> from collections import defaultdict
>>> frequncies = defaultdict(int)  # 传入int函数，默认值为0
>>> def f():
        return 10
>>> d = defaultdict(f)
>>> d[5]
10

• Counter
  实际应用中，我们会遇到很多需要统计每个元素出现次数的场景，比如一个字符串，统计每个字母出现的次数等等。collections中的Counter就是为了处理这一场景而实现的。

>>> from collections import Counter
>>> s = 'Hello world'
>>>  frequency = Counter(s)
>>> print(frequency)
Counter({'l': 3, 'o': 2, 'H': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})
>>> frequency.most_common()
[('l', 3), ('o', 2), ('H', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

其中，most_common()是一个很有用的方法，可以返回一个元组构成的列表，[0][0]位置表示了出现次数最多的元素。

3. list

在python中，list通常用于存储一些“相同”类型对象的实例，如字符串、列表或我们自己定义的对象。如果我们想要按照某种顺序存储一些项目，就应该使用list。

1) 常用方法

• append(ele): 末尾添加元素
• insert(index, ele): 在制定位置插入元素
• count(ele): 统计某个元素的出现次数
• index(): 输出某个元素在列表中的索引位置，没有则抛出异常
• find(): 与index功能一样，没有不抛出异常，返回-1
• reverse(): 列表倒置
• sort(): 排序

2) 列表排序 sort()

如果不添加任何参数，sort方法会执行默认的行为，对字符串按照字母表顺序排列，数字列表按照数字顺序排列，元组列表按照第一个元素排列，不能比较则抛出TypeError异常。

• 自定义对象比较
  如果是自定义的对象，则需要同时定义小于方法：__lt__().

class WeirdSortee:
    def __init__(self, string, number, sort_num):
        self.string = string
        self.number = number
        self.sort_num = sort_num
        
    def __lt__(self, object):
        if self.sort_num:
            return self.number < object.number
        return self.string < object.string

    def __repr__(self):
        return "{}: {}".format(self.string, self.number)

>>> a = WeirdSortee('a', 4, True)
>>> b = WeirdSortee('b', 3, True)
>>> c = WeirdSortee('c', 2, True)
>>> d = WeirdSortee('d', 1, True)
>>> l = [a, b, c, d]
>>> l.sort()
>>> l
[a: 4, b: 3, c: 2, d: 1]

这里__repr__方法是为了打印方便.

从理论上来说，如果实现了__lt__方法，则需要实现类似的__gt__，__eq__，__ge__，__le__，__ne__等方法。也可以在实现了__eq__方法之后，调用@total_ordering类装饰器来免费获取其他方法。

from functools import total_ordering

@total_ordering
class WeirdSortee:
    def __init__(self, string, number, sort_num):
        self.string = string
        self.number = number
        self.sort_num = sort_num
        
    def __lt__(self, object):
        if self.sort_num:
            return self.number < object.number
        return self.string < object.string
    
    def __eq__(self, object):
        return all((
        self.string == object.string,
        self.number == object.number,
        self.sort_num == object.number
        ))
    
    def __repr__(self):
        return "{}: {}".format(self.string, self.number)

• 设置key参数
  如果只是为了自定义排序的顺序，实现这么多方法还是比较大材小用。可以通过设置sort方法的key参数，将列表中的对象转化成可以比较的对象，如

>>> l = ['hello', 'HELP', 'Helo']
>>> l.sort()
>>> l
['HELP', 'Helo', 'hello']
>>> l.sort(key=str.lower)
>>> l
>>> ['hello', 'Helo', 'HELP']

这里的lower方法也是可以接收self作为参数的，str.lower(item) 与item.lower()是一样的。

如果需要经常对元组构成的列表进行排序，但不是按照第一个元素进行排序，可以使用operator.itemgetter方法：

>>> from operator import itemgetter
>>> l = [('h', 4), ('n', 6), ('o', 5), ('p', 1), ('t', 3), ('y', 2)]
>>> l.sort()
>>> l
[('p', 1), ('y', 2), ('t', 3), ('h', 4), ('o', 5), ('n', 6)]
>>> l.sort(key = itemgetter(1))
>>> l
[('h', 4), ('n', 6), ('o', 5), ('p', 1), ('t', 3), ('y', 2)]

itemgetter也可以用于字典；attrgetter和methodcaller也可以达到相同的目的。

4. set

在python中，set可以保存任意可求哈希值的对象，因此，list和dict由于可变，不能作为set的元素。set和dict类似，都是无序的，无法通过索引来查找元素。

使用集合的原因一般有两个：1）利用其元素的唯一性，排除重复的元素。2）用于两个或多个集合组合。

1) 常用方法

• union(): 求并集，也可以用"|"
• intersesction(): 求交集，也可以用"&"
• symmetric_defference(): 在其中一个而不在两个集合中共同出现
• issubset(): 判断是否子集
• issuperset(): 判断是否超集

说明：当使用in来判断元素是否在容器中时，set要比list高效的多，因为set是通过计算元素的哈希值来判断，与set大小无关；list是遍历所有元素直到找到，与list长度有关。