四、python数据类型的性能

比较列表list 和字典 dict 两种内置数据类型上各种操作大O数量级

两种都属于容器，都是可变类型。

List 列表数据类型常用操作性能

最常用：按索引取值和赋值（v=a[i],a[i]=v）
由于列表的随机访问特性，这两个操作执行时间与列表大小无关，数量级均为O(1)
另一个是列表增长，可以选择append()和_add_() "+"
lst.append(v),执行是将是o(1)
lst = lst + [v],执行时间是o(n+k),其中k是被加的列表长度 。（本质是生成一个新的列表再复制过去）
选择哪个方法来操作列表，决定了程序的性能

# 用+的方式生成
def test1():
    l = []
    for i in range(1000):
        l = l + [i]
    print(len(l))

# 用append方法添加元素
def test2():
    l = []
    for i in range(1000):
        l.append(i)

# 用列表推导式
def test3():
    l = [i for i in range(1000)]

# 用range函数调用转成列表
def test4():
    l = list(range(1000))


# 用timeit模块对函数进行计数
# 创建一个Timer对象，指定需要反复运行的语句和只需运行一次的安装语句
# 调用这个对象的timeit方法，其中可以指定反复运行多少次
# number 是重复执行代码的次数； 这个模块一般用于测试python函数的性能。
# Timer.timeit返回执行代码的平均耗时（float类型的秒数）
# t1 = Timer("test1()", "from __main__ import test1") test1()需要执行的多次源代码；from __main__ import test1 执行一次的“安装”语句。

from timeit import Timer

t1 = Timer("test1()", "from __main__ import test1")
print("concat %f seconds\n" % t1.timeit(number=1000))

t2 = Timer("test2()", "from __main__ import test2")
print("concat %f seconds\n" % t2.timeit(number=1000))

t3 = Timer("test3()", "from __main__ import test3")
print("concat %f seconds\n" % t3.timeit(number=1000))

t4 = Timer("test4()", "from __main__ import test4")
print("concat %f seconds\n" % t4.timeit(number=1000))

性能最优的方式range函数调用再转成列表，其次列表推导式

List操作比较大O()数量级

我们注意到pop这个操作：
pop()从末尾移除元素 O(1)
pop(i)从列表中部移除元素· O(n)
原因在于python所选择的实现方法
从中部移除元素的话，要把移除元素后面的元素全部向前挪位复制一边，这个看起来有点笨拙，但这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O（1）
这也是一种对常用和不常用操作的折衷方案

# list.pop的计时实验
# 为了验证表中的大O数量级，我们把两种情况下的pop操作来实际计时对比
# 相对同一个大小的List，分别调用pop()和pop(0)
# 对比不同大小的List做计时时，期望的结果是pop()的时间不随list大小变化，pop(0)的时间随list变大和变长。
l1 = list(range(1000))
l2 = list(range(1000))
l3 = list(range(100000))
l4 = list(range(100000))

def test5():
    a = l1.pop()

def test6():
    a = l2.pop(0)

def test7():
    a = l3.pop(0)

def test8():
    a = l4.pop()

t5 = Timer("test5()", "from __main__ import test5")
print("concat %f seconds\n" % t5.timeit(number=1000))
t6 = Timer("test6()", "from __main__ import test6")
print("concat %f seconds\n" % t6.timeit(number=1000))
t7 = Timer("test7()", "from __main__ import test7")
print("concat %f seconds\n" % t7.timeit(number=1000))
t8 = Timer("test8()", "from __main__ import test8")
print("concat %f seconds\n" % t8.timeit(number=1000))

对于相同大小的list,pop()比pop(index)快

list的大小，对pop()的效率没有影响；对pop(index)的效率有影响

对列表来说，按下标赋值、按下标取值的时间复杂度为O(1),比较快，按下标删除元素就会慢
你可以换一种方式，删除比较快，但是按下标取值赋值比较慢。

为什么要用这个方式这样实现呢？为什么要这么设计呢？
数据都存储在内存单元，内存单元都是连续的，内存单元在硬件上都是挨着的。
如何组织一组数据，按下标取值赋值，能达到O(1)的时间复杂度？
内存都是连续的，中间不为空，比如取下标为3的，先找到下标为0的，+3就可以找到下标为3的位置的数，
当数据规模越大，n越大，比如取下标为n的，又是先找到下标为0的，再+n就可以了，就找到下标为n的位置的数
所以找到下标为n的永远只需要找到下标为0的再多做一步就可以了，与数据量规模n无关，所以是O(1)
在这种按下标赋值、取值能达到O(1)的程度,原因在于内存是连续的，中间不为空，但是就是因为内存连续中间不为空，导致按中间位置增加、删除的操作变得耗时，中间增加，数据要往后面挪一位，中间删除，数据要往前挪一位，就是O(n)。所以按下标取值、赋值时要变得很快时，那么按下标插入数据、删除数据就变得很慢。两者矛盾的关系需要权衡取舍。
这种就不适合数据要经常增加删除、变动的时候。

dict 数据类型

字典与列表不同，根据关键码key找到数据项，而列表是根据位置index
最常用的取值get和赋值set，其性能为O(1),另一个重要的操作contains(in)是判断字典中是否存在某个关键码key，这个性能也是O(1)

O(1) 表示它的效率不变，不受长度影响
python 官方的算法复杂度网站
https://wiki.python.org/moin/TimeComplexity

字典in的时间复杂度为什么是O(1)?
字典是一种特殊的数据结构Hash table，

字典其实是集合类型的扩充,集合就是简版的字典，集合只有key，没有value,字典里的value是附带的。
in就是判断这个key有没有在字典，不是判断value有没有在这个字典里。

为什么是O(1)呢？

比如说看b这个key是不是在这个字典里，b经过函数计算是1，所以b放在1的内存地址里，为1的内存地址也只会放b,（因为哈希函数是对应的关系）可以直接看内存地址为1的地方有没有值就可以了。所以时间效率是O(1)。
如果看n这个key是不是在这个字典里，直接找n经过哈希函数计算的值的内存地址有没有存储东西就行，所以时间效率是O(1)，不会随着数据规模n变大而变大。

缺点：浪费存储空间，存储的东西不是连续的挨在一起排，才能这么实现。