初学python之以时间复杂度去理解列表常见使用方法

 

列表list,一个有序的队列

列表内的个体为元素,由若干个元素按照顺序进行排列,列表是可变化的,也就是说可以增删

 

list定义

常用的列表定义方式: 使用[] 或者 a = list()

取数列表可以用range()

 

 

列表查询方法

index

index = 索引,以0开始查找

方法:value,[start,[stop]]

通过对应位置的索引进行查找,找到列表内的元素是否有匹配,如有则返回索引值

匹配到第一个元素则立即返回索引位

有时候从右边查找更加便利,比如反斜杠/ 从右边找更加便捷

 

例:

 

In [22]: a

Out[22]: [1, 2, 3, 5, 10, 20, 33, 55]

 

In [23]: a.index(3)

Out[23]: 2

 

In [24]: a.index(33)

Out[24]: 6

 

从右向左查找 index(value, [start, [stop]]) 

 

从某个值开始查找

 

In [46]: a.index(33,3)

Out[46]: 6

 

In [50]:a.index(55,-1)

Out[50]: 7

 

计算元素出现的次数

 

In [53]: a = [1,1,1,3,2,11,5,43,1,1]

In [54]: a.count(1)

Out[54]: 5

 

 

时间复杂度

     计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况

 

index 和count 方法对应的时间复杂度

数学符号对应 O

O(n)

O(2)

O(1)

 

n表示多少个元素,意思为有多少个元素就从前到后多少个元素

将所有的元素都遍历一遍

 

需要考虑index方法和count方法适用性,是否该用,选型哪个需要考虑

随着列表数据规模增加而效率下降,如果能做到O1/2/3 这样则可以很快返回结果

 

 

list列表元素修改

对某一项索引位置赋值(修改)

 

In [59]: a

Out[59]: [1, 1, 1, 3, 2, 11, 5, 43, 1, 1]

In [60]: a[1] = 2

In [61]: a

Out[61]: [1, 2, 1, 3, 2, 11, 5, 43, 1, 1]

 

列表就地修改

对列表本身进行追加元素

 

lst.append(100)

[1, 2, 3, 2, 2, 5, 6, 100]

 

append 对list进行增加元素,返回一个None

 

In [71]: lst = [1,2,3,2,2,5,6]

 

In [72]: a = lst.append(100)

 

In [73]: type(a)

Out[73]: NoneType

 

In [74]: a

 

In [75]: print(a)

None

 

这里返回值为空

 

list运算

 

In [77]: a = [1,2,3]

 

In [78]: a * 3

Out[78]: [1, 2, 3, 1, 2, 3, 1, 2, 3]

这里有返回打印

有输出则是没有被就地修改,都是构造新的列表

我们看到增加之后原列表发生了变化,这样被称为就地修改,就地修改为只对当前列表进行修改,修改的是对象的本身

 

append对时间复杂度为O(1),因为通过索引进行修改,而且是从尾部进行修改

这样通过索引线性修改所耗时间很快,并非O(n) ,O(n)为逐步遍历,找到某个项再进行修改

 

 

insert 插入元素

In [81]: a.insert(1,'a')

In [82]: a

Out[82]: [1, 'a', 2, 3]

 

insert 为在指定处插入对象,这样会引起整个内存结构变化,所有数据统一向后错位,如果量级大则不要去做,尽可能new一个

所以尽可能避免挪动

insert时间复杂度为 O(n),如果放在开头则不建议,一般list规模很大,所以要考虑效率问题

所以,insert更适合链表方式

 

 

extend 将迭代对象追加

迭代对象不用解释了,可以是列表,可以是字典等等

 

b = {'c':123}

In [85]: a.extend(b)

In [86]: a

Out[86]: [1, 'a', 2, 3, 'c']

 

追加迭代自己

 

In [88]: a.extend(a)

 

In [89]: a

Out[89]: [1, 'a', 2, 3, 'c', 1, 'a', 2, 3,'c']

 

remove 删除某个元素

remove 为删除某个内容,而并非索引

remove 为就地修改,在做位置的挪动,所以这里需要注重效率

In [89]: a

Out[89]: [1, 'a', 2, 3, 'c', 1, 'a', 2, 3,'c']

 

In [90]: a.remove(1)

 

In [91]: a

Out[91]: ['a', 2, 3, 'c', 1, 'a', 2, 3,'c']

 

In [92]: a.remove(1)

 

In [93]: a

Out[93]: ['a', 2, 3, 'c', 'a', 2, 3, 'c']

在顺序列表中,在中间包括开头,需要考虑效率问题

 

 

pop 弹出

从尾部进行弹出并且删除尾部的元素

In [103]: a = [1,2,3,11,13,12,20]

 

In [104]: a.pop()

Out[104]: 20

 

pop效率为O(1) 由于是在尾部进行就地修改,所以效率非常高

 

使用index进行pop,而索引则是从1开始并非是0

 

In [108]: a.pop(0)

Out[108]: 1

 

In [109]: a

Out[109]: [2, 3, 11, 13, 12]

 

pop的特性直接将前端显示,移除+修改并行操作

在清除对象过多的情况下,会引起大规模GC垃圾回收,同样要考虑到效率问题

 

 

list的排序

sort() 排序

 

In [113]: a = [63,1,44,2,19,94,64,21]

In [114]: a.sort()

In [115]: a

Out[115]: [1, 2, 19, 21, 44, 63, 64, 94]

 

reverse进行到排序

默认为: sort(Key=None,reverse=False)

默认情况下是升序排列,降序由大到小,那么进行到排序:

In [116]: a.sort(reverse=True)

 

In [117]: a

Out[117]: [94, 64, 63, 44, 21, 19, 2, 1]

 

但是当前如果遇到字符串则无法进行

In [117]: a

Out[117]: [94, 64, 63, 44, 21, 19, 2, 1]

 

In [118]: a.append('haha')

 

In [119]: a.sort(reverse=False)

---------------------------------------------------------------------------

TypeError                               Traceback (most recent call last)

<ipython-input-119-83555bcb738d> in<module>()

----> 1 a.sort(reverse=False)

 

TypeError: unorderable types: str() <int()

 

那么我们可以使用key=None 的方法进行对字符串排序

 

In [121]: a.sort(key=str)

 

In [122]: a

Out[122]: [1, 19, 2, 21, 44, 63, 64, 94,'haha']

 

In [123]: a.sort(key=str,reverse=True)

 

In [124]: a

Out[124]: ['haha', 94, 64, 63, 44, 21, 2,19, 1]

同样可以按照字母进行正排倒排

In [125]: a.append('ab')

 

In [126]: a.append('ba')

 

In [127]: a.sort(key=str,reverse=True)

 

In [128]: a

Out[128]: ['haha', 'ba', 'ab', 94, 64, 63,44, 21, 2, 19, 1]

 

In [129]: a.sort(key=str)

 

In [130]: a

Out[130]: [1, 19, 2, 21, 44, 63, 64, 94,'ab', 'ba', 'haha']

 

排序规则:将每个元素转为字符串,其都是直接转为ASCII码进行排序,这里的str为当前定义的函数,如果是自己写的函数可以自定义排序规则

 

 

取随机数

涉及random

choice 从非空序列的元素中随机选择

 

In [167]: a

Out[167]: [1, 19, 2, 21, 44, 63, 64, 94,'ab', 'ba', 'haha']

 

In [168]: import random

 

In [169]: random.choice(a)

Out[169]: 1

 

In [170]: random.choice(a)

Out[170]: 64

 

randrange取之间的随机数的,以及步长

 

In [172]: random.randrange(1,10)

Out[172]: 5

 

shuffle 打乱元素

In [174]: random.shuffle(a)

 

In [175]: a

Out[175]: [94, 64, 'ba', 21, 44, 19, 63, 2,1, 'ab', 'haha']

 

 

 

列表复制

== 和is 的区别

In [131]: lst0 = list(range(4))

 

In [132]: lst0

Out[132]: [0, 1, 2, 3]

 

In [133]: id(lst0)

Out[133]: 140196597896584

首先进行哈希匹配

 

In [134]: hash(id(lst0))

Out[134]: 140196597896584

 

给lst1 进行赋值 让其等于lst0

In [135]: lst1 = list(range(4))

 

In [136]: id(lst1)

Out[136]: 140196608816840

查看两个列表的值

In [138]: lst1

Out[138]: [0, 1, 2, 3]

 

In [139]: lst0

Out[139]: [0, 1, 2, 3]

 

In [140]: lst0 == lst1

Out[140]: True

 

In [141]: lst0 is lst1

Out[141]: False

 

通过以上,可以明白:

  ==   比较返回值 判断是否依次相等

  is   比较内存地址是否一致

 

地址空间的引用

In [142]: id(lst0[1])

Out[142]: 9177888

 

In [143]: id(lst1[1])

Out[143]: 9177888

 

以上看到,是没有复制的过程,而是被引用了同样的内存地址空间

 

使用copy进行复制并返回一个新的列表

 

In [150]: lst0

Out[150]: [0, 1, 2, 3]

 

In [151]: lst5=lst0.copy()

 

In [152]: lst5

Out[152]: [0, 1, 2, 3]

 

使用= 进行拷贝

 

In [163]: lst5 = lst0

 

In [164]: lst0[1] = 555

 

In [165]: lst0

Out[165]: [0, 555, 2, 3]

 

In [166]: lst5

Out[166]: [0, 555, 2, 3]

 

因为赋值的是引用类型,所以直接将嵌套的list拷贝的内存地址

通过这个内存地址修改,则对两个list同时修改

 

需要注意的是:需要观察拷贝的类型是什么,不然会引起副作用,但是也可以通过特性批量进行操作

 

深拷贝和潜拷贝的基本概念

浅拷贝

     在一般都是实现了浅拷贝,只拷贝了第一层结构,

     被称为 shadow copy,但是引用的都是同一个内存地址

 

深拷贝

如果出现层次嵌套,会对引用类型进行深入拷贝,在结构上拷贝的一模一样,引用的内存地址则独立开辟

使用deepcopy可以进行深拷贝

 

 

使用list求100内的质数:

 

lst1 = []

 

for x in range(2,101):

    for i in lst1:

        if x % i == 0:

           break

    else:                   

        lst1.append(x)

 

print(lst1)

 


本文转自zuzhou 51CTO博客,原文链接:http://blog.51cto.com/yijiu/1966783

上一篇:03 EM算法 - EM算法流程和直观案例


下一篇:初识解释器