点击小眼睛开启蜘蛛网特效

常见的Python知识点汇总(一)

《常见的Python知识点汇总(一)》

部分内容收集于网络~

dict 字典

python中的字典的实现也是一个散列表。是key-value结构。

  • Python的dict和set为什么是无序的?
  • 为什么不是所有的python对象都可以用作dict的键和set中的元素

要弄懂上面的问题,我们首先要了解Python内部是如何实现dict和set类型的。我们先来看看dict的内部结构,dict其实本质上是一个散列表(散列表即总有空白元素的数组,Python会保证至少有三分之一的数组元素是空的),dict的每个键都占用一个表元,而一个表元中又分为两个部分,分别是对键的引用和对值的引用。

当我们存放一个对象的时候,首先会要计算这个元素的散列值,python中使用hash()方法来实现的,这也就回答了第二个问题,因为不是所有的python对象都可以使用hash来获取散列值,获取不到散列值也就不可能存放到dict中,所以只有可hash的对象才能够作为dict的键。值得注意的是内置的hash方法可以用于所有的内置类型对象的,所有用户自定义的对象默认都是可以作为键的,因为自定义对象的散列值是通过id()来获取的。例如:

class T(object):
    pass

t = T()

print(id(t))
d = {t: 1}
print(d)

###  2133693018240
###  {<__main__.T object at 0x000001F0CA03B080>: 1}

假设我们已经获取到了元素的散列值,接下来就该计算应当存放位置了,将散列值对数组长度进行取余,得到的结果就是存放位置的索引了。但是不同的key可能会得到相同的散列值,也就是哈希冲突的问题,python内部是使用开放寻址的方法来解决的,开放寻址法就不在此详细说了。

关于为什么dict是无序的,这个是因为python内部会保证散列表至少有三分之一的位置为空,当我们增加元素的时候,python有可能会对散列表进行扩容,具体操作就是重新开辟一块更大的空间,将原有的元素添加到新表里面,这个过程中可能又会发生新的散列冲突,导致新的散列表中的键的次序发生变化。当然呢如果想要保存顺序也可以使用OrderedDict来处理.

dict的操作时间复杂度:

  • 获取:O(1)
  • 修改:O(1)
  • 删除:O(1)
  • 搜索:O(1)
  • 迭代:O(n)
  • 复制:O(n)

set集合和dict一样也是基于散列表的,只是他的表元只包含值的引用而没有对键的引用,其他的和dict基本上是一致的,所以在此就不再多说了。

list和tuple

List和tuple中可以存放不同类型的元素,并且互相转化很简单,直接关键词上就可以。

https://www.cnblogs.com/webary/p/5187217.html

这两个的底层实现都是线性表,线性表又分两类:

  • 顺序表:将表元素直接顺序的放在一块划分的连续存储区内,所以元素的顺序关系由存储顺序自然表示。
  • 链接表:将表元素放在通过链接构造起来的系列存储块里。两种模型各有长短。

提到python中list和tuple的底层实现,就要回到最基本的数据结构——线性表。

把一组数据元素,通常它们还是同一类型,看成一个序列,序列里的位置和顺序都代表着有意义的信息或者关系,把这样的数据序列就是线性表。线性表(表)应用非常广泛,是复杂结构的实现基础。

线性表中的线性,来源于每个元素的上下文环境是顺序衔接的,即除首元素之外,表中每个元素仅有一个前驱元素;除末尾元素之外,每个元素都仅有一个后继元素。所以称之为线性表。

如何组织线性表里的数据,并且为之配置高效的操作方法是线性表实现的关键。
这里要考虑两个方面:

  • 1.保存元素数据信息和元素顺序信息要适应计算机内存的管理,
  • 2.考虑重要操作的实现效率,如定位访问更改和删除,元素遍历等操作。

所以提出两种表的基本模型。

  • 1.顺序表:将表元素直接顺序的放在一块划分的连续存储区内,所以元素的顺序关系由存储顺序自然表示。
  • 2.链接表:将表元素放在通过链接构造起来的系列存储块里。两种模型各有长短。

下面主要看顺序表

顺序表的基本实现方式十分简单。通常元素类型相同,故每个元素的存储量相同,等距安排同等大小的存储单元顺序存储元素数据即可,直接映射到内存里。表中任何元素的位置计算都很简单,只要知道了第一个元素的内存位置,+逻辑地址(表内元素索引0,1,2,。。。)单个元素的存储单元数目即可,故索引操作和元素访问是O(1)时间。

然而表元素大小差异巨大,所需的存储单元不一致的话,内存没法安排统一的线性顺序。只需将实际元素数据存储在另外的存储区,在顺序表原来的内存单元里保存每个元素数据的label(标识,即引用信息,在独立存储区的地址链接,实现对元素的间接访问),由于地址链接的大小肯定是一致的,所以依然保持了内存的顺序性映射。这样的结构又叫索引结构。

这里注意外部对表每一步操作后,存储块的容量(max)和当前元素个数(num)必须要实时记录,当做附加数据信息,以支持各种操作。直接访问元素显然是O(1)时间,按下标循环并检查和处理的话,O(n)时间复杂度。
尤其注意的是变动操作中的保序问题,尾部操作和定点位置的操作的差别。
在表尾部操作显然简单,判断表没满(max>num),就可以根据num直接找到尾部,执行操作。如果在其他指定位置如i,加入新元素,i这个位置被新元素占了,原来i位置的元素直接移到到末尾num处,这种就是非保序操作,O(1)时间,变动操作后,元素的顺序与原来顺序不要求一致。若要求保住原有的元素顺序,就要将原来的i位置元素后移到i+1位置,原来i+1位置元素后移到i+2,后续元素均要顺移,受元素个数影响,保序操作最坏和平均时间都是O(n)。删除操作情况类似。

总结顺序表:

  • 优点在于O(1)时间直接按位置访问元素,元素存储紧凑,除表元素外,存储区外只需要O(1)空间存放少量辅助信息(max和num)。
  • 缺点:表一旦大,需要的连续内存空间就很大。存储块划分之后,不可更新,造成闲置浪费。加入删除操作要移动很多元素,效率低。

一个顺序表包括两部分信息,一个是元素数据的集合,一个是前面的实现操作的记录辅助信息(max和num)。这样就可以采用一体式和分离式结构。分离式结构将max,num,链接信息(元素实际存放的内存地址)放一起,内存中元素存储区与他们分开存储。一体式顾名思义。

终于要考虑表存储区的容量大小问题了。存储区满了之后,肯定要分配更大的存储区去替代。一体式结构就在这里失效了。又引入分离式技术,不改变表的标识,另外申请更大的存储区,然后把已有的元素复制到新存储区,更新存储链接,就可以继续加新元素。这样可扩充容量的表就是动态顺序表。

对于动态顺序表,前端插入和定位插入,每一次操作都与长度有关,如果表规模从0增长到n,整个增长过程插入的时间就为O(n2)。

后端插入(O(1)),再考虑容量更新的问题。涉及到空闲内存单元的量和更替存储区的频度问题。一种策略是线性增长,比如,每次替换存储区时加10个存储单元,那么假设从0容量到1000,每加10个元素,换一次存储执行一次元素复制,总复制次数=10+20+30+。。。990=49500,考虑增长到n容量(n次后端插入),就有1/20×n2次复制。虽然每次尾端插入为O(1)时间,但一次插入操作的平均代价变成了O(n),并不理想。

另外一种方式为加倍策略。每次存储量更新时翻倍,考虑容量从0增加到1024,复制次数为1+2+4+。。。512=1023. 对于容量n,表从0到n的整个增长过程,执行尾端插入,存储区每次更新加倍,元素复制次数也是O(n),插入操作的平均时间变成了O(1)。比前者具有优势。但实际上也是以空间换时间。

至此,回顾python的list和tuple,均采用了顺序表的结构。Tuple不支持改变内部状态的操作,看可更新的List。

List的下表索引和更新高效,为O(1),且元素有序,只能采用连续表,元素数据保存在连续的存储区里,且删除,插入是要求保序的,尾部插入O(1),定位插入O(n),n为长度;list可以不断加入新元素,且对象标识(用内置id函数可以看其内存地址)不变,可以看出使用了分离式存储技术,是动态顺序表,存储区可扩充替换。
根据python的documentation,List存储区的扩充实际采用以下原则:空表分配8个元素的存储区,插入(append,insert等)元素满了之后,换4倍大的存储区(未超出50000),若表非常大了(元素超过50000个),换存储区时容量加倍。

综上,python的list采用的是连续存储的分离式结构的动态顺序表,且插入和删除要求保序。使用时,一定要考虑尾端插入和定位插入的效率差异。

python传值

python不允许程序员选择采用传值还是传引用。Python参数传递采用的肯定是“传对象引用”的方式。这种方式相当于传值和传引用的一种综合。如果函数收到的是一个可变对象(比如字典或者列表)的引用,就能修改对象的原始值--相当于通过“传引用”来传递对象。如果函数收到的是一个不可变对象(比如数字、字符或者元组)的引用,就不能直接修改原始对象--相当于通过“传值’来传递对象。

一些函数使用方法

sort

>>>l=[('a', 1), ('b', 2), ('c', 6), ('d', 4), ('e', 3)]
>>>sorted(l, key=lambda x:x[0])
Out[39]: [('a', 1), ('b', 2), ('c', 6), ('d', 4), ('e', 3)]
>>>sorted(l, key=lambda x:x[0], reverse=True)
Out[40]: [('e', 3), ('d', 4), ('c', 6), ('b', 2), ('a', 1)]
>>>sorted(l, key=lambda x:x[1])
Out[41]: [('a', 1), ('b', 2), ('e', 3), ('d', 4), ('c', 6)]
>>>sorted(l, key=lambda x:x[1], reverse=True)
Out[42]: [('c', 6), ('d', 4), ('e', 3), ('b', 2), ('a', 1)]


# 或者使用这个
>>>l.sort(key=lambda x : x[1])
>>>l
Out[45]: [('a', 1), ('b', 2), ('e', 3), ('d', 4), ('c', 6)]
>>>l.sort(key=lambda x : x[1], reverse=True)
>>>l
Out[47]: [('c', 6), ('d', 4), ('e', 3), ('b', 2), ('a', 1)]

classmethod 与 staticmethod

class A(object):

    # 属性默认为类属性(可以给直接被类本身调用)
    num = "类属性"

    # 实例化方法(必须实例化类之后才能被调用)
    def func1(self): # self : 表示实例化类后的地址id
        print("func1")
        print(self)

    # 类方法(不需要实例化类就可以被类本身调用)
    @classmethod
    def func2(cls):  # cls : 表示没用被实例化的类本身
        print("func2")
        print(cls)
        print(cls.num)
        cls().func1()

    # 不传递传递默认self参数的方法(该方法也是可以直接被类调用的,但是这样做不标准)
    def func3():
        print("func3")
        print(A.num) # 属性是可以直接用类本身调用的
    
# A.func1() 这样调用是会报错:因为func1()调用时需要默认传递实例化类后的地址id参数,如果不实例化类是无法调用的
A.func2()
A.func3()

Python的垃圾回收机制

  • 小整数对象池,Python对于[-5,257)这些整数对象都是提前建立好的,不会被垃圾回收。在一个Python的程序中,所有位于这个范围内的整数使用的是同一个对象。
  • intern机制,对于很多重复的对象,例如很多一样的字符串,python会用一个引用机制,只占用一个“HelloWorld”所占的内存对象,靠引用计数去维护何时释放。
  • 单个单词不可修改,默认开启inter机制,共用对象,引用计数为0,则销毁。
  • 引用计数为主,分代回收为辅,其中引用计数类似于C++中的智能指针。实现高效,有实时性,也就是一旦没有了引用,内存就直接释放掉了。每个对象都有其自己的生命周期。

https://www.cnblogs.com/alexzhang92/p/9416692.html

多线程和多进程

https://zhuanlan.zhihu.com/p/50862620

深拷贝和浅拷贝

首先深拷贝和浅拷贝都是对象的拷贝,都会生成一个看起来相同的对象,他们本质的区别是拷贝出来的对象的地址是否和原对象一样,也就是地址的复制还是值的复制的区别。

在浅拷贝时,拷贝出来的新对象的地址和原对象是不一样的,但是新对象里面的可变元素(如列表)的地址和原对象里的可变元素的地址是相同的,也就是说浅拷贝它拷贝的是浅层次的数据结构(不可变元素),对象里的可变元素作为深层次的数据结构并没有被拷贝到新地址里面去,而是和原对象里的可变元素指向同一个地址,所以在新对象或原对象里对这个可变元素做修改时,两个对象是同时改变的,但是深拷贝不会这样,这个是浅拷贝相对于深拷贝最根本的区别。

Composing Programs with python

关于大部分Python的语法,可以看专门介绍一门语言理解的网站-以Python为讲解。

这里只列出比较重要的一些代码,其他的可以看上面的那个网站,重点看:

  • 1.6节-后半部分
  • 2.3节-sequences
def curried_pow(x):
    def h(y):
        return pow(x,y)
    return h

curried_pow(2)(3)
Out[3]: 8

def map_to_range(start, end, f):
    while start < end:
        print(f(start))
        start = start + 1
        
map_to_range(0, 10, curried_pow(2))
1
2
4
8
16
32
64
128
256
512

def curry2(f):
    def g(x):
        def h(y):
            return f(x,y)
        return h
    return g
def uncurry2(g):
    def f(x,y):
        return g(x)(y)
    return f
pow_curried = curry2(pow)

pow_curried(2)(5)
Out[9]: 32

map_to_range(0, 10, pow_curried(2))
1
2
4
8
16
32
64
128
256
512

uncurry2(pow_curried)(2,5)
Out[11]: 32

相关讲解:

python3与python2的区别

python2和python3的区别,主要集中在,print, raw_input, xrange, 整除除法这些区别上。

  点赞
本篇文章采用 署名-非商业性使用-禁止演绎 4.0 国际 进行许可
转载请务必注明来源: https://oldpan.me/archives/common-python-knowledge-1

   关注Oldpan博客微信公众号,你最需要的及时推送给你。


发表评论

电子邮件地址不会被公开。 必填项已用*标注

评论审核已启用。您的评论可能需要一段时间后才能被显示。