标签搜索
搜索到
36
篇与
转载文章
的结果
-
哈夫曼树（最优二叉树）的概念以及构造 哈夫曼树产生的背景在实际生活和生产应用中，我们往往会遇到综合比较一系列的离散量的问题；比如说车站根据包裹的重量以及旅途的长短来确定携带行李的价格，或者我们根据一定的重量范围来给一箱铁球进行分类。这一类问题的解决思路是：1、 根据实际需要划分出分类的标准；2、 按一定的顺序（算法）将实际的数据归到相应的类别里。一般情况下，我们所确定的分类标准并不能保证每一类的数据量是平均分配的；也就是说，由于每一类数据出现的概率不同，造成当采用不同的算法时所需的运算次数的不同。当然，在实际生产生活中，我们更希望得到一种最快，最简洁同时也不会产生歧义的算法。在这个背景下，哈夫曼树以及哈夫曼算法应运而生。准备概念森林：森林由n(n>=2)个二叉树组成，它的遍历可以归结为二叉树的遍历，即以其中一棵二叉树的根结点为森林的“根结点”，之后每一个二叉树的根结点都依次相连，由此组成了一个大的二叉树——森林向二叉树的转化。路径和路径的长度：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。对于一个二叉树，其在第n层上的结点到根结点的路径长度为n-1。结点的权：根据应用的需要给树的结点赋的权值。结点的带权路径长度：从根结点到该结点的路径长度与该几点权的乘积。树的带权路径长度（WPL）：树中所有叶子的带权路径长度之和。哈夫曼二叉树及其构造有了以上的概念，哈夫曼二叉树的定义就变得水到渠成。所谓哈夫曼二叉树（最优二叉树），就是带权路径长度最小的二叉树（注意这里的带权路径）。因为树的带权路径长度只与所有叶子的带权路径长度有关，所以对于一个哈夫曼树，其真正其作用的数据是存在于叶子上。再回到问题产生的根源。我们说在现实的分类中，每一类数据出现的概率不尽相同；这些数据出现的概率可以被看做哈夫曼树中叶子的权值。为了获取最短的路径，也就是带权路径长度最短的二叉树，我们希望那些权值低的数据拥有相对较长的对根结点的路径长度。根据这一思路，我们可以从一群离散的数据中构造出一颗哈夫曼树，具体的算法如下：根据给定的n个权值{w1 ,w2 ,...,wn }构造n棵二叉树的集合F={T1 ,T2 ,...,Tn }，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根 结点的权值为其左、右子树上根结点的权值之 和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复2和3，直到F中只含一棵树为止。这棵树便是最优二叉树。例如，有权值分别为 5、10、15、20、25、40的结点，根据以上算法构造出一个哈夫曼树。取这六个树中最小的两个树5、10连成一个二叉树，其权值为15；此时森林里的树变为15（5、10）、15、20、25、40。取这五个树中最小的两个树（15（5、10）、15），构成一个新的二叉树30（（5、10）、15）；此时森立里的树变为20、25、30（（5、10）、15）、40。继续上述过程，得到一个新的二叉树45（20、25）；此时的森林变为30（（5、10）、15）、40、45（20、25）。继续得到二叉树70（（5、10）、15）、40）；则森林里只剩下两棵树：70（（5、10）、15）、40）与45（20、25）。最后将这两棵二叉树合并成为一棵二叉树115（（（5、10）、15）、40）、（20、25）），完成了哈夫曼树的构造。计算WPL=(5+10)4+153+402+(20+25)2=275。以上便是哈夫曼树（最优二叉树）的相关概念和构造方法。根据最后二叉树可以解决类似于文章开头提到的一些实际问题。同时还另外引申出了哈夫曼编码——即不等长编码，实现数据总长度的最优化。 -
利用js去除无限debugger csdn看见的，还别说，挺好用//去除无限debugger Function.prototype.__constructor_back = Function.prototype.constructor ; Function.prototype.constructor = function() { if(arguments && typeof arguments[0]==='string'){ //alert("new function: "+ arguments[0]); if( "debugger" === arguments[0]){ //arguments[0]="consoLe.Log(\"anti debugger\");"; //arguments[0]=";"; return } } return Function.prototype.__constructor_back.apply(this,arguments); }原文链接：https://blog.csdn.net/qq_39799322/article/details/119275806
-
-
关于Python的面试题 Python语言特性1 Python的函数参数传递看两个例子:a = 1 def fun(a): a = 2 fun(a) print a # 1a = [] def fun(a): a.append(1) fun(a) print a # [1]所有的变量都可以理解是内存中一个对象的“引用”，或者，也可以看似c中void*的感觉。通过id来看引用a的内存地址可以比较理解：a = 1 def fun(a): print "func_in",id(a) # func_in 41322472 a = 2 print "re-point",id(a), id(2) # re-point 41322448 41322448 print "func_out",id(a), id(1) # func_out 41322472 41322472 fun(a) print a # 1注：具体的值在不同电脑上运行时可能不同。可以看到，在执行完a = 2之后，a引用中保存的值，即内存地址发生变化，由原来1对象的所在的地址变成了2这个实体对象的内存地址。而第2个例子a引用保存的内存值就不会发生变化：a = [] def fun(a): print "func_in",id(a) # func_in 53629256 a.append(1) print "func_out",id(a) # func_out 53629256 fun(a) print a # [1]这里记住的是类型是属于对象的，而不是变量。而对象有两种,“可更改”（mutable）与“不可更改”（immutable）对象。在python中，strings, tuples, 和numbers是不可更改的对象，而 list, dict, set 等则是可以修改的对象。(这就是这个问题的重点)当一个引用传递给函数的时候,函数自动复制一份引用,这个函数里的引用和外边的引用没有半毛关系了.所以第一个例子里函数把引用指向了一个不可变对象,当函数返回的时候,外面的引用没半毛感觉.而第二个例子就不一样了,函数内的引用指向的是可变对象,对它的操作就和定位了指针地址一样,在内存里进行修改.如果还不明白的话,这里有更好的解释: http://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference2 Python中的元类(metaclass)这个非常的不常用,但是像ORM这种复杂的结构还是会需要的,详情请看:http://stackoverflow.com/questions/100003/what-is-a-metaclass-in-python3 @[email protected],即静态方法(staticmethod),类方法(classmethod)和实例方法,如下:def foo(x): print "executing foo(%s)"%(x) class A(object): def foo(self,x): print "executing foo(%s,%s)"%(self,x) @classmethod def class_foo(cls,x): print "executing class_foo(%s,%s)"%(cls,x) @staticmethod def static_foo(x): print "executing static_foo(%s)"%x a=A() 这里先理解下函数参数里面的self和cls.这个self和cls是对类或者实例的绑定,对于一般的函数来说我们可以这么调用foo(x),这个函数就是最常用的,它的工作跟任何东西(类,实例)无关.对于实例方法,我们知道在类里每次定义方法的时候都需要绑定这个实例,就是foo(self, x),为什么要这么做呢?因为实例方法的调用离不开实例,我们需要把实例自己传给函数,调用的时候是这样的a.foo(x)(其实是foo(a, x)).类方法一样,只不过它传递的是类而不是实例,A.class_foo(x).注意这里的self和cls可以替换别的参数,但是python的约定是这俩,还是不要改的好.对于静态方法其实和普通的方法一样,不需要对谁进行绑定,唯一的区别是调用的时候需要使用a.static_foo(x)或者A.static_foo(x)来调用.\实例方法类方法静态方法a = A()a.foo(x)a.class_foo(x)a.static_foo(x)A不可用A.class_foo(x)A.static_foo(x)更多关于这个问题:http://stackoverflow.com/questions/136097/what-is-the-difference-between-staticmethod-and-classmethod-in-pythonhttps://realpython.com/blog/python/instance-class-and-static-methods-demystified/4 类变量和实例变量类变量： 是可在类的所有实例之间共享的值（也就是说，它们不是单独分配给每个实例的）。例如下例中，num_of_instance 就是类变量，用于跟踪存在着多少个Test 的实例。实例变量：实例化之后，每个实例单独拥有的变量。class Test(object): num_of_instance = 0 def __init__(self, name): self.name = name Test.num_of_instance += 1 if __name__ == '__main__': print Test.num_of_instance # 0 t1 = Test('jack') print Test.num_of_instance # 1 t2 = Test('lucy') print t1.name , t1.num_of_instance # jack 2 print t2.name , t2.num_of_instance # lucy 2补充的例子class Person: name="aaa" p1=Person() p2=Person() p1.name="bbb" print p1.name # bbb print p2.name # aaa print Person.name # aaa这里p1.name="bbb"是实例调用了类变量,这其实和上面第一个问题一样,就是函数传参的问题,p1.name一开始是指向的类变量name="aaa",但是在实例的作用域里把类变量的引用改变了,就变成了一个实例变量,self.name不再引用Person的类变量name了.可以看看下面的例子:class Person: name=[] p1=Person() p2=Person() p1.name.append(1) print p1.name # [1] print p2.name # [1] print Person.name # [1]参考:http://stackoverflow.com/questions/6470428/catch-multiple-exceptions-in-one-line-except-block5 Python自省这个也是python彪悍的特性.自省就是面向对象的语言所写的程序在运行时,所能知道对象的类型.简单一句就是运行时能够获得对象的类型.比如type(),dir(),getattr(),hasattr(),isinstance().a = [1,2,3] b = {'a':1,'b':2,'c':3} c = True print type(a),type(b),type(c) # <type 'list'> <type 'dict'> <type 'bool'> print isinstance(a,list) # True6 字典推导式可能你见过列表推导时,却没有见过字典推导式,在2.7中才加入的:d = {key: value for (key, value) in iterable}7 Python中单下划线和双下划线>>> class MyClass(): ... def __init__(self): ... self.__superprivate = "Hello" ... self._semiprivate = ", world!" ... >>> mc = MyClass() >>> print mc.__superprivate Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: myClass instance has no attribute '__superprivate' >>> print mc._semiprivate , world! >>> print mc.__dict__ {'_MyClass__superprivate': 'Hello', '_semiprivate': ', world!'}__foo__:一种约定,Python内部的名字,用来区别其他用户自定义的命名,以防冲突，就是例如__init__(),__del__(),__call__()这些特殊方法_foo:一种约定,用来指定变量私有.程序员用来指定私有变量的一种方式.不能用from module import * 导入，其他方面和公有一样访问；__foo:这个有真正的意义:解析器用_classname__foo来代替这个名字,以区别和其他类相同的命名,它无法直接像公有成员一样随便访问,通过对象名._类名__xxx这样的方式可以访问.详情见:http://stackoverflow.com/questions/1301346/the-meaning-of-a-single-and-a-double-underscore-before-an-object-name-in-python或者: http://www.zhihu.com/question/197549418 字符串格式化:%和.format.format在许多方面看起来更便利.对于%最烦人的是它无法同时传递一个变量和元组.你可能会想下面的代码不会有什么问题:"hi there %s" % name但是,如果name恰好是(1,2,3),它将会抛出一个TypeError异常.为了保证它总是正确的,你必须这样做:"hi there %s" % (name,) # 提供一个单元素的数组而不是一个参数但是有点丑..format就没有这些问题.你给的第二个问题也是这样,.format好看多了.你为什么不用它?不知道它(在读这个之前)为了和Python2.5兼容(譬如logging库建议使用%(issue #4))http://stackoverflow.com/questions/5082452/python-string-formatting-vs-format9 迭代器和生成器这个是stackoverflow里python排名第一的问题,值得一看: http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python这是中文版: http://taizilongxu.gitbooks.io/stackoverflow-about-python/content/1/README.html这里有个关于生成器的创建问题面试官有考：问： 将列表生成式中[]改成() 之后数据结构是否改变？ 答案：是，从列表变为生成器>>> L = [x*x for x in range(10)] >>> L [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] >>> g = (x*x for x in range(10)) >>> g <generator object <genexpr> at 0x0000028F8B774200>通过列表生成式，可以直接创建一个列表。但是，受到内存限制，列表容量肯定是有限的。而且，创建一个包含百万元素的列表，不仅是占用很大的内存空间，如：我们只需要访问前面的几个元素，后面大部分元素所占的空间都是浪费的。因此，没有必要创建完整的列表（节省大量内存空间）。在Python中，我们可以采用生成器：边循环，边计算的机制—>generator10 *args and **kwargs用*args和**kwargs只是为了方便并没有强制使用它们.当你不确定你的函数里将要传递多少参数时你可以用*args.例如,它可以传递任意数量的参数:>>> def print_everything(*args): for count, thing in enumerate(args): ... print '{0}. {1}'.format(count, thing) ... >>> print_everything('apple', 'banana', 'cabbage') 0. apple 1. banana 2. cabbage相似的,**kwargs允许你使用没有事先定义的参数名:>>> def table_things(**kwargs): ... for name, value in kwargs.items(): ... print '{0} = {1}'.format(name, value) ... >>> table_things(apple = 'fruit', cabbage = 'vegetable') cabbage = vegetable apple = fruit你也可以混着用.命名参数首先获得参数值然后所有的其他参数都传递给*args和**kwargs.命名参数在列表的最前端.例如:def table_things(titlestring, **kwargs)*args和**kwargs可以同时在函数的定义中,但是*args必须在**kwargs前面.当调用函数时你也可以用*和**语法.例如:>>> def print_three_things(a, b, c): ... print 'a = {0}, b = {1}, c = {2}'.format(a,b,c) ... >>> mylist = ['aardvark', 'baboon', 'cat'] >>> print_three_things(*mylist) a = aardvark, b = baboon, c = cat就像你看到的一样,它可以传递列表(或者元组)的每一项并把它们解包.注意必须与它们在函数里的参数相吻合.当然,你也可以在函数定义或者函数调用时用*.http://stackoverflow.com/questions/3394835/args-and-kwargs11 面向切面编程AOP和装饰器这个AOP一听起来有点懵,同学面阿里的时候就被问懵了...装饰器是一个很著名的设计模式，经常被用于有切面需求的场景，较为经典的有插入日志、性能测试、事务处理等。装饰器是解决这类问题的绝佳设计，有了装饰器，我们就可以抽离出大量函数中与函数功能本身无关的雷同代码并继续重用。概括的讲，装饰器的作用就是为已经存在的对象添加额外的功能。这个问题比较大,推荐: http://stackoverflow.com/questions/739654/how-can-i-make-a-chain-of-function-decorators-in-python中文: http://taizilongxu.gitbooks.io/stackoverflow-about-python/content/3/README.html12 鸭子类型“当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子，那么这只鸟就可以被称为鸭子。”我们并不关心对象是什么类型，到底是不是鸭子，只关心行为。比如在python中，有很多file-like的东西，比如StringIO,GzipFile,socket。它们有很多相同的方法，我们把它们当作文件使用。又比如list.extend()方法中,我们并不关心它的参数是不是list,只要它是可迭代的,所以它的参数可以是list/tuple/dict/字符串/生成器等.鸭子类型在动态语言中经常使用，非常灵活，使得python不像java那样专门去弄一大堆的设计模式。13 Python中重载引自知乎:http://www.zhihu.com/question/20053359函数重载主要是为了解决两个问题。可变参数类型。可变参数个数。另外，一个基本的设计原则是，仅仅当两个函数除了参数类型和参数个数不同以外，其功能是完全相同的，此时才使用函数重载，如果两个函数的功能其实不同，那么不应当使用重载，而应当使用一个名字不同的函数。好吧，那么对于情况 1 ，函数功能相同，但是参数类型不同，python 如何处理？答案是根本不需要处理，因为 python 可以接受任何类型的参数，如果函数的功能相同，那么不同的参数类型在 python 中很可能是相同的代码，没有必要做成两个不同函数。那么对于情况 2 ，函数功能相同，但参数个数不同，python 如何处理？大家知道，答案就是缺省参数。对那些缺少的参数设定为缺省参数即可解决问题。因为你假设函数功能相同，那么那些缺少的参数终归是需要用的。好了，鉴于情况 1 跟 情况 2 都有了解决方案，python 自然就不需要函数重载了。14 新式类和旧式类这个面试官问了,我说了老半天,不知道他问的真正意图是什么.stackoverflow这篇文章很好的介绍了新式类的特性: http://www.cnblogs.com/btchenguang/archive/2012/09/17/2689146.html新式类很早在2.2就出现了,所以旧式类完全是兼容的问题,Python3里的类全部都是新式类.这里有一个MRO问题可以了解下(新式类继承是根据C3算法,旧式类是深度优先),<Python核心编程>里讲的也很多.一个旧式类的深度优先的例子class A(): def foo1(self): print "A" class B(A): def foo2(self): pass class C(A): def foo1(self): print "C" class D(B, C): pass d = D() d.foo1() # A按照经典类的查找顺序从左到右深度优先的规则，在访问d.foo1()的时候,D这个类是没有的..那么往上查找,先找到B,里面没有,深度优先,访问A,找到了foo1(),所以这时候调用的是A的foo1()，从而导致C重写的foo1()被绕过15 __new__和__init__的区别这个__new__确实很少见到,先做了解吧.__new__是一个静态方法,而__init__是一个实例方法.__new__方法会返回一个创建的实例,而__init__什么都不返回.只有在__new__返回一个cls的实例时后面的__init__才能被调用.当创建一个新实例时调用__new__,初始化一个实例时用__init__.stackoverflowps: __metaclass__是创建类时起作用.所以我们可以分别使用__metaclass__,__new__和__init__来分别在类创建,实例创建和实例初始化的时候做一些小手脚.16 单例模式 单例模式是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问，从而方便对实例个数的控制并节约系统资源。如果希望在系统中某个类的对象只能存在一个，单例模式是最好的解决方案。__new__()在__init__()之前被调用，用于生成实例对象。利用这个方法和类的属性的特点可以实现设计模式的单例模式。单例模式是指创建唯一对象，单例模式设计的类只能实例这个绝对常考啊.绝对要记住1~2个方法,当时面试官是让手写的.1 使用__new__方法class Singleton(object): def __new__(cls, *args, **kw): if not hasattr(cls, '_instance'): orig = super(Singleton, cls) cls._instance = orig.__new__(cls, *args, **kw) return cls._instance class MyClass(Singleton): a = 12 共享属性创建实例时把所有实例的__dict__指向同一个字典,这样它们具有相同的属性和方法. class Borg(object): _state = {} def __new__(cls, *args, **kw): ob = super(Borg, cls).__new__(cls, *args, **kw) ob.__dict__ = cls._state return ob class MyClass2(Borg): a = 13 装饰器版本def singleton(cls): instances = {} def getinstance(*args, **kw): if cls not in instances: instances[cls] = cls(*args, **kw) return instances[cls] return getinstance @singleton class MyClass: ...4 import方法作为python的模块是天然的单例模式# mysingleton.py class My_Singleton(object): def foo(self): pass my_singleton = My_Singleton() # to use from mysingleton import my_singleton my_singleton.foo() 单例模式伯乐在线详细解释17 Python中的作用域Python 中，一个变量的作用域总是由在代码中被赋值的地方所决定的。当 Python 遇到一个变量的话他会按照这样的顺序进行搜索：本地作用域（Local）→当前作用域被嵌入的本地作用域（Enclosing locals）→全局/模块作用域（Global）→内置作用域（Built-in）18 GIL线程全局锁线程全局锁(Global Interpreter Lock),即Python为了保证线程安全而采取的独立线程运行的限制,说白了就是一个核只能在同一时间运行一个线程.对于io密集型任务，python的多线程起到作用，但对于cpu密集型任务，python的多线程几乎占不到任何优势，还有可能因为争夺资源而变慢。见Python 最难的问题解决办法就是多进程和下面的协程(协程也只是单CPU,但是能减小切换代价提升性能).19 协程知乎被问到了,呵呵哒,跪了简单点说协程是进程和线程的升级版,进程和线程都面临着内核态和用户态的切换问题而耗费许多切换时间,而协程就是用户自己控制切换的时机,不再需要陷入系统的内核态.Python里最常见的yield就是协程的思想!可以查看第九个问题.20 闭包闭包(closure)是函数式编程的重要的语法结构。闭包也是一种组织代码的结构，它同样提高了代码的可重复使用性。当一个内嵌函数引用其外部作作用域的变量,我们就会得到一个闭包. 总结一下,创建一个闭包必须满足以下几点:必须有一个内嵌函数内嵌函数必须引用外部函数中的变量外部函数的返回值必须是内嵌函数感觉闭包还是有难度的,几句话是说不明白的,还是查查相关资料.重点是函数运行后并不会被撤销,就像16题的instance字典一样,当函数运行完后,instance并不被销毁,而是继续留在内存空间里.这个功能类似类里的类变量,只不过迁移到了函数上.闭包就像个空心球一样,你知道外面和里面,但你不知道中间是什么样.21 lambda函数其实就是一个匿名函数,为什么叫lambda?因为和后面的函数式编程有关.推荐: 知乎22 Python函数式编程这个需要适当的了解一下吧,毕竟函数式编程在Python中也做了引用.推荐: 酷壳python中函数式编程支持:filter 函数的功能相当于过滤器。调用一个布尔函数bool_func来迭代遍历每个seq中的元素；返回一个使bool_seq返回值为true的元素的序列。>>>a = [1,2,3,4,5,6,7] >>>b = filter(lambda x: x > 5, a) >>>print b >>>[6,7]map函数是对一个序列的每个项依次执行函数，下面是对一个序列每个项都乘以2：>>> a = map(lambda x:x*2,[1,2,3]) >>> list(a) [2, 4, 6]reduce函数是对一个序列的每个项迭代调用函数，下面是求3的阶乘：>>> reduce(lambda x,y:x*y,range(1,4)) 623 Python里的拷贝引用和copy(),deepcopy()的区别import copy a = [1, 2, 3, 4, ['a', 'b']] #原始对象 b = a #赋值，传对象的引用 c = copy.copy(a) #对象拷贝，浅拷贝 d = copy.deepcopy(a) #对象拷贝，深拷贝 a.append(5) #修改对象a a[4].append('c') #修改对象a中的['a', 'b']数组对象 print 'a = ', a print 'b = ', b print 'c = ', c print 'd = ', d 输出结果： a = [1, 2, 3, 4, ['a', 'b', 'c'], 5] b = [1, 2, 3, 4, ['a', 'b', 'c'], 5] c = [1, 2, 3, 4, ['a', 'b', 'c']] d = [1, 2, 3, 4, ['a', 'b']]24 Python垃圾回收机制Python GC主要使用引用计数（reference counting）来跟踪和回收垃圾。在引用计数的基础上，通过“标记-清除”（mark and sweep）解决容器对象可能产生的循环引用问题，通过“分代回收”（generation collection）以空间换时间的方法提高垃圾回收效率。1 引用计数PyObject是每个对象必有的内容，其中ob_refcnt就是做为引用计数。当一个对象有新的引用时，它的ob_refcnt就会增加，当引用它的对象被删除，它的ob_refcnt就会减少.引用计数为0时，该对象生命就结束了。优点:简单实时性缺点:维护引用计数消耗资源循环引用2 标记-清除机制基本思路是先按需分配，等到没有空闲内存的时候从寄存器和程序栈上的引用出发，遍历以对象为节点、以引用为边构成的图，把所有可以访问到的对象打上标记，然后清扫一遍内存空间，把所有没标记的对象释放。3 分代技术分代回收的整体思想是：将系统中的所有内存块根据其存活时间划分为不同的集合，每个集合就成为一个“代”，垃圾收集频率随着“代”的存活时间的增大而减小，存活时间通常利用经过几次垃圾回收来度量。Python默认定义了三代对象集合，索引数越大，对象存活时间越长。举例：当某些内存块M经过了3次垃圾收集的清洗之后还存活时，我们就将内存块M划到一个集合A中去，而新分配的内存都划分到集合B中去。当垃圾收集开始工作时，大多数情况都只对集合B进行垃圾回收，而对集合A进行垃圾回收要隔相当长一段时间后才进行，这就使得垃圾收集机制需要处理的内存少了，效率自然就提高了。在这个过程中，集合B中的某些内存块由于存活时间长而会被转移到集合A中，当然，集合A中实际上也存在一些垃圾，这些垃圾的回收会因为这种分代的机制而被延迟。25 Python的List推荐: http://www.jianshu.com/p/J4U6rR26 Python的isis是对比地址,==是对比值27 read,readline和readlinesread 读取整个文件readline 读取下一行,使用生成器方法readlines 读取整个文件到一个迭代器以供我们遍历28 Python2和3的区别推荐：Python 2.7.x 与 Python 3.x 的主要差异29 super initsuper() lets you avoid referring to the base class explicitly, which can be nice. But the main advantage comes with multiple inheritance, where all sorts of fun stuff can happen. See the standard docs on super if you haven't already.Note that the syntax changed in Python 3.0: you can just say super().__init__() instead of super(ChildB, self).__init__() which IMO is quite a bit nicer.http://stackoverflow.com/questions/576169/understanding-python-super-with-init-methodsPython2.7中的super方法浅见30 range and xrange都在循环时使用，xrange内存性能更好。for i in range(0, 20):for i in xrange(0, 20):What is the difference between range and xrange functions in Python 2.X? range creates a list, so if you do range(1, 10000000) it creates a list in memory with 9999999 elements. xrange is a sequence object that evaluates lazily.http://stackoverflow.com/questions/94935/what-is-the-difference-between-range-and-xrange-functions-in-python-2-x操作系统1 select,poll和epoll其实所有的I/O都是轮询的方法,只不过实现的层面不同罢了.这个问题可能有点深入了,但相信能回答出这个问题是对I/O多路复用有很好的了解了.其中tornado使用的就是epoll的.selec,poll和epoll区别总结基本上select有3个缺点:连接数受限查找配对速度慢数据由内核拷贝到用户态poll改善了第一个缺点epoll改了三个缺点.关于epoll的: http://www.cnblogs.com/my_life/articles/3968782.html2 调度算法先来先服务(FCFS, First Come First Serve)短作业优先(SJF, Shortest Job First)最高优先权调度(Priority Scheduling)时间片轮转(RR, Round Robin)多级反馈队列调度(multilevel feedback queue scheduling)常见的调度算法总结:http://www.jianshu.com/p/6edf8174c1eb实时调度算法:最早截至时间优先 EDF最低松弛度优先 LLF3 死锁原因:竞争资源程序推进顺序不当必要条件:互斥条件请求和保持条件不剥夺条件环路等待条件处理死锁基本方法:预防死锁(摒弃除1以外的条件)避免死锁(银行家算法)检测死锁(资源分配图)解除死锁剥夺资源撤销进程死锁概念处理策略详细介绍:https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/10.html4 程序编译与链接推荐: http://www.ruanyifeng.com/blog/2014/11/compiler.htmlBulid过程可以分解为4个步骤:预处理(Prepressing), 编译(Compilation)、汇编(Assembly)、链接(Linking)以c语言为例:1 预处理预编译过程主要处理那些源文件中的以“#”开始的预编译指令，主要处理规则有：将所有的“#define”删除，并展开所用的宏定义处理所有条件预编译指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”处理“#include”预编译指令，将被包含的文件插入到该编译指令的位置，注：此过程是递归进行的删除所有注释添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或警告时可显示行号保留所有的#pragma编译器指令。2 编译编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。这个过程是整个程序构建的核心部分。3 汇编汇编器是将汇编代码转化成机器可以执行的指令，每一条汇编语句几乎都是一条机器指令。经过编译、链接、汇编输出的文件成为目标文件(Object File)4 链接链接的主要内容就是把各个模块之间相互引用的部分处理好，使各个模块可以正确的拼接。链接的主要过程包块 地址和空间的分配（Address and Storage Allocation）、符号决议(Symbol Resolution)和重定位(Relocation)等步骤。5 静态链接和动态链接静态链接方法：静态链接的时候，载入代码就会把程序会用到的动态代码或动态代码的地址确定下来静态库的链接可以使用静态链接，动态链接库也可以使用这种方法链接导入库动态链接方法：使用这种方式的程序并不在一开始就完成动态链接，而是直到真正调用动态库代码时，载入程序才计算(被调用的那部分)动态代码的逻辑地址，然后等到某个时候，程序又需要调用另外某块动态代码时，载入程序又去计算这部分代码的逻辑地址，所以，这种方式使程序初始化时间较短，但运行期间的性能比不上静态链接的程序6 虚拟内存技术虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储系统.7 分页和分段分页: 用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。分段: 将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。分页与分段的主要区别页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.分页的作业地址空间是一维的.分段的地址空间是二维的.8 页面置换算法最佳置换算法OPT:不可能实现先进先出FIFO最近最久未使用算法LRU:最近一段时间里最久没有使用过的页面予以置换.clock算法9 边沿触发和水平触发边缘触发是指每当状态变化时发生一个 io 事件，条件触发是只要满足条件就发生一个 io 事件数据库1 事务数据库事务(Database Transaction) ，是指作为单个逻辑工作单元执行的一系列操作，要么完全地执行，要么完全地不执行。彻底理解数据库事务: http://www.hollischuang.com/archives/8982 数据库索引推荐: http://tech.meituan.com/mysql-index.htmlMySQL索引背后的数据结构及算法原理聚集索引,非聚集索引,B-Tree,B+Tree,最左前缀原理3 Redis原理Redis是什么？是一个完全开源免费的key-value内存数据库通常被认为是一个数据结构服务器，主要是因为其有着丰富的数据结构 strings、map、 list、sets、 sorted setsRedis数据库 通常局限点来说，Redis也以消息队列的形式存在，作为内嵌的List存在，满足实时的高并发需求。在使用缓存的时候，redis比memcached具有更多的优势，并且支持更多的数据类型，把redis当作一个中间存储系统，用来处理高并发的数据库操作速度快：使用标准C写，所有数据都在内存中完成，读写速度分别达到10万/20万持久化：对数据的更新采用Copy-on-write技术，可以异步地保存到磁盘上，主要有两种策略，一是根据时间，更新次数的快照（save 300 10 ）二是基于语句追加方式(Append-only file，aof)自动操作：对不同数据类型的操作都是自动的，很安全快速的主--从复制，官方提供了一个数据，Slave在21秒即完成了对Amazon网站10G key set的复制。Sharding技术： 很容易将数据分布到多个Redis实例中，数据库的扩展是个永恒的话题，在关系型数据库中，主要是以添加硬件、以分区为主要技术形式的纵向扩展解决了很多的应用场景，但随着web2.0、移动互联网、云计算等应用的兴起，这种扩展模式已经不太适合了，所以近年来，像采用主从配置、数据库复制形式的，Sharding这种技术把负载分布到多个特理节点上去的横向扩展方式用处越来越多。Redis缺点是数据库容量受到物理内存的限制,不能用作海量数据的高性能读写,因此Redis适合的场景主要局限在较小数据量的高性能操作和运算上。Redis较难支持在线扩容，在集群容量达到上限时在线扩容会变得很复杂。为避免这一问题，运维人员在系统上线时必须确保有足够的空间，这对资源造成了很大的浪费。4 乐观锁和悲观锁悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。乐观锁与悲观锁的具体区别: http://www.cnblogs.com/Bob-FD/p/3352216.html5 MVCC 全称是Multi-Version Concurrent Control，即多版本并发控制，在MVCC协议下，每个读操作会看到一个一致性的snapshot，并且可以实现非阻塞的读。MVCC允许数据具有多个版本，这个版本可以是时间戳或者是全局递增的事务ID，在同一个时间点，不同的事务看到的数据是不同的。MySQL的innodb引擎是如何实现MVCC的innodb会为每一行添加两个字段，分别表示该行创建的版本和删除的版本，填入的是事务的版本号，这个版本号随着事务的创建不断递增。在repeated read的隔离级别（事务的隔离级别请看这篇文章）下，具体各种数据库操作的实现：select：满足以下两个条件innodb会返回该行数据：该行的创建版本号小于等于当前版本号，用于保证在select操作之前所有的操作已经执行落地。该行的删除版本号大于当前版本或者为空。删除版本号大于当前版本意味着有一个并发事务将该行删除了。insert：将新插入的行的创建版本号设置为当前系统的版本号。delete：将要删除的行的删除版本号设置为当前系统的版本号。update：不执行原地update，而是转换成insert + delete。将旧行的删除版本号设置为当前版本号，并将新行insert同时设置创建版本号为当前版本号。其中，写操作（insert、delete和update）执行时，需要将系统版本号递增。 由于旧数据并不真正的删除，所以必须对这些数据进行清理，innodb会开启一个后台线程执行清理工作，具体的规则是将删除版本号小于当前系统版本的行删除，这个过程叫做purge。通过MVCC很好的实现了事务的隔离性，可以达到repeated read级别，要实现serializable还必须加锁。参考：MVCC浅析6 MyISAM和InnoDBMyISAM 适合于一些需要大量查询的应用，但其对于有大量写操作并不是很好。甚至你只是需要update一个字段，整个表都会被锁起来，而别的进程，就算是读进程都无法操作直到读操作完成。另外，MyISAM 对于 SELECT COUNT(*) 这类的计算是超快无比的。InnoDB 的趋势会是一个非常复杂的存储引擎，对于一些小的应用，它会比 MyISAM 还慢。他是它支持“行锁” ，于是在写操作比较多的时候，会更优秀。并且，他还支持更多的高级应用，比如：事务。mysql 数据库引擎: http://www.cnblogs.com/0201zcr/p/5296843.htmlMySQL存储引擎－－MyISAM与InnoDB区别: https://segmentfault.com/a/1190000008227211网络1 三次握手客户端通过向服务器端发送一个SYN来创建一个主动打开，作为三次握手的一部分。客户端把这段连接的序号设定为随机数 A。服务器端应当为一个合法的SYN回送一个SYN/ACK。ACK 的确认码应为 A+1，SYN/ACK 包本身又有一个随机序号 B。最后，客户端再发送一个ACK。当服务端受到这个ACK的时候，就完成了三路握手，并进入了连接创建状态。此时包序号被设定为收到的确认号 A+1，而响应则为 B+1。2 四次挥手注意: 中断连接端可以是客户端，也可以是服务器端. 下面仅以客户端断开连接举例, 反之亦然.客户端发送一个数据分段, 其中的 FIN 标记设置为1. 客户端进入 FIN-WAIT 状态. 该状态下客户端只接收数据, 不再发送数据.服务器接收到带有 FIN = 1 的数据分段, 发送带有 ACK = 1 的剩余数据分段, 确认收到客户端发来的 FIN 信息.服务器等到所有数据传输结束, 向客户端发送一个带有 FIN = 1 的数据分段, 并进入 CLOSE-WAIT 状态, 等待客户端发来带有 ACK = 1 的确认报文.客户端收到服务器发来带有 FIN = 1 的报文, 返回 ACK = 1 的报文确认, 为了防止服务器端未收到需要重发, 进入 TIME-WAIT 状态. 服务器接收到报文后关闭连接. 客户端等待 2MSL 后未收到回复, 则认为服务器成功关闭, 客户端关闭连接.图解: http://blog.csdn.net/whuslei/article/details/66674713 ARP协议地址解析协议(Address Resolution Protocol)，其基本功能为透过目标设备的IP地址，查询目标的MAC地址，以保证通信的顺利进行。它是IPv4网络层必不可少的协议，不过在IPv6中已不再适用，并被邻居发现协议（NDP）所替代。4 urllib和urllib2的区别这个面试官确实问过,当时答的urllib2可以Post而urllib不可以.urllib提供urlencode方法用来GET查询字符串的产生，而urllib2没有。这是为何urllib常和urllib2一起使用的原因。urllib2可以接受一个Request类的实例来设置URL请求的headers，urllib仅可以接受URL。这意味着，你不可以伪装你的User Agent字符串等。5 Post和GetGET和POST有什么区别？及为什么网上的多数答案都是错的知乎回答get: RFC 2616 - Hypertext Transfer Protocol -- HTTP/1.1post: RFC 2616 - Hypertext Transfer Protocol -- HTTP/1.16 Cookie和Session CookieSession储存位置客户端服务器端目的跟踪会话，也可以保存用户偏好设置或者保存用户名密码等跟踪会话安全性不安全安全session技术是要使用到cookie的，之所以出现session技术，主要是为了安全。7 apache和nginx的区别nginx 相对 apache 的优点：轻量级，同样起web 服务，比apache 占用更少的内存及资源抗并发，nginx 处理请求是异步非阻塞的，支持更多的并发连接，而apache 则是阻塞型的，在高并发下nginx 能保持低资源低消耗高性能配置简洁高度模块化的设计，编写模块相对简单社区活跃apache 相对nginx 的优点：rewrite ，比nginx 的rewrite 强大模块超多，基本想到的都可以找到少bug ，nginx 的bug 相对较多超稳定8 网站用户密码保存明文保存明文hash后保存,如md5MD5+Salt方式,这个salt可以随机知乎使用了Bcrypy(好像)加密9 HTTP和HTTPS状态码定义1xx 报告接收到请求，继续进程2xx 成功步骤成功接收，被理解，并被接受3xx 重定向为了完成请求,必须采取进一步措施4xx 客户端出错请求包括错的顺序或不能完成5xx 服务器出错服务器无法完成显然有效的请求403: Forbidden404: Not FoundHTTPS握手,对称加密,非对称加密,TLS/SSL,RSA10 XSRF和XSSCSRF(Cross-site request forgery)跨站请求伪造XSS(Cross Site Scripting)跨站脚本攻击CSRF重点在请求,XSS重点在脚本11 幂等 IdempotenceHTTP方法的幂等性是指一次和多次请求某一个资源应该具有同样的副作用。(注意是副作用)GET http://www.bank.com/account/123456，不会改变资源的状态，不论调用一次还是N次都没有副作用。请注意，这里强调的是一次和N次具有相同的副作用，而不是每次GET的结果相同。GET http://www.news.com/latest-news这个HTTP请求可能会每次得到不同的结果，但它本身并没有产生任何副作用，因而是满足幂等性的。DELETE方法用于删除资源，有副作用，但它应该满足幂等性。比如：DELETE http://www.forum.com/article/4231，调用一次和N次对系统产生的副作用是相同的，即删掉id为4231的帖子；因此，调用者可以多次调用或刷新页面而不必担心引起错误。POST所对应的URI并非创建的资源本身，而是资源的接收者。比如：POST http://www.forum.com/articles的语义是在http://www.forum.com/articles下创建一篇帖子，HTTP响应中应包含帖子的创建状态以及帖子的URI。两次相同的POST请求会在服务器端创建两份资源，它们具有不同的URI；所以，POST方法不具备幂等性。PUT所对应的URI是要创建或更新的资源本身。比如：PUT http://www.forum/articles/4231的语义是创建或更新ID为4231的帖子。对同一URI进行多次PUT的副作用和一次PUT是相同的；因此，PUT方法具有幂等性。12 RESTful架构(SOAP,RPC)推荐: http://www.ruanyifeng.com/blog/2011/09/restful.html13 SOAPSOAP（原为Simple Object Access Protocol的首字母缩写，即简单对象访问协议）是交换数据的一种协议规范，使用在计算机网络Web服务（web service）中，交换带结构信息。SOAP为了简化网页服务器（Web Server）从XML数据库中提取数据时，节省去格式化页面时间，以及不同应用程序之间按照HTTP通信协议，遵从XML格式执行资料互换，使其抽象于语言实现、平台和硬件。14 RPCRPC（Remote Procedure Call Protocol）——远程过程调用协议，它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。RPC协议假定某些传输协议的存在，如TCP或UDP，为通信程序之间携带信息数据。在OSI网络通信模型中，RPC跨越了传输层和应用层。RPC使得开发包括网络分布式多程序在内的应用程序更加容易。总结:服务提供的两大流派.传统意义以方法调用为导向通称RPC。为了企业SOA,若干厂商联合推出webservice,制定了wsdl接口定义,传输soap.当互联网时代,臃肿SOA被简化为http+xml/json.但是简化出现各种混乱。以资源为导向,任何操作无非是对资源的增删改查，于是统一的REST出现了.进化的顺序: RPC -> SOAP -> RESTful15 CGI和WSGICGI是通用网关接口，是连接web服务器和应用程序的接口，用户通过CGI来获取动态数据或文件等。CGI程序是一个独立的程序，它可以用几乎所有语言来写，包括perl，c，lua，python等等。WSGI, Web Server Gateway Interface，是Python应用程序或框架和Web服务器之间的一种接口，WSGI的其中一个目的就是让用户可以用统一的语言(Python)编写前后端。官方说明：PEP-333316 中间人攻击在GFW里屡见不鲜的,呵呵.中间人攻击（Man-in-the-middle attack，通常缩写为MITM）是指攻击者与通讯的两端分别创建独立的联系，并交换其所收到的数据，使通讯的两端认为他们正在通过一个私密的连接与对方直接对话，但事实上整个会话都被攻击者完全控制。17 c10k问题所谓c10k问题，指的是服务器同时支持成千上万个客户端的问题，也就是concurrent 10 000 connection（这也是c10k这个名字的由来）。推荐: https://my.oschina.net/xianggao/blog/66427518 socket推荐: http://www.360doc.com/content/11/0609/15/5482098_122692444.shtmlSocket=Ip address+ TCP/UDP + port19 浏览器缓存推荐: http://www.cnblogs.com/skynet/archive/2012/11/28/2792503.html304 Not Modified20 HTTP1.0和HTTP1.1推荐: http://blog.csdn.net/elifefly/article/details/3964766请求头Host字段,一个服务器多个网站长链接文件断点续传身份认证,状态管理,Cache缓存HTTP请求8种方法介绍 HTTP/1.1协议中共定义了8种HTTP请求方法，HTTP请求方法也被叫做“请求动作”，不同的方法规定了不同的操作指定的资源方式。服务端也会根据不同的请求方法做不同的响应。GETGET请求会显示请求指定的资源。一般来说GET方法应该只用于数据的读取，而不应当用于会产生副作用的非幂等的操作中。GET会方法请求指定的页面信息，并返回响应主体，GET被认为是不安全的方法，因为GET方法会被网络蜘蛛等任意的访问。HEADHEAD方法与GET方法一样，都是向服务器发出指定资源的请求。但是，服务器在响应HEAD请求时不会回传资源的内容部分，即：响应主体。这样，我们可以不传输全部内容的情况下，就可以获取服务器的响应头信息。HEAD方法常被用于客户端查看服务器的性能。POSTPOST请求会 向指定资源提交数据，请求服务器进行处理，如：表单数据提交、文件上传等，请求数据会被包含在请求体中。POST方法是非幂等的方法，因为这个请求可能会创建新的资源或/和修改现有资源。PUTPUT请求会身向指定资源位置上传其最新内容，PUT方法是幂等的方法。通过该方法客户端可以将指定资源的最新数据传送给服务器取代指定的资源的内容。DELETEDELETE请求用于请求服务器删除所请求URI（统一资源标识符，Uniform Resource Identifier）所标识的资源。DELETE请求后指定资源会被删除，DELETE方法也是幂等的。CONNECTCONNECT方法是HTTP/1.1协议预留的，能够将连接改为管道方式的代理服务器。通常用于SSL加密服务器的链接与非加密的HTTP代理服务器的通信。OPTIONSOPTIONS请求与HEAD类似，一般也是用于客户端查看服务器的性能。 这个方法会请求服务器返回该资源所支持的所有HTTP请求方法，该方法会用’*’来代替资源名称，向服务器发送OPTIONS请求，可以测试服务器功能是否正常。JavaScript的XMLHttpRequest对象进行CORS跨域资源共享时，就是使用OPTIONS方法发送嗅探请求，以判断是否有对指定资源的访问权限。 允许TRACETRACE请求服务器回显其收到的请求信息，该方法主要用于HTTP请求的测试或诊断。HTTP/1.1之后增加的方法在HTTP/1.1标准制定之后，又陆续扩展了一些方法。其中使用中较多的是 PATCH 方法：PATCHPATCH方法出现的较晚，它在2010年的RFC 5789标准中被定义。PATCH请求与PUT请求类似，同样用于资源的更新。二者有以下两点不同：但PATCH一般用于资源的部分更新，而PUT一般用于资源的整体更新。 当资源不存在时，PATCH会创建一个新的资源，而PUT只会对已在资源进行更新。21 AjaxAJAX,Asynchronous JavaScript and XML（异步的 JavaScript 和 XML）, 是与在不重新加载整个页面的情况下，与服务器交换数据并更新部分网页的技术。*NIXunix进程间通信方式(IPC)管道（Pipe）：管道可用于具有亲缘关系进程间的通信，允许一个进程和另一个与它有共同祖先的进程之间进行通信。命名管道（named pipe）：命名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建。信号（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux除了支持Unix早期信号语义函数sigal外，还支持语义符合Posix.1标准的信号函数sigaction（实际上，该函数是基于BSD的，BSD为了实现可靠信号机制，又能够统一对外接口，用sigaction函数重新实现了signal函数）。消息（Message）队列：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。内存映射（mapped memory）：内存映射允许任何多个进程间通信，每一个使用该机制的进程通过把一个共享的文件映射到自己的进程地址空间来实现它。信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上：Linux和System V的变种都支持套接字。数据结构1 红黑树红黑树与AVL的比较：AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。红黑树详解: https://xieguanglei.github.io/blog/post/red-black-tree.html教你透彻了解红黑树: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md编程题1 台阶问题/斐波那契一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)第二种记忆方法def memo(func): cache = {} def wrap(*args): if args not in cache: cache[args] = func(*args) return cache[args] return wrap @memo def fib(i): if i < 2: return 1 return fib(i-1) + fib(i-2)第三种方法def fib(n): a, b = 0, 1 for _ in xrange(n): a, b = b, a + b return b2 变态台阶问题一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。fib = lambda n: n if n < 2 else 2 * fib(n - 1)3 矩形覆盖我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)4 杨氏矩阵查找在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。使用Step-wise线性搜索。def get_value(l, r, c): return l[r][c] def find(l, x): m = len(l) - 1 n = len(l[0]) - 1 r = 0 c = n while c >= 0 and r <= m: value = get_value(l, r, c) if value == x: return True elif value > x: c = c - 1 elif value < x: r = r + 1 return False5 去除列表中的重复元素用集合list(set(l))用字典l1 = ['b','c','d','b','c','a','a'] l2 = {}.fromkeys(l1).keys() print l2用字典并保持顺序l1 = ['b','c','d','b','c','a','a'] l2 = list(set(l1)) l2.sort(key=l1.index) print l2列表推导式l1 = ['b','c','d','b','c','a','a'] l2 = [] [l2.append(i) for i in l1 if not i in l2]sorted排序并且用列表推导式.l = ['b','c','d','b','c','a','a'][single.append(i) for i in sorted(l) if i not in single]print single6 链表成对调换1->2->3->4转换成2->1->4->3.class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # @param a ListNode # @return a ListNode def swapPairs(self, head): if head != None and head.next != None: next = head.next head.next = self.swapPairs(next.next) next.next = head return next return head7 创建字典的方法1 直接创建dict = {'name':'earth', 'port':'80'}2 工厂方法items=[('name','earth'),('port','80')] dict2=dict(items) dict1=dict((['name','earth'],['port','80']))3 fromkeys()方法dict1={}.fromkeys(('x','y'),-1) dict={'x':-1,'y':-1} dict2={}.fromkeys(('x','y')) dict2={'x':None, 'y':None}8 合并两个有序列表知乎远程面试要求编程尾递归def _recursion_merge_sort2(l1, l2, tmp): if len(l1) == 0 or len(l2) == 0: tmp.extend(l1) tmp.extend(l2) return tmp else: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] return _recursion_merge_sort2(l1, l2, tmp) def recursion_merge_sort2(l1, l2): return _recursion_merge_sort2(l1, l2, [])循环算法思路：定义一个新的空列表比较两个列表的首个元素小的就插入到新列表里把已经插入新列表的元素从旧列表删除直到两个旧列表有一个为空再把旧列表加到新列表后面def loop_merge_sort(l1, l2): tmp = [] while len(l1) > 0 and len(l2) > 0: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] tmp.extend(l1) tmp.extend(l2) return tmppop弹出a = [1,2,3,7] b = [3,4,5] def merge_sortedlist(a,b): c = [] while a and b: if a[0] >= b[0]: c.append(b.pop(0)) else: c.append(a.pop(0)) while a: c.append(a.pop(0)) while b: c.append(b.pop(0)) return c print merge_sortedlist(a,b) 9 交叉链表求交点其实思想可以按照从尾开始比较两个链表，如果相交，则从尾开始必然一致，只要从尾开始比较，直至不一致的地方即为交叉点，如图所示# 使用a,b两个list来模拟链表，可以看出交叉点是 7这个节点 a = [1,2,3,7,9,1,5] b = [4,5,7,9,1,5] for i in range(1,min(len(a),len(b))): if i==1 and (a[-1] != b[-1]): print "No" break else: if a[-i] != b[-i]: print "交叉节点：",a[-i+1] break else: pass另外一种比较正规的方法，构造链表类class ListNode: def __init__(self, x): self.val = x self.next = None def node(l1, l2): length1, lenth2 = 0, 0 # 求两个链表长度 while l1.next: l1 = l1.next length1 += 1 while l2.next: l2 = l2.next length2 += 1 # 长的链表先走 if length1 > lenth2: for _ in range(length1 - length2): l1 = l1.next else: for _ in range(length2 - length1): l2 = l2.next while l1 and l2: if l1.next == l2.next: return l1.next else: l1 = l1.next l2 = l2.next修改了一下:#coding:utf-8 class ListNode: def __init__(self, x): self.val = x self.next = None def node(l1, l2): length1, length2 = 0, 0 # 求两个链表长度 while l1.next: l1 = l1.next#尾节点 length1 += 1 while l2.next: l2 = l2.next#尾节点 length2 += 1 #如果相交 if l1.next == l2.next: # 长的链表先走 if length1 > length2: for _ in range(length1 - length2): l1 = l1.next return l1#返回交点 else: for _ in range(length2 - length1): l2 = l2.next return l2#返回交点 # 如果不相交 else: return思路: http://humaoli.blog.163.com/blog/static/13346651820141125102125995/10 二分查找 #coding:utf-8 def binary_search(list, item): low = 0 high = len(list) - 1 while low <= high: mid = (high - low) / 2 + low # 避免(high + low) / 2溢出 guess = list[mid] if guess > item: high = mid - 1 elif guess < item: low = mid + 1 else: return mid return None mylist = [1,3,5,7,9] print binary_search(mylist, 3) 参考: http://blog.csdn.net/u013205877/article/details/7641171811 快排#coding:utf-8 def quicksort(list): if len(list)<2: return list else: midpivot = list[0] lessbeforemidpivot = [i for i in list[1:] if i<=midpivot] biggerafterpivot = [i for i in list[1:] if i > midpivot] finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot) return finallylist print quicksort([2,4,6,7,1,2,5])更多排序问题可见：数据结构与算法-排序篇-Python描述12 找零问题 #coding:utf-8 #values是硬币的面值values = [ 25, 21, 10, 5, 1] #valuesCounts 钱币对应的种类数 #money 找出来的总钱数 #coinsUsed 对应于目前钱币总数i所使用的硬币数目 def coinChange(values,valuesCounts,money,coinsUsed): #遍历出从1到money所有的钱数可能 for cents in range(1,money+1): minCoins = cents #把所有的硬币面值遍历出来和钱数做对比 for kind in range(0,valuesCounts): if (values[kind] <= cents): temp = coinsUsed[cents - values[kind]] +1 if (temp < minCoins): minCoins = temp coinsUsed[cents] = minCoins print ('面值:{0}的最少硬币使用数为:{1}'.format(cents, coinsUsed[cents])) 思路: http://blog.csdn.net/wdxin1322/article/details/9501163方法: http://www.cnblogs.com/ChenxofHit/archive/2011/03/18/1988431.html13 广度遍历和深度遍历二叉树给定一个数组，构建二叉树，并且按层次打印这个二叉树14 二叉树节点 class Node(object): def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4))) 15 层次遍历 def lookup(root): row = [root] while row: print(row) row = [kid for item in row for kid in (item.left, item.right) if kid] 16 深度遍历 def deep(root): if not root: return print root.data deep(root.left) deep(root.right) if __name__ == '__main__': lookup(tree) deep(tree)17 前中后序遍历深度遍历改变顺序就OK了 #coding:utf-8 #二叉树的遍历 #简单的二叉树节点类 class Node(object): def __init__(self,value,left,right): self.value = value self.left = left self.right = right #中序遍历:遍历左子树,访问当前节点,遍历右子树 def mid_travelsal(root): if root.left is not None: mid_travelsal(root.left) #访问当前节点 print(root.value) if root.right is not None: mid_travelsal(root.right) #前序遍历:访问当前节点,遍历左子树,遍历右子树 def pre_travelsal(root): print (root.value) if root.left is not None: pre_travelsal(root.left) if root.right is not None: pre_travelsal(root.right) #后续遍历:遍历左子树,遍历右子树,访问当前节点 def post_trvelsal(root): if root.left is not None: post_trvelsal(root.left) if root.right is not None: post_trvelsal(root.right) print (root.value) 18 求最大树深def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) + 119 求两棵树是否相同def isSameTree(p, q): if p == None and q == None: return True elif p and q : return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right) else : return False20 前序中序求后序推荐: http://blog.csdn.net/hinyunsin/article/details/6315502def rebuild(pre, center): if not pre: return cur = Node(pre[0]) index = center.index(pre[0]) cur.left = rebuild(pre[1:index + 1], center[:index]) cur.right = rebuild(pre[index + 1:], center[index + 1:]) return cur def deep(root): if not root: return deep(root.left) deep(root.right) print root.data21 单链表逆置class Node(object): def __init__(self, data=None, next=None): self.data = data self.next = next link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9))))))))) def rev(link): pre = link cur = link.next pre.next = None while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre root = rev(link) while root: print root.data root = root.next思路: http://blog.csdn.net/feliciafay/article/details/6841115方法: http://www.xuebuyuan.com/2066385.html?mobile=122 两个字符串是否是变位词class Anagram: """ @:param s1: The first string @:param s2: The second string @:return true or false """ def Solution1(s1,s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and stillOK: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]: found = True else: pos2 = pos2 + 1 if found: alist[pos2] = None else: stillOK = False pos1 = pos1 + 1 return stillOK print(Solution1('abcd','dcba')) def Solution2(s1,s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() pos = 0 matches = True while pos < len(s1) and matches: if alist1[pos] == alist2[pos]: pos = pos + 1 else: matches = False return matches print(Solution2('abcde','edcbg')) def Solution3(s1,s2): c1 = [0]*26 c2 = [0]*26 for i in range(len(s1)): pos = ord(s1[i])-ord('a') c1[pos] = c1[pos] + 1 for i in range(len(s2)): pos = ord(s2[i])-ord('a') c2[pos] = c2[pos] + 1 j = 0 stillOK = True while j<26 and stillOK: if c1[j] == c2[j]: j = j + 1 else: stillOK = False return stillOK print(Solution3('apple','pleap'))23 动态规划问题可参考：动态规划(DP)的整理-Python描述Python设计模式代码直戳: https://github.com/faif/python-patterns创建型模式工厂方法实例 -> 类 -> 类工厂抽象工厂简单来说就是把一些具有相同方法的类再进行封装,抽象共同的方法以供调用.是工厂方法的进阶版本.实例 -> 类 -> 类工厂 -> 抽象工厂惰性初始化 Lazy [email protected],就是当调用的时候才生成.生成器 BuilderBuilder模式主要用于构建一个复杂的对象，但这个对象构建的算法是稳定的，对象中的各个部分经常变化。Builder模式主要在于应对复杂对象各个部分的频繁需求变动。但是难以应对算法的需求变动。这点一定要注意，如果用错了，会带来很多不必要的麻烦。重点是将复杂对象的建造过程抽象出来（抽象类别），使这个抽象过程的不同实现方法可以构造出不同表现（属性）的对象。简单的说：子对象变化较频繁，对算法相对稳定。单例模式 Singleton一个类只有一个实例原型模式特点是通过复制一个已经存在的实例来返回新的实例,而不是新建实例.多用于创建复杂的或者耗时的实例,因为这种情况下,复制一个已经存在的实例使程序运行更高效;或者创建值相等,只是命名不一样的同类数据.对象池 Object pool一个对象池是一组已经初始化过且可以使用的对象，而可以不用在有需求时创建和销毁对象。池的用户可以从池子中取得对象，对其进行操作处理，并在不需要时归还给池子而非销毁 而不是销毁它. 在Python内部实现了对象池技术.例如像小整型这样的数据引用非常多,创建销毁都会消耗时间,所以保存在对象池里,减少开销.结构型模式修饰模型 DecoratorPython里就是装饰器.代理模式 Proxy例如Python里的引用计数.行为型模式迭代器迭代容器里所有的元素.Github原文链接：https://github.com/taizilongxu/interview_python
-
Python面试宝典-基础篇-2020 Python面试宝典 - 基础篇 - 2020题目001: 在Python中如何实现单例模式。点评：单例模式是指让一个类只能创建出唯一的实例，这个题目在面试中出现的频率极高，因为它考察的不仅仅是单例模式，更是对Python语言到底掌握到何种程度，建议大家用装饰器和元类这两种方式来实现单例模式，因为这两种方式的通用性最强，而且也可以顺便展示自己对装饰器和元类中两个关键知识点的理解。方法一：使用装饰器实现单例模式。from functools import wraps def singleton(cls): """单例类装饰器""" instances = {} @wraps(cls) def wrapper(*args, **kwargs): if cls not in instances: instances[cls] = cls(*args, **kwargs) return instances[cls] return wrapper @singleton class President: pass扩展：装饰器是Python中非常有特色的语法，用一个函数去装饰另一个函数或类，为其添加额外的能力。通常通过装饰来实现的功能都属横切关注功能，也就是跟正常的业务逻辑没有必然联系，可以动态添加或移除的功能。装饰器可以为代码提供缓存、代理、上下文环境等服务，它是对设计模式中代理模式的践行。在写装饰器的时候，带装饰功能的函数（上面代码中的wrapper函数）通常都会用functools模块中的wraps再加以装饰，这个装饰器最重要的作用是给被装饰的类或函数动态添加一个__wrapped__属性，这个属性会将被装饰之前的类或函数保留下来，这样在我们不需要装饰功能的时候，可以通过它来取消装饰器，例如可以使用President = President.__wrapped__来取消对President类做的单例处理。需要提醒大家的是：上面的单例并不是线程安全的，如果要做到线程安全，需要对创建对象的代码进行加锁的处理。在Python中可以使用threading模块的RLock对象来提供锁，可以使用锁对象的acquire和release方法来实现加锁和解锁的操作。当然，更为简便的做法是使用锁对象的with上下文语法来进行隐式的加锁和解锁操作。方法二：使用元类实现单例模式。class SingletonMeta(type): """自定义单例元类""" def __init__(cls, *args, **kwargs): cls.__instance = None super().__init__(*args, **kwargs) def __call__(cls, *args, **kwargs): if cls.__instance is None: cls.__instance = super().__call__(*args, **kwargs) return cls.__instance class President(metaclass=SingletonMeta): pass扩展：Python是面向对象的编程语言，在面向对象的世界中，一切皆为对象。对象是通过类来创建的，而类本身也是对象，类这样的对象是通过元类来创建的。我们在定义类时，如果没有给一个类指定父类，那么默认的父类是object，如果没有给一个类指定元类，那么默认的元类是type。通过自定义的元类，我们可以改变一个类默认的行为，就如同上面的代码中，我们通过元类的__call__魔术方法，改变了President类的构造器那样。补充：关于单例模式，在面试中还有可能被问到它的应用场景。通常一个对象的状态是被其他对象共享的，就可以将其设计为单例，例如项目中使用的数据库连接池对象和配置对象通常都是单例，这样才能保证所有地方获取到的数据库连接和配置信息是完全一致的；而且由于对象只有唯一的实例，因此从根本上避免了重复创建对象造成的时间和空间上的开销，也避免了对资源的多重占用。再举个例子，项目中的日志操作通常也会使用单例模式，这是因为共享的日志文件一直处于打开状态，只能有一个实例去操作它，否则在写入日志的时候会产生混乱。题目002：不使用中间变量，交换两个变量a和b的值。点评：典型的送人头的题目，通常交换两个变量需要借助一个中间变量，如果不允许使用中间变量，在其他编程语言中可以使用异或运算的方式来实现交换两个变量的值，但是Python中有更为简单明了的做法。方法一：a = a ^ b b = a ^ b a = a ^ b方法二：a, b = b, a扩展：需要注意，a, b = b, a这种做法其实并不是元组解包，虽然很多人都这样认为。Python字节码指令中有ROT_TWO指令来支持这个操作，类似的还有ROT_THREE，对于3个以上的元素，如a, b, c, d = b, c, d, a，才会用到创建元组和元组解包。想知道你的代码对应的字节码指令，可以使用Python标准库中dis模块的dis函数来反汇编你的Python代码。题目003：写一个删除列表中重复元素的函数，要求去重后元素相对位置保持不变。点评：这个题目在初中级Python岗位面试的时候经常出现，题目源于《Python Cookbook》这本书第一章的第10个问题，有很多面试题其实都是这本书上的原题，所以建议大家有时间好好研读一下这本书。def dedup(items): no_dup_items = [] seen = set() for item in items: if item not in seen: no_dup_items.append(item) seen.add(item) return no_dup_items如果愿意也可以把上面的函数改造成一个生成器，代码如下所示。def dedup(items): seen = set() for item in items: if item not in seen: yield item seen.add(item)扩展：由于Python中的集合底层使用哈希存储，所以集合的in和not in成员运算在性能上远远优于列表，所以上面的代码我们使用了集合来保存已经出现过的元素。集合中的元素必须是hashable对象，因此上面的代码在列表元素不是hashable对象时会失效，要解决这个问题可以给函数增加一个参数，该参数可以设计为返回哈希码或hashable对象的函数。题目004：假设你使用的是官方的CPython，说出下面代码的运行结果。点评：下面的程序对实际开发并没有什么意义，但却是CPython中的一个大坑，这道题旨在考察面试者对官方的Python解释器到底了解到什么程度。a, b, c, d = 1, 1, 1000, 1000 print(a is b, c is d) def foo(): e = 1000 f = 1000 print(e is f, e is d) g = 1 print(g is a) foo()运行结果：True False True False True上面代码中a is b的结果是True但c is d的结果是False，这一点的确让人费解。CPython解释器出于性能优化的考虑，把频繁使用的整数对象用一个叫small_ints的对象池缓存起来造成的。small_ints缓存的整数值被设定为[-5, 256]这个区间，也就是说，在任何引用这些整数的地方，都不需要重新创建int对象，而是直接引用缓存池中的对象。如果整数不在该范围内，那么即便两个整数的值相同，它们也是不同的对象。CPython底层为了进一步提升性能还做了另一个设定，对于同一个代码块中值不在small_ints缓存范围内的整数，如果同一个代码块中已经存在一个值与其相同的整数对象，那么就直接引用该对象，否则创建新的int对象。需要大家注意的是，这条规则对数值型适用，但对字符串则需要考虑字符串的长度，这一点大家可以自行证明。扩展：如果你用PyPy（另一种Python解释器实现，支持JIT，对CPython的缺点进行了改良，在性能上优于CPython，但对三方库的支持略差）来运行上面的代码，你会发现所有的输出都是True。题目005：Lambda函数是什么，举例说明的它的应用场景。点评：这个题目主要想考察的是Lambda函数的应用场景，潜台词是问你在项目中有没有使用过Lambda函数，具体在什么场景下会用到Lambda函数，借此来判断你写代码的能力。因为Lambda函数通常用在高阶函数中，主要的作用是通过向函数传入函数或让函数返回函数最终实现代码的解耦合。Lambda函数也叫匿名函数，它是功能简单用一行代码就能实现的小型函数。Python中的Lambda函数只能写一个表达式，这个表达式的执行结果就是函数的返回值，不用写return关键字。Lambda函数因为没有名字，所以也不会跟其他函数发生命名冲突的问题。扩展：面试的时候有可能还会考你用Lambda函数来实现一些功能，也就是用一行代码来实现题目要求的功能，例如：用一行代码实现求阶乘的函数，用一行代码实现求最大公约数的函数等。fac = lambda x: __import__('functools').reduce(int.__mul__, range(1, x + 1), 1) gcd = lambda x, y: y % x and gcd(y % x, x) or xLambda函数其实最为主要的用途是把一个函数传入另一个高阶函数（如Python内置的filter、map等）中来为函数做解耦合，增强函数的灵活性和通用性。下面的例子通过使用filter和map函数，实现了从列表中筛选出奇数并求平方构成新列表的操作，因为用到了高阶函数，过滤和映射数据的规则都是函数的调用者通过另外一个函数传入的，因此这filter和map函数没有跟特定的过滤和映射数据的规则耦合在一起。items = [12, 5, 7, 10, 8, 19] items = list(map(lambda x: x ** 2, filter(lambda x: x % 2, items))) print(items) # [25, 49, 361]扩展：用列表的生成式来实现上面的代码会更加简单明了，代码如下所示。items = [12, 5, 7, 10, 8, 19] items = [x ** 2 for x in items if x % 2] print(items) # [25, 49, 361]题目006：说说Python中的浅拷贝和深拷贝。点评：这个题目本身出现的频率非常高，但是就题论题而言没有什么技术含量。对于这种面试题，在回答的时候一定要让你的答案能够超出面试官的预期，这样才能获得更好的印象分。所以回答这个题目的要点不仅仅是能够说出浅拷贝和深拷贝的区别，深拷贝的时候可能遇到的两大问题，还要说出Python标准库对浅拷贝和深拷贝的支持，然后可以说说列表、字典如何实现拷贝操作以及如何通过序列化和反序列的方式实现深拷贝，最后还可以提到设计模式中的原型模式以及它在项目中的应用。浅拷贝通常只复制对象本身，而深拷贝不仅会复制对象，还会递归的复制对象所关联的对象。深拷贝可能会遇到两个问题：一是一个对象如果直接或间接的引用了自身，会导致无休止的递归拷贝；二是深拷贝可能对原本设计为多个对象共享的数据也进行拷贝。Python通过copy模块中的copy和deepcopy函数来实现浅拷贝和深拷贝操作，其中deepcopy可以通过memo字典来保存已经拷贝过的对象，从而避免刚才所说的自引用递归问题；此外，可以通过copyreg模块的pickle函数来定制指定类型对象的拷贝行为。deepcopy函数的本质其实就是对象的一次序列化和一次返回序列化，面试题中还考过用自定义函数实现对象的深拷贝操作，显然我们可以使用pickle模块的dumps和loads来做到，代码如下所示。import pickle my_deep_copy = lambda obj: pickle.loads(pickle.dumps(obj))列表的切片操作[:]相当于实现了列表对象的浅拷贝，而字典的copy方法可以实现字典对象的浅拷贝。对象拷贝其实是更为快捷的创建对象的方式。在Python中，通过构造器创建对象属于两阶段构造，首先是分配内存空间，然后是初始化。在创建对象时，我们也可以基于“原型”对象来创建新对象，通过对原型对象的拷贝（复制内存）就完成了对象的创建和初始化，这种做法更加高效，这也就是设计模式中的原型模式。在Python中，我们可以通过元类的方式来实现原型模式，代码如下所示。import copy class PrototypeMeta(type): """实现原型模式的元类""" def __init__(cls, *args, **kwargs): super().__init__(*args, **kwargs) # 为对象绑定clone方法来实现对象拷贝 cls.clone = lambda self, is_deep=True: \ copy.deepcopy(self) if is_deep else copy.copy(self) class Person(metaclass=PrototypeMeta): pass p1 = Person() p2 = p1.clone() # 深拷贝 p3 = p1.clone(is_deep=False) # 浅拷贝题目007：Python是如何实现内存管理的？点评：当面试官问到这个问题的时候，一个展示自己的机会就摆在面前了。你要先反问面试官：“你说的是官方的CPython解释器吗？”。这个反问可以展示出你了解过Python解释器的不同的实现版本，而且你也知道面试官想问的是CPython。当然，很多面试官对不同的Python解释器底层实现到底有什么差别也没有概念。所以，千万不要觉得面试官一定比你强，怀揣着这份自信可以让你更好的完成面试。Python提供了自动化的内存管理，也就是说内存空间的分配与释放都是由Python解释器在运行时自动进行的，自动管理内存功能极大的减轻程序员的工作负担，也能够帮助程序员在一定程度上解决内存泄露的问题。以CPython解释器为例，它的内存管理有三个关键点：引用计数、标记清理、分代收集。引用计数：对于CPython解释器来说，Python中的每一个对象其实就是PyObject结构体，它的内部有一个名为ob_refcnt 的引用计数器成员变量。程序在运行的过程中ob_refcnt的值会被更新并藉此来反映引用有多少个变量引用到该对象。当对象的引用计数值为0时，它的内存就会被释放掉。typedef struct _object { _PyObject_HEAD_EXTRA Py_ssize_t ob_refcnt; struct _typeobject *ob_type; } PyObject;以下情况会导致引用计数加1：对象被创建对象被引用对象作为参数传入到一个函数中对象作为元素存储到一个容器中以下情况会导致引用计数减1：用del语句显示删除对象引用对象引用被重新赋值其他对象一个对象离开它所在的作用域持有该对象的容器自身被销毁持有该对象的容器删除该对象可以通过sys模块的getrefcount函数来获得对象的引用计数。引用计数的内存管理方式在遇到循环引用的时候就会出现致命伤，因此需要其他的垃圾回收算法对其进行补充。标记清理：CPython使用了“标记-清理”（Mark and Sweep）算法解决容器类型可能产生的循环引用问题。该算法在垃圾回收时分为两个阶段：标记阶段，遍历所有的对象，如果对象是可达的（被其他对象引用），那么就标记该对象为可达；清除阶段，再次遍历对象，如果发现某个对象没有标记为可达，则就将其回收。CPython底层维护了两个双端链表，一个链表存放着需要被扫描的容器对象（姑且称之为链表A），另一个链表存放着临时不可达对象（姑且称之为链表B）。为了实现“标记-清理”算法，链表中的每个节点除了有记录当前引用计数的ref_count变量外，还有一个gc_ref变量，这个gc_ref是ref_count的一个副本，所以初始值为ref_count的大小。执行垃圾回收时，首先遍历链表A中的节点，并且将当前对象所引用的所有对象的gc_ref减1，这一步主要作用是解除循环引用对引用计数的影响。再次遍历链表A中的节点，如果节点的gc_ref值为0，那么这个对象就被标记为“暂时不可达”（GC_TENTATIVELY_UNREACHABLE）并被移动到链表B中；如果节点的gc_ref不为0，那么这个对象就会被标记为“可达“（GC_REACHABLE），对于”可达“对象，还要递归的将该节点可以到达的节点标记为”可达“；链表B中被标记为”可达“的节点要重新放回到链表A中。在两次遍历之后，链表B中的节点就是需要释放内存的节点。分代回收：在循环引用对象的回收中，整个应用程序会被暂停，为了减少应用程序暂停的时间，Python 通过分代回收（空间换时间）的方法提高垃圾回收效率。分代回收的基本思想是：对象存在的时间越长，是垃圾的可能性就越小，应该尽量不对这样的对象进行垃圾回收。CPython将对象分为三种世代分别记为0、1、2，每一个新生对象都在第0代中，如果该对象在一轮垃圾回收扫描中存活下来，那么它将被移到第1代中，存在于第1代的对象将较少的被垃圾回收扫描到；如果在对第1代进行垃圾回收扫描时，这个对象又存活下来，那么它将被移至第2代中，在那里它被垃圾回收扫描的次数将会更少。分代回收扫描的门限值可以通过gc模块的get_threshold函数来获得，该函数返回一个三元组，分别表示多少次内存分配操作后会执行0代垃圾回收，多少次0代垃圾回收后会执行1代垃圾回收，多少次1代垃圾回收后会执行2代垃圾回收。需要说明的是，如果执行一次2代垃圾回收，那么比它年轻的代都要执行垃圾回收。如果想修改这几个门限值，可以通过gc模块的set_threshold函数来做到。题目008：说一下你对Python中迭代器和生成器的理解。点评：很多人面试者都会写迭代器和生成器，但是却无法准确的解释什么是迭代器和生成器。如果你也有同样的困惑，可以参考下面的回答。迭代器是实现了迭代器协议的对象。跟其他编程语言不通，Python中没有用于定义协议或表示约定的关键字，像interface、protocol这些单词并不在Python语言的关键字列表中。Python语言通过魔法方法来表示约定，也就是我们所说的协议，而__next__和__iter__这两个魔法方法就代表了迭代器协议。可以通过for-in循环从迭代器对象中取出值，也可以使用next函数取出迭代器对象中的下一个值。生成器是迭代器的语法升级版本，可以用更为简单的代码来实现一个迭代器。扩展：面试中经常让写生成斐波那契数列的迭代器，大家可以参考下面的代码。class Fib(object): def __init__(self, num): self.num = num self.a, self.b = 0, 1 self.idx = 0 def __iter__(self): return self def __next__(self): if self.idx < self.num: self.a, self.b = self.b, self.a + self.b self.idx += 1 return self.a raise StopIteration()如果用生成器的语法来改写上面的代码，代码会简单优雅很多。def fib(num): a, b = 0, 1 for _ in range(num): a, b = b, a + b yield a题目009：正则表达式的match方法和search方法有什么区别？点评：正则表达式是字符串处理的重要工具，所以也是面试中经常考察的知识点。在Python中，使用正则表达式有两种方式，一种是直接调用re模块中的函数，传入正则表达式和需要处理的字符串；一种是先通过re模块的compile函数创建正则表达式对象，然后再通过对象调用方法并传入需要处理的字符串。如果一个正则表达式被频繁的使用，我们推荐用re.compile函数创建正则表达式对象，这样会减少频繁编译同一个正则表达式所造成的开销。match方法是从字符串的起始位置进行正则表达式匹配，返回Match对象或None。search方法会扫描整个字符串来找寻匹配的模式，同样也是返回Match对象或None。题目010：下面这段代码的执行结果是什么。def multiply(): return [lambda x: i * x for i in range(4)] print([m(100) for m in multiply()])运行结果：[300, 300, 300, 300]上面代码的运行结果很容易被误判为[0, 100, 200, 300]。首先需要注意的是multiply函数用生成式语法返回了一个列表，列表中保存了4个Lambda函数，这4个Lambda函数会返回传入的参数乘以i的结果。需要注意的是这里有闭包（closure）现象，multiply函数中的局部变量i的生命周期被延展了，由于i最终的值是3，所以通过m(100)调列表中的Lambda函数时会返回300，而且4个调用都是如此。如果想得到[0, 100, 200, 300]这个结果，可以按照下面几种方式来修改multiply函数。方法一：使用生成器，让函数获得i的当前值。def multiply(): return (lambda x: i * x for i in range(4)) print([m(100) for m in multiply()])或者def multiply(): for i in range(4): yield lambda x: x * i print([m(100) for m in multiply()])方法二：使用偏函数，彻底避开闭包。from functools import partial from operator import __mul__ def multiply(): return [partial(__mul__, i) for i in range(4)] print([m(100) for m in multiply()])题目011：Python中为什么没有函数重载？点评：C++、Java、C#等诸多编程语言都支持函数重载，所谓函数重载指的是在同一个作用域中有多个同名函数，它们拥有不同的参数列表（参数个数不同或参数类型不同或二者皆不同），可以相互区分。重载也是一种多态性，因为通常是在编译时通过参数的个数和类型来确定到底调用哪个重载函数，所以也被称为编译时多态性或者叫前绑定。这个问题的潜台词其实是问面试者是否有其他编程语言的经验，是否理解Python是动态类型语言，是否知道Python中函数的可变参数、关键字参数这些概念。首先Python是解释型语言，函数重载现象通常出现在编译型语言中。其次Python是动态类型语言，函数的参数没有类型约束，也就无法根据参数类型来区分重载。再者Python中函数的参数可以有默认值，可以使用可变参数和关键字参数，因此即便没有函数重载，也要可以让一个函数根据调用者传入的参数产生不同的行为。题目012：用Python代码实现Python内置函数max。点评：这个题目看似简单，但实际上还是比较考察面试者的功底。因为Python内置的max函数既可以传入可迭代对象找出最大，又可以传入两个或多个参数找出最大；最为关键的是还可以通过命名关键字参数key来指定一个用于元素比较的函数，还可以通过default命名关键字参数来指定当可迭代对象为空时返回的默认值。下面的代码仅供参考：def my_max(*args, key=None, default=None): """ 获取可迭代对象中最大的元素或两个及以上实参中最大的元素 :param args: 一个可迭代对象或多个元素 :param key: 提取用于元素比较的特征值的函数，默认为None :param default: 如果可迭代对象为空则返回该默认值，如果没有给默认值则引发ValueError异常 :return: 返回可迭代对象或多个元素中的最大元素 """ if len(args) == 1 and len(args[0]) == 0: if default: return default else: raise ValueError('max() arg is an empty sequence') items = args[0] if len(args) == 1 else args max_elem, max_value = items[0], items[0] if key: max_value = key(max_value) for item in items: value = item if key: value = key(item) if value > max_value: max_elem, max_value = item, value return max_elem题目013：写一个函数统计传入的列表中每个数字出现的次数并返回对应的字典。点评：送人头的题目，不解释。def count_letters(items): result = {} for item in items: if isinstance(item, (int, float)): result[item] = result.get(item, 0) + 1 return result也可以直接使用Python标准库中collections模块的Counter类来解决这个问题，Counter是dict的子类，它会将传入的序列中的每个元素作为键，元素出现的次数作为值来构造字典。from collections import Counter def count_letters(items): counter = Counter(items) return {key: value for key, value in counter.items() \ if isinstance(key, (int, float))}题目014：使用Python代码实现遍历一个文件夹的操作。点评：基本也是送人头的题目，只要用过os模块就应该知道怎么做。Python标准库os模块的walk函数提供了遍历一个文件夹的功能，它返回一个生成器。import os g = os.walk('/Users/Hao/Downloads/') for path, dir_list, file_list in g: for dir_name in dir_list: print(os.path.join(path, dir_name)) for file_name in file_list: print(os.path.join(path, file_name))说明：os.path模块提供了很多进行路径操作的工具函数，在项目开发中也是经常会用到的。如果题目明确要求不能使用os.walk函数，那么可以使用os.listdir函数来获取指定目录下的文件和文件夹，然后再通过循环遍历用os.isdir函数判断哪些是文件夹，对于文件夹可以通过递归调用进行遍历，这样也可以实现遍历一个文件夹的操作。题目015：现有2元、3元、5元共三种面额的货币，如果需要找零99元，一共有多少种找零的方式？点评：还有一个非常类似的题目：“一个小朋友走楼梯，一次可以走1个台阶、2个台阶或3个台阶，问走完10个台阶一共有多少种走法？”，这两个题目的思路是一样，如果用递归函数来写的话非常简单。from functools import lru_cache @lru_cache() def change_money(total): if total == 0: return 1 if total < 0: return 0 return change_money(total - 2) + change_money(total - 3) + \ change_money(total - 5)说明：在上面的代码中，我们用lru_cache装饰器装饰了递归函数change_money，如果不做这个优化，上面代码的渐近时间复杂度将会是$O(3^N)$，而如果参数total的值是99，这个运算量是非常巨大的。lru_cache装饰器会缓存函数的执行结果，这样就可以减少重复运算所造成的开销，这是空间换时间的策略，也是动态规划的编程思想。题目016：写一个函数，给定矩阵的阶数n，输出一个螺旋式数字矩阵。例如：n = 2，返回：1 2 4 3例如：n = 3，返回：1 2 3 8 9 4 7 6 5这个题目本身并不复杂，下面的代码仅供参考。def show_spiral_matrix(n): matrix = [[0] * n for _ in range(n)] row, col = 0, 0 num, direction = 1, 0 while num <= n ** 2: if matrix[row][col] == 0: matrix[row][col] = num num += 1 if direction == 0: if col < n - 1 and matrix[row][col + 1] == 0: col += 1 else: direction += 1 elif direction == 1: if row < n - 1 and matrix[row + 1][col] == 0: row += 1 else: direction += 1 elif direction == 2: if col > 0 and matrix[row][col - 1] == 0: col -= 1 else: direction += 1 else: if row > 0 and matrix[row - 1][col] == 0: row -= 1 else: direction += 1 direction %= 4 for x in matrix: for y in x: print(y, end='\t') print()题目017：阅读下面的代码，写出程序的运行结果。items = [1, 2, 3, 4] print([i for i in items if i > 2]) print([i for i in items if i % 2]) print([(x, y) for x, y in zip('abcd', (1, 2, 3, 4, 5))]) print({x: f'item{x ** 2}' for x in (2, 4, 6)}) print(len({x for x in 'hello world' if x not in 'abcdefg'}))点评：生成式（推导式）属于Python的特色语法之一，几乎是面试必考内容。Python中通过生成式字面量语法，可以创建出列表、集合、字典。[3, 4] [1, 3] [('a', 1), ('b', 2), ('c', 3), ('d', 4)] {2: 'item4', 4: 'item16', 6: 'item36'} 6题目018：说出下面代码的运行结果。class Parent: x = 1 class Child1(Parent): pass class Child2(Parent): pass print(Parent.x, Child1.x, Child2.x) Child1.x = 2 print(Parent.x, Child1.x, Child2.x) Parent.x = 3 print(Parent.x, Child1.x, Child2.x)点评：运行上面的代码首先输出1 1 1，这一点大家应该没有什么疑问。接下来，通过Child1.x = 2给类Child1重新绑定了属性x并赋值为2，所以Child1.x会输出2，而Parent和Child2并不受影响。执行Parent.x = 3会重新给Parent类的x属性赋值为3，由于Child2的x属性继承自Parent，所以Child2.x的值也是3；而之前我们为Child1重新绑定了x属性，那么它的x属性值不会受到Parent.x = 3的影响，还是之前的值2。1 1 1 1 2 1 3 2 3题目19：说说你用过Python标准库中的哪些模块。点评：Python标准库中的模块非常多，建议大家根据自己过往的项目经历来介绍你用过的标准库和三方库，因为这些是你最为熟悉的，经得起面试官深挖的。模块名介绍sys跟Python解释器相关的变量和函数，例如：sys.version、sys.exit()os和操作系统相关的功能，例如：os.listdir()、os.remove()re和正则表达式相关的功能，例如：re.compile()、re.search()math和数学运算相关的功能，例如：math.pi、math.e、math.coslogging和日志系统相关的类和函数，例如：logging.Logger、logging.Handlerjson / pickle实现对象序列化和反序列的模块，例如：json.loads、json.dumpshashlib封装了多种哈希摘要算法的模块，例如：hashlib.md5、hashlib.sha1urllib包含了和URL相关的子模块，例如：urllib.request、urllib.parseitertools提供各种迭代器的模块，例如：itertools.cycle、itertools.productfunctools函数相关工具模块，例如：functools.partial、functools.lru_cachecollections / heapq封装了常用数据结构和算法的模块，例如：collections.dequethreading / multiprocessing多线程/多进程相关类和函数的模块，例如：threading.Threadconcurrent.futures / asyncio并发编程/异步编程相关的类和函数的模块，例如：ThreadPoolExecutorbase64提供BASE-64编码相关函数的模块，例如：bas64.encodecsv和读写CSV文件相关的模块，例如：csv.reader、csv.writerprofile / cProfile / pstats和代码性能剖析相关的模块，例如：cProfile.run、pstats.Statsunittest和单元测试相关的模块，例如：unittest.TestCase题目20：__init__和__new__方法有什么区别？Python中调用构造器创建对象属于两阶段构造过程，首先执行__new__方法获得保存对象所需的内存空间，再通过__init__执行对内存空间数据的填充（对象属性的初始化）。__new__方法的返回值是创建好的Python对象（的引用），而__init__方法的第一个参数就是这个对象（的引用），所以在__init__中可以完成对对象的初始化操作。__new__是类方法，它的第一个参数是类，__init__是对象方法，它的第一个参数是对象。题目21：输入年月日，判断这个日期是这一年的第几天。方法一：不使用标准库中的模块和函数。def is_leap_year(year): """判断指定的年份是不是闰年，平年返回False，闰年返回True""" return year % 4 == 0 and year % 100 != 0 or year % 400 == 0 def which_day(year, month, date): """计算传入的日期是这一年的第几天""" # 用嵌套的列表保存平年和闰年每个月的天数 days_of_month = [ [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31], [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] ] days = days_of_month[is_leap_year(year)][:month - 1] return sum(days) + date方法二：使用标准库中的datetime模块。import datetime def which_day(year, month, date): end = datetime.date(year, month, date) start = datetime.date(year, 1, 1) return (end - start).days + 1题目22：平常工作中用什么工具进行静态代码分析。点评：静态代码分析工具可以从代码中提炼出各种静态属性，这使得开发者可以对代码的复杂性、可维护性和可读性有更好的了解，这里所说的静态属性包括：代码是否符合编码规范，例如：PEP-8。代码中潜在的问题，包括：语法错误、缩进问题、导入缺失、变量覆盖等。代码中的坏味道。代码的复杂度。代码的逻辑问题。工作中静态代码分析主要用到的是Pylint。Pylint可以检查出代码错误、坏味道、不规范的代码等问题，较新的版本中还提供了代码复杂度统计数据，可以生成检查报告。Flake8封装了Pyflakes（检查代码逻辑错误）、McCabe（检查代码复杂性）和Pycodestyle（检查代码是否符合PEP-8规范）工具，它可以执行这三个工具提供的检查。题目23：说一下你知道的Python中的魔术方法。点评：魔术方法也称为魔法方法，是Python中的特色语法，也是面试中的高频问题。魔术方法作用__new__、__init__、__del__创建和销毁对象相关__add__、__sub__、__mul__、__div__、__floordiv__、__mod__算术运算符相关__eq__、__ne__、__lt__、__gt__、__le__、__ge__关系运算符相关__pos__、__neg__、__invert__一元运算符相关__lshift__、__rshift__、__and__、__or__、__xor__位运算相关__enter__、__exit__上下文管理器协议__iter__、__next__、__reversed__迭代器协议__int__、__long__、__float__、__oct__、__hex__类型/进制转换相关__str__、__repr__、__hash__、__dir__对象表述相关__len__、__getitem__、__setitem__、__contains__、__missing__序列相关__copy__、__deepcopy__对象拷贝相关__call__、__setattr__、__getattr__、__delattr__其他魔术方法题目24：函数参数*arg和**kwargs分别代表什么？Python中，函数的参数分为位置参数、可变参数、关键字参数、命名关键字参数。*args代表可变参数，可以接收0个或任意多个参数，当不确定调用者会传入多少个位置参数时，就可以使用可变参数，它会将传入的参数打包成一个元组。**kwargs代表关键字参数，可以接收用参数名=参数值的方式传入的参数，传入的参数的会打包成一个字典。定义函数时如果同时使用*args和**kwargs，那么函数可以接收任意参数。题目25：写一个记录函数执行时间的装饰器。点评：高频面试题，也是最简单的装饰器，面试者必须要掌握的内容。方法一：用函数实现装饰器。from functools import wraps from time import time def record_time(func): @wraps(func) def wrapper(*args, **kwargs): start = time() result = func(*args, **kwargs) print(f'{func.__name__}执行时间: {time() - start}秒') return result return wrapper方法二：用类实现装饰器。类有__call__魔术方法，该类对象就是可调用对象，可以当做装饰器来使用。from functools import wraps from time import time class Record: def __call__(self, func): @wraps(func) def wrapper(*args, **kwargs): start = time() result = func(*args, **kwargs) print(f'{func.__name__}执行时间: {time() - start}秒') return result return wrapper说明：装饰器可以用来装饰类或函数，为其提供额外的能力，属于设计模式中的代理模式。扩展：装饰器本身也可以参数化，例如上面的例子中，如果不希望在终端中显示函数的执行时间而是希望由调用者来决定如何输出函数的执行时间，可以通过参数化装饰器的方式来做到，代码如下所示。from functools import wraps from time import time def record_time(output): """可以参数化的装饰器""" def decorate(func): @wraps(func) def wrapper(*args, **kwargs): start = time() result = func(*args, **kwargs) output(func.__name__, time() - start) return result return wrapper return decorate题目26：什么是鸭子类型（duck typing）？鸭子类型是动态类型语言判断一个对象是不是某种类型时使用的方法，也叫做鸭子判定法。简单的说，鸭子类型是指判断一只鸟是不是鸭子，我们只关心它游泳像不像鸭子、叫起来像不像鸭子、走路像不像鸭子就足够了。换言之，如果对象的行为跟我们的预期是一致的（能够接受某些消息），我们就认定它是某种类型的对象。在Python语言中，有很多bytes-like对象（如：bytes、bytearray、array.array、memoryview）、file-like对象（如：StringIO、BytesIO、GzipFile、socket）、path-like对象（如：str、bytes），其中file-like对象都能支持read和write操作，可以像文件一样读写，这就是所谓的对象有鸭子的行为就可以判定为鸭子的判定方法。再比如Python中列表的extend方法，它需要的参数并不一定要是列表，只要是可迭代对象就没有问题。说明：动态语言的鸭子类型使得设计模式的应用被大大简化。题目27：说一下Python中变量的作用域。Python中有四种作用域，分别是局部作用域（Local）、嵌套作用域（Embedded）、全局作用域（Global）、内置作用域（Built-in），搜索一个标识符时，会按照LEGB的顺序进行搜索，如果所有的作用域中都没有找到这个标识符，就会引发NameError异常。题目28：说一下你对闭包的理解。闭包是支持一等函数的编程语言（Python、JavaScript等）中实现词法绑定的一种技术。当捕捉闭包的时候，它的自由变量（在函数外部定义但在函数内部使用的变量）会在捕捉时被确定，这样即便脱离了捕捉时的上下文，它也能照常运行。简单的说，可以将闭包理解为能够读取其他函数内部变量的函数。正在情况下，函数的局部变量在函数调用结束之后就结束了生命周期，但是闭包使得局部变量的生命周期得到了延展。使用闭包的时候需要注意，闭包会使得函数中创建的对象不会被垃圾回收，可能会导致很大的内存开销，所以闭包一定不能滥用。题目29：说一下Python中的多线程和多进程的应用场景和优缺点。线程是操作系统分配CPU的基本单位，进程是操作系统分配内存的基本单位。通常我们运行的程序会包含一个或多个进程，而每个进程中又包含一个或多个线程。多线程的优点在于多个线程可以共享进程的内存空间，所以进程间的通信非常容易实现；但是如果使用官方的CPython解释器，多线程受制于GIL（全局解释器锁），并不能利用CPU的多核特性，这是一个很大的问题。使用多进程可以充分利用CPU的多核特性，但是进程间通信相对比较麻烦，需要使用IPC机制（管道、套接字等）。多线程适合那些会花费大量时间在I/O操作上，但没有太多并行计算需求且不需占用太多内存的I/O密集型应用。多进程适合执行计算密集型任务（如：视频编码解码、数据处理、科学计算等）、可以分解为多个并行子任务并能合并子任务执行结果的任务以及在内存使用方面没有任何限制且不强依赖于I/O操作的任务。扩展：Python中实现并发编程通常有多线程、多进程和异步编程三种选择。异步编程实现了协作式并发，通过多个相互协作的子程序的用户态切换，实现对CPU的高效利用，这种方式也是非常适合I/O密集型应用的。题目30：说一下Python 2和Python 3的区别。点评：这种问题千万不要背所谓的参考答案，说一些自己最熟悉的就足够了。Python 2中的print和exec都是关键字，在Python 3中变成了函数。Python 3中没有long类型，整数都是int类型。Python 2中的不等号<>在Python 3中被废弃，统一使用!=。Python 2中的xrange函数在Python 3中被range函数取代。Python 3对Python 2中不安全的input函数做出了改进，废弃了raw_input函数。Python 2中的file函数被Python 3中的open函数取代。Python 2中的/运算对于int类型是整除，在Python 3中要用//来做整除除法。Python 3中改进了Python 2捕获异常的代码，很明显Python 3的写法更合理。Python 3生成式中循环变量的作用域得到了更好的控制，不会影响到生成式之外的同名变量。Python 3中的round函数可以返回int或float类型，Python 2中的round函数返回float类型。Python 3的str类型是Unicode字符串，Python 2的str类型是字节串，相当于Python 3中的bytes。Python 3中的比较运算符必须比较同类对象。Python 3中定义类的都是新式类，Python 2中定义的类有新式类（显式继承自object的类）和旧式类（经典类）之分，新式类和旧式类在MRO问题上有非常显著的区别，新式类可以使用__class__属性获取自身类型，新式类可以使用__slots__魔法。Python 3对代码缩进的要求更加严格，如果混用空格和制表键会引发TabError。Python 3中字典的keys、values、items方法都不再返回list对象，而是返回view object，内置的map、filter等函数也不再返回list对象，而是返回迭代器对象。Python 3标准库中某些模块的名字跟Python 2是有区别的；而在三方库方面，有些三方库只支持Python 2，有些只能支持Python 3。题目31：谈谈你对“猴子补丁”（monkey patching）的理解。“猴子补丁”是动态类型语言的一个特性，代码运行时在不修改源代码的前提下改变代码中的方法、属性、函数等以达到热补丁（hot patch）的效果。很多系统的安全补丁也是通过猴子补丁的方式来实现的，但实际开发中应该避免对猴子补丁的使用，以免造成代码行为不一致的问题。在使用gevent库的时候，我们会在代码开头的地方执行gevent.monkey.patch_all()，这行代码的作用是把标准库中的socket模块给替换掉，这样我们在使用socket的时候，不用修改任何代码就可以实现对代码的协程化，达到提升性能的目的，这就是对猴子补丁的应用。另外，如果希望用ujson三方库替换掉标准库中的json，也可以使用猴子补丁的方式，代码如下所示。import json, ujson json.__name__ = 'ujson' json.dumps = ujson.dumps json.loads = ujson.loads单元测试中的Mock技术也是对猴子补丁的应用，Python中的unittest.mock模块就是解决单元测试中用Mock对象替代被测对象所依赖的对象的模块。题目32：阅读下面的代码说出运行结果。class A: def who(self): print('A', end='') class B(A): def who(self): super(B, self).who() print('B', end='') class C(A): def who(self): super(C, self).who() print('C', end='') class D(B, C): def who(self): super(D, self).who() print('D', end='') item = D() item.who()点评：这道题考查到了两个知识点：Python中的MRO（方法解析顺序）。在没有多重继承的情况下，向对象发出一个消息，如果对象没有对应的方法，那么向上（父类）搜索的顺序是非常清晰的。如果向上追溯到object类（所有类的父类）都没有找到对应的方法，那么将会引发AttributeError异常。但是有多重继承尤其是出现菱形继承（钻石继承）的时候，向上追溯到底应该找到那个方法就得确定MRO。Python 3中的类以及Python 2中的新式类使用C3算法来确定MRO，它是一种类似于广度优先搜索的方法；Python 2中的旧式类（经典类）使用深度优先搜索来确定MRO。在搞不清楚MRO的情况下，可以使用类的mro方法或__mro__属性来获得类的MRO列表。super()函数的使用。在使用super函数时，可以通过super(类型, 对象)来指定对哪个对象以哪个类为起点向上搜索父类方法。所以上面B类代码中的super(B, self).who()表示以B类为起点，向上搜索self（D类对象）的who方法，所以会找到C类中的who方法，因为D类对象的MRO列表是D --> B --> C --> A --> object。ACBD题目33：编写一个函数实现对逆波兰表达式求值，不能使用Python的内置函数。点评：逆波兰表达式也称为“后缀表达式”，相较于平常我们使用的“中缀表达式”，逆波兰表达式不需要括号来确定运算的优先级，例如5 * (2 + 3)对应的逆波兰表达式是5 2 3 + *。逆波兰表达式求值需要借助栈结构，扫描表达式遇到运算数就入栈，遇到运算符就出栈两个元素做运算，将运算结果入栈。表达式扫描结束后，栈中只有一个数，这个数就是最终的运算结果，直接出栈即可。import operator class Stack: """栈（FILO）""" def __init__(self): self.elems = [] def push(self, elem): """入栈""" self.elems.append(elem) def pop(self): """出栈""" return self.elems.pop() @property def is_empty(self): """检查栈是否为空""" return len(self.elems) == 0 def eval_suffix(expr): """逆波兰表达式求值""" operators = { '+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv } stack = Stack() for item in expr.split(): if item.isdigit(): stack.push(float(item)) else: num2 = stack.pop() num1 = stack.pop() stack.push(operators[item](num1, num2)) return stack.pop()题目34：Python中如何实现字符串替换操作？Python中实现字符串替换大致有两类方法：字符串的replace方法和正则表达式的sub方法。方法一：使用字符串的replace方法。message = 'hello, world!' print(message.replace('o', 'O').replace('l', 'L').replace('he', 'HE'))方法二：使用正则表达式的sub方法。import re message = 'hello, world!' pattern = re.compile('[aeiou]') print(pattern.sub('#', message))扩展：还有一个相关的面试题，对保存文件名的列表排序，要求文件名按照字母表和数字大小进行排序，例如对于列表filenames = ['a12.txt', 'a8.txt', 'b10.txt', 'b2.txt', 'b19.txt', 'a3.txt'] ，排序的结果是['a3.txt', 'a8.txt', 'a12.txt', 'b2.txt', 'b10.txt', 'b19.txt']。提示一下，可以通过字符串替换的方式为文件名补位，根据补位后的文件名用sorted函数来排序，大家可以思考下这个问题如何解决。题目35：如何剖析Python代码的执行性能？剖析代码性能可以使用Python标准库中的cProfile和pstats模块，cProfile的run函数可以执行代码并收集统计信息，创建出Stats对象并打印简单的剖析报告。Stats是pstats模块中的类，它是一个统计对象。当然，也可以使用三方工具line_profiler和memory_profiler来剖析每一行代码耗费的时间和内存，这两个三方工具都会用非常友好的方式输出剖析结构。如果使用PyCharm，可以利用“Run”菜单的“Profile”菜单项对代码进行性能分析，PyCharm中可以用表格或者调用图（Call Graph）的方式来显示性能剖析的结果。下面是使用cProfile剖析代码性能的例子。example.pyimport cProfile def is_prime(num): for factor in range(2, int(num ** 0.5) + 1): if num % factor == 0: return False return True class PrimeIter: def __init__(self, total): self.counter = 0 self.current = 1 self.total = total def __iter__(self): return self def __next__(self): if self.counter < self.total: self.current += 1 while not is_prime(self.current): self.current += 1 self.counter += 1 return self.current raise StopIteration() cProfile.run('list(PrimeIter(10000))')如果使用line_profiler三方工具，可以直接剖析is_prime函数每行代码的性能，需要给is_prime函数添加一个profiler装饰器，[email protected] def is_prime(num): for factor in range(2, int(num ** 0.5) + 1): if num % factor == 0: return False return True安装line_profiler。pip install line_profiler使用line_profiler。kernprof -lv example.py运行结果如下所示。Line # Hits Time Per Hit % Time Line Contents ============================================================== 1 @profile 2 def is_prime(num): 3 86624 48420.0 0.6 50.5 for factor in range(2, int(num ** 0.5) + 1): 4 85624 44000.0 0.5 45.9 if num % factor == 0: 5 6918 3080.0 0.4 3.2 return False 6 1000 430.0 0.4 0.4 return True题目36：如何使用random模块生成随机数、实现随机乱序和随机抽样？点评：送人头的题目，因为Python标准库中的常用模块应该是Python开发者都比较熟悉的内容，这个问题回如果答不上来，整个面试基本也就砸锅了。random.random()函数可以生成[0.0, 1.0)之间的随机浮点数。random.uniform(a, b)函数可以生成[a, b]或[b, a]之间的随机浮点数。random.randint(a, b)函数可以生成[a, b]或[b, a]之间的随机整数。random.shuffle(x)函数可以实现对序列x的原地随机乱序。random.choice(seq)函数可以从非空序列中取出一个随机元素。random.choices(population, weights=None, *, cum_weights=None, k=1)函数可以从总体中随机抽取（有放回抽样）出容量为k的样本并返回样本的列表，可以通过参数指定个体的权重，如果没有指定权重，个体被选中的概率均等。random.sample(population, k)函数可以从总体中随机抽取（无放回抽样）出容量为k的样本并返回样本的列表。扩展：random模块提供的函数除了生成均匀分布的随机数外，还可以生成其他分布的随机数，例如random.gauss(mu, sigma)函数可以生成高斯分布（正态分布）的随机数；random.paretovariate(alpha)函数会生成帕累托分布的随机数；random.gammavariate(alpha, beta)函数会生成伽马分布的随机数。题目37：解释一下线程池的工作原理。点评：池化技术就是一种典型空间换时间的策略，我们使用的数据库连接池、线程池等都是池化技术的应用，Python标准库currrent.futures模块的ThreadPoolExecutor就是线程池的实现，如果要弄清楚它的工作原理，可以参考下面的内容。线程池是一种用于减少线程本身创建和销毁造成的开销的技术，属于典型的空间换时间操作。如果应用程序需要频繁的将任务派发到线程中执行，线程池就是必选项，因为创建和释放线程涉及到大量的系统底层操作，开销较大，如果能够在应用程序工作期间，将创建和释放线程的操作变成预创建和借还操作，将大大减少底层开销。线程池在应用程序启动后，立即创建一定数量的线程，放入空闲队列中。这些线程最开始都处于阻塞状态，不会消耗CPU资源，但会占用少量的内存空间。当任务到来后，从队列中取出一个空闲线程，把任务派发到这个线程中运行，并将该线程标记为已占用。当线程池中所有的线程都被占用后，可以选择自动创建一定数量的新线程，用于处理更多的任务，也可以选择让任务排队等待直到有空闲的线程可用。在任务执行完毕后，线程并不退出结束，而是继续保持在池中等待下一次的任务。当系统比较空闲时，大部分线程长时间处于闲置状态时，线程池可以自动销毁一部分线程，回收系统资源。基于这种预创建技术，线程池将线程创建和销毁本身所带来的开销分摊到了各个具体的任务上，执行次数越多，每个任务所分担到的线程本身开销则越小。一般线程池都必须具备下面几个组成部分：线程池管理器：用于创建并管理线程池。工作线程和线程队列：线程池中实际执行的线程以及保存这些线程的容器。任务接口：将线程执行的任务抽象出来，形成任务接口，确保线程池与具体的任务无关。任务队列：线程池中保存等待被执行的任务的容器。题目38：举例说明什么情况下会出现KeyError、TypeError、ValueError。举一个简单的例子，变量a是一个字典，执行int(a['x'])这个操作就有可能引发上述三种类型的异常。如果字典中没有键x，会引发KeyError；如果键x对应的值不是str、float、int、bool以及bytes-like类型，在调用int函数构造int类型的对象时，会引发TypeError；如果a[x]是一个字符串或者字节串，而对应的内容又无法处理成int时，将引发ValueError。题目39：说出下面代码的运行结果。def extend_list(val, items=[]): items.append(val) return items list1 = extend_list(10) list2 = extend_list(123, []) list3 = extend_list('a') print(list1) print(list2) print(list3)点评：Python函数在定义的时候，默认参数items的值就被计算出来了，即[]。因为默认参数items引用了对象[]，每次调用该函数，如果对items引用的列表进行了操作，下次调用时，默认参数还是引用之前的那个列表而不是重新赋值为[]，所以列表中会有之前添加的元素。如果通过传参的方式为items重新赋值，那么items将引用到新的列表对象，而不再引用默认的那个列表对象。这个题在面试中经常被问到，通常不建议使用容器类型的默认参数，像PyLint这样的代码检查工具也会对这种代码提出质疑和警告。[10, 'a'] [123] [10, 'a']题目40：如何读取大文件，例如内存只有4G，如何读取一个大小为8G的文件？很显然4G内存要一次性的加载大小为8G的文件是不现实的，遇到这种情况必须要考虑多次读取和分批次处理。在Python中读取文件可以先通过open函数获取文件对象，在读取文件时，可以通过read方法的size参数指定读取的大小，也可以通过seek方法的offset参数指定读取的位置，这样就可以控制单次读取数据的字节数和总字节数。除此之外，可以使用内置函数iter将文件对象处理成迭代器对象，每次只读取少量的数据进行处理，代码大致写法如下所示。with open('...', 'rb') as file: for data in iter(lambda: file.read(2097152), b''): pass在Linux系统上，可以通过split命令将大文件切割为小片，然后通过读取切割后的小文件对数据进行处理。例如下面的命令将名为filename的大文件切割为大小为512M的多个文件。split -b 512m filename如果愿意， 也可以将名为filename的文件切割为10个文件，命令如下所示。split -n 10 filename扩展：外部排序跟上述的情况非常类似，由于处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。“排序-归并算法”就是一种常用的外部排序策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件，然后在归并阶段将这些临时文件组合为一个大的有序文件，这个大的有序文件就是排序的结果。题目41：说一下你对Python中模块和包的理解。每个Python文件就是一个模块，而保存这些文件的文件夹就是一个包，但是这个作为Python包的文件夹必须要有一个名为__init__.py的文件，否则无法导入这个包。通常一个文件夹下还可以有子文件夹，这也就意味着一个包下还可以有子包，子包中的__init__.py并不是必须的。模块和包解决了Python中命名冲突的问题，不同的包下可以有同名的模块，不同的模块下可以有同名的变量、函数或类。在Python中可以使用import或from ... import ...来导入包和模块，在导入的时候还可以使用as关键字对包、模块、类、函数、变量等进行别名，从而彻底解决编程中尤其是多人协作团队开发时的命名冲突问题。题目42：说一下你知道的Python编码规范。点评：企业的Python编码规范基本上是参照PEP-8来制定的，后者还提到了可以使用Lint工具来检查代码的规范程度，面试的时候遇到这类问题，可以先说下这两个参照标准，然后挑重点说一下Python编码的注意事项。空格的使用使用空格来表示缩进而不要用制表符（Tab）。和语法相关的每一层缩进都用4个空格来表示。每行的字符数不要超过79个字符，如果表达式因太长而占据了多行，除了首行之外的其余各行都应该在正常的缩进宽度上再加上4个空格。函数和类的定义，代码前后都要用两个空行进行分隔。在同一个类中，各个方法之间应该用一个空行进行分隔。二元运算符的左右两侧应该保留一个空格，而且只要一个空格就好。标识符命名变量、函数和属性应该使用小写字母来拼写，如果有多个单词就使用下划线进行连接。类中受保护的实例属性，应该以一个下划线开头。类中私有的实例属性，应该以两个下划线开头。类和异常的命名，应该每个单词首字母大写。模块级别的常量，应该采用全大写字母，如果有多个单词就用下划线进行连接。类的实例方法，应该把第一个参数命名为self以表示对象自身。类的类方法，应该把第一个参数命名为cls以表示该类自身。表达式和语句采用内联形式的否定词，而不要把否定词放在整个表达式的前面。例如：if a is not b就比if not a is b更容易让人理解。不要用检查长度的方式来判断字符串、列表等是否为None或者没有元素，应该用if not x这样的写法来检查它。就算if分支、for循环、except异常捕获等中只有一行代码，也不要将代码和if、for、except等写在一起，分开写才会让代码更清晰。import语句总是放在文件开头的地方。引入模块的时候，from math import sqrt比import math更好。如果有多个import语句，应该将其分为三部分，从上到下分别是Python标准模块、第三方模块和自定义模块，每个部分内部应该按照模块名称的字母表顺序来排列。题目43：运行下面的代码是否会报错，如果报错请说明哪里有什么样的错，如果不报错请说出代码的执行结果。class A: def __init__(self, value): self.__value = value @property def value(self): return self.__value obj = A(1) obj.__value = 2 print(obj.value) print(obj.__value)点评：这道题有两个考察点，一个考察点是对_和__开头的对象属性访问权限以及@property装饰器的了解，另外一个考察的点是对动态语言的理解，不需要过多的解释。1 2扩展：如果不希望代码运行时动态的给对象添加新属性，可以在定义类时使用__slots__魔法。例如，我们可以在上面的A中添加一行__slots__ = ('__value', )，再次运行上面的代码，将会在原来的第10行处产生AttributeError错误。题目44：对下面给出的字典按值从大到小对键进行排序。prices = { 'AAPL': 191.88, 'GOOG': 1186.96, 'IBM': 149.24, 'ORCL': 48.44, 'ACN': 166.89, 'FB': 208.09, 'SYMC': 21.29 }点评：sorted函数的高阶用法在面试的时候经常出现，key参数可以传入一个函数名或一个Lambda函数，该函数的返回值代表了在排序时比较元素的依据。sorted(prices, key=lambda x: prices[x], reverse=True) 题目45：说一下namedtuple的用法和作用。点评：Python标准库的collections模块提供了很多有用的数据结构，这些内容并不是每个开发者都清楚，就比如题目问到的namedtuple，在我参加过的面试中，90%的面试者都不能准确的说出它的作用和应用场景。此外，deque也是一个非常有用但又经常被忽视的类，还有Counter、OrderedDict 、defaultdict 、UserDict等类，大家清楚它们的用法吗？在使用面向对象编程语言的时候，定义类是最常见的一件事情，有的时候，我们会用到只有属性没有方法的类，这种类的对象通常只用于组织数据，并不能接收消息，所以我们把这种类称为数据类或者退化的类，就像C语言中的结构体那样。我们并不建议使用这种退化的类，在Python中可以用namedtuple（命名元组）来替代这种类。from collections import namedtuple Card = namedtuple('Card', ('suite', 'face')) card1 = Card('红桃', 13) card2 = Card('草花', 5) print(f'{card1.suite}{card1.face}') print(f'{card2.suite}{card2.face}')命名元组与普通元组一样是不可变容器，一旦将数据存储在namedtuple的顶层属性中，数据就不能再修改了，也就意味着对象上的所有属性都遵循“一次写入，多次读取”的原则。和普通元组不同的是，命名元组中的数据有访问名称，可以通过名称而不是索引来获取保存的数据，不仅在操作上更加简单，代码的可读性也会更好。命名元组的本质就是一个类，所以它还可以作为父类创建子类。除此之外，命名元组内置了一系列的方法，例如，可以通过_asdict方法将命名元组处理成字典，也可以通过_replace方法创建命名元组对象的浅拷贝。class MyCard(Card): def show(self): faces = ['', 'A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K'] return f'{self.suite}{faces[self.face]}' print(Card) # <class '__main__.Card'> card3 = MyCard('方块', 12) print(card3.show()) # 方块Q print(dict(card1._asdict())) # {'suite': '红桃', 'face': 13} print(card2._replace(suite='方块')) # Card(suite='方块', face=5)总而言之，命名元组能更好的组织数据结构，让代码更加清晰和可读，在很多场景下是元组、字典和数据类的替代品。在需要创建占用空间更少的不可变类时，命名元组就是很好的选择。题目46：按照题目要求写出对应的函数。要求：写一个函数，传入一个有若干个整数的列表，该列表中某个元素出现的次数超过了50%，返回这个元素。def more_than_half(items): temp, times = None, 0 for item in items: if times == 0: temp = item times += 1 else: if item == temp: times += 1 else: times -= 1 return temp点评：LeetCode上的题目，在Python面试中出现过，利用元素出现次数超过了50%这一特征，出现和temp相同的元素就将计数值加1，出现和temp不同的元素就将计数值减1。如果计数值为0，说明之前出现的元素已经对最终的结果没有影响，用temp记下当前元素并将计数值置为1。最终，出现次数超过了50%的这个元素一定会被赋值给变量temp。题目47：按照题目要求写出对应的函数。要求：写一个函数，传入的参数是一个列表（列表中的元素可能也是一个列表），返回该列表最大的嵌套深度。例如：列表[1, 2, 3]的嵌套深度为1，列表[[1], [2, [3]]]的嵌套深度为3。def list_depth(items): if isinstance(items, list): max_depth = 1 for item in items: max_depth = max(list_depth(item) + 1, max_depth) return max_depth return 0点评：看到题目应该能够比较自然的想到使用递归的方式检查列表中的每个元素。题目48：按照题目要求写出对应的装饰器。要求：有一个通过网络获取数据的函数（可能会因为网络原因出现异常），写一个装饰器让这个函数在出现指定异常时可以重试指定的次数，并在每次重试之前随机延迟一段时间，最长延迟时间可以通过参数进行控制。方法一：from functools import wraps from random import random from time import sleep def retry(*, retry_times=3, max_wait_secs=5, errors=(Exception, )): def decorate(func): @wraps(func) def wrapper(*args, **kwargs): for _ in range(retry_times): try: return func(*args, **kwargs) except errors: sleep(random() * max_wait_secs) return None return wrapper return decorate方法二：from functools import wraps from random import random from time import sleep class Retry(object): def __init__(self, *, retry_times=3, max_wait_secs=5, errors=(Exception, )): self.retry_times = retry_times self.max_wait_secs = max_wait_secs self.errors = errors def __call__(self, func): @wraps(func) def wrapper(*args, **kwargs): for _ in range(self.retry_times): try: return func(*args, **kwargs) except self.errors: sleep(random() * self.max_wait_secs) return None return wrapper点评：我们不止一次强调过，装饰器几乎是Python面试必问内容，这个题目比之前的题目稍微复杂一些，它需要的是一个参数化的装饰器。题目49：写一个函数实现字符串反转，尽可能写出你知道的所有方法。点评：烂大街的题目，基本上算是送人头的题目。方法一：反向切片def reverse_string(content): return content[::-1]方法二：反转拼接def reverse_string(content): return ''.join(reversed(content))方法三：递归调用def reverse_string(content): if len(content) <= 1: return content return reverse_string(content[1:]) + content[0]方法四：双端队列from collections import deque def reverse_string(content): q = deque() q.extendleft(content) return ''.join(q)方法五：反向组装from io import StringIO def reverse_string(content): buffer = StringIO() for i in range(len(content) - 1, -1, -1): buffer.write(content[i]) return buffer.getvalue()方法六：反转拼接def reverse_string(content): return ''.join([content[i] for i in range(len(content) - 1, -1, -1)])方法七：半截交换def reverse_string(content): length, content= len(content), list(content) for i in range(length // 2): content[i], content[length - 1 - i] = content[length - 1 - i], content[i] return ''.join(content)方法八：对位交换def reverse_string(content): length, content= len(content), list(content) for i, j in zip(range(length // 2), range(length - 1, length // 2 - 1, -1)): content[i], content[j] = content[j], content[i] return ''.join(content)扩展：这些方法其实都是大同小异的，面试的时候能够给出几种有代表性的就足够了。给大家留一个思考题，上面这些方法，哪些做法的性能较好呢？我们之前提到过剖析代码性能的方法，大家可以用这些方法来检验下你给出的答案是否正确。题目50：按照题目要求写出对应的函数。要求：列表中有1000000个元素，取值范围是[1000, 10000)，设计一个函数找出列表中的重复元素。def find_dup(items: list): dups = [0] * 9000 for item in items: dups[item - 1000] += 1 for idx, val in enumerate(dups): if val > 1: yield idx + 1000点评：这道题的解法和计数排序的原理一致，虽然元素的数量非常多，但是取值范围[1000, 10000)并不是很大，只有9000个可能的取值，所以可以用一个能够保存9000个元素的dups列表来记录每个元素出现的次数，dups列表所有元素的初始值都是0，通过对items列表中元素的遍历，当出现某个元素时，将dups列表对应位置的值加1，最后dups列表中值大于1的元素对应的就是items列表中重复出现过的元素。Github原文链接：https://github.com/jackfrued/Python-Interview-Bible
-
数据库事务的概念及其实现原理 1.认识事务1.1为什么需要数据库事务转账是生活中常见的操作,比如从A账户转账100元到B账号。站在用户角度而言,这是一个逻辑上的单一操作,然而在数据库系统中,至少会分成两个步骤来完成:将A账户的金额减少100元将B账户的金额增加100元在这个过程中可能会出现以下问题:转账操作的第一步执行成功,A账户上的钱减少了100元,但是第二步执行失败或者未执行便发生系统崩溃,导致B账户并没有相应增加100元。转账操作刚完成就发生系统崩溃,系统重启恢复时丢失了崩溃前的转账记录。同时又另一个用户转账给B账户,由于同时对B账户进行操作,导致B账户金额出现异常。为了便于解决这些问题,需要引入数据库事务的概念。1.2什么是数据库事务定义:数据库事务是构成单一逻辑工作单元的操作集合一个典型的数据库事务如下所示BEGIN TRANSACTION //事务开始 SQL1 SQL2 COMMIT/ROLLBACK //事务提交或回滚关于事务的定义有几点需要解释下：数据库事务可以包含一个或多个数据库操作,但这些操作构成一个逻辑上的整体。构成逻辑整体的这些数据库操作,要么全部执行成功,要么全部不执行。构成事务的所有操作,要么全都对数据库产生影响,要么全都不产生影响,即不管事务是否执行成功,数据库总能保持一致性状态。以上即使在数据库出现故障以及并发事务存在的情况下依然成立。1.3 事务如何解决问题对于上面的转账例子,可以将转账相关的所有操作包含在一个事务中BEGIN TRANSACTION A账户减少100元 B账户增加100元 COMMIT当数据库操作失败或者系统出现崩溃,系统能够以事务为边界进行恢复,不会出现A账户金额减少而B账户未增加的情况。当有多个用户同时操作数据库时,数据库能够以事务为单位进行并发控制,使多个用户对B账户的转账操作相互隔离。事务使系统能够更方便的进行故障恢复以及并发控制,从而保证数据库状态的一致性。1.4 事务的ACID特性以及实现原理概述原子性(Atomicity):事务中的所有操作作为一个整体像原子一样不可分割，要么全部成功,要么全部失败。一致性(Consistency):事务的执行结果必须使数据库从一个一致性状态到另一个一致性状态。一致性状态是指:系统的状态满足数据的完整性约束(主码,参照完整性,check约束等)系统的状态反应数据库本应描述的现实世界的真实状态,比如转账前后两个账户的金额总和应该保持不变。隔离性(Isolation):并发执行的事务不会相互影响,其对数据库的影响和它们串行执行时一样。比如多个用户同时往一个账户转账,最后账户的结果应该和他们按先后次序转账的结果一样。持久性(Durability):事务一旦提交,其对数据库的更新就是持久的。任何事务或系统故障都不会导致数据丢失。在事务的ACID特性中,C即一致性是事务的根本追求,而对数据一致性的破坏主要来自两个方面事务的并发执行事务故障或系统故障数据库系统是通过并发控制技术和日志恢复技术来避免这种情况发生的。并发控制技术保证了事务的隔离性,使数据库的一致性状态不会因为并发执行的操作被破坏。日志恢复技术保证了事务的原子性,使一致性状态不会因事务或系统故障被破坏。同时使已提交的对数据库的修改不会因系统崩溃而丢失,保证了事务的持久性。2 并发异常与并发控制技术2.1 常见的并发异常在讲解并发控制技术前,先简单介绍下数据库常见的并发异常脏写：脏写是指事务回滚了其他事务对数据项的已提交修改,比如下面这种情况在事务1对数据A的回滚,导致事务2对A的已提交修改也被回滚了丢失更新：丢失更新是指事务覆盖了其他事务对数据的已提交修改,导致这些修改好像丢失了一样事务1和事务2读取A的值都为10,事务2先将A加上10并提交修改,之后事务2将A减少10并提交修改,A的值最后为,导致事务2对A的修改好像丢失了一样脏读：脏读是指一个事务读取了另一个事务未提交的数据在事务1对A的处理过程中,事务2读取了A的值,但之后事务1回滚,导致事务2读取的A是未提交的脏数据。不可重复读：不可重复读是指一个事务对同一数据的读取结果前后不一致。脏读和不可重复读的区别在于:前者读取的是事务未提交的脏数据,后者读取的是事务已经提交的数据,只不过因为数据被其他事务修改过导致前后两次读取的结果不一样,比如下面这种情况由于事务2对A的已提交修改,事务1前后两次读取的结果不一致幻读：幻读是指事务读取某个范围的数据时，因为其他事务的操作导致前后两次读取的结果不一致。幻读和不可重复读的区别在于,不可重复读是针对确定的某一行数据而言,而幻读是针对不确定的多行数据。因而幻读通常出现在带有查询条件的范围查询中,比如下面这种情况事务1查询A<5的数据,由于事务2插入了一条A=4的数据,导致事务1两次查询得到的结果不一样2.2 事务的隔离级别事务具有隔离性,理论上来说事务之间的执行不应该相互产生影响,其对数据库的影响应该和它们串行执行时一样。然而完全的隔离性会导致系统并发性能很低,降低对资源的利用率,因而实际上对隔离性的要求会有所放宽,这也会一定程度造成对数据库一致性要求降低SQL标准为事务定义了不同的隔离级别,从低到高依次是读未提交(READ UNCOMMITTED)读已提交(READ COMMITTED)可重复读(REPEATABLE READ)串行化(SERIALIZABLE)事务的隔离级别越低,可能出现的并发异常越多,但是通常而言系统能提供的并发能力越强。不同的隔离级别与可能的并发异常的对应情况如下表所示,有一点需要强调,这种对应关系只是理论上的,对于特定的数据库实现不一定准确,比如mysql的Innodb存储引擎通过Next-Key Locking技术在可重复读级别就消除了幻读的可能。所有事务隔离级别都不允许出现脏写,而串行化可以避免所有可能出现的并发异常,但是会极大的降低系统的并发处理能力2.3 事务隔离性的实现——常见的并发控制技术并发控制技术是实现事务隔离性以及不同隔离级别的关键,实现方式有很多,按照其对可能冲突的操作采取的不同策略可以分为乐观并发控制和悲观并发控制两大类。乐观并发控制:对于并发执行可能冲突的操作,假定其不会真的冲突,允许并发执行,直到真正发生冲突时才去解决冲突,比如让事务回滚。悲观并发控制:对于并发执行可能冲突的操作,假定其必定发生冲突,通过让事务等待(锁)或者中止(时间戳排序)的方式使并行的操作串行执行。2.3.1 基于封锁的并发控制2.3.2 基于时间戳的并发控制2.3.3 基于有效性检查的并发控制2.3.4 基于快照隔离的并发控制2.3.5 关于并发控制技术的总结原文链接：https://www.cnblogs.com/takumicx/p/9998844.html
-
vite2.1 最新alias别名设置方式 vite.config.js 别名配置resolve.alias类型： Record<string, string> | Array<{ find: string | RegExp, replacement: string }>将会被传递到 @rollup/plugin-alias 作为 entries 的选项。也可以是一个对象，或一个 { find, replacement } 的数组.当使用文件系统路径的别名时，请始终使用绝对路径。相对路径的别名值会被原封不动地使用，因此无法被正常解析。更高级的自定义解析方法可以通过 插件 实现。import { defineConfig } from 'vite' import path from "path"; import vue from [email protected]/plugin-vue' // https://vitejs.dev/config/ export default defineConfig({ resolve: { alias: { "@": path.resolve(__dirname, "src"), "components": path.resolve(__dirname, "src/components"), "styles": path.resolve(__dirname, "src/styles"), "plugins": path.resolve(__dirname, "src/plugins"), "views": path.resolve(__dirname, "src/views"), "layouts": path.resolve(__dirname, "src/layouts"), "utils": path.resolve(__dirname, "src/utils"), "apis": path.resolve(__dirname, "src/apis"), "dirs": path.resolve(__dirname, "src/directives"), }, }, plugins: [vue()], });或者 数组的形式 import { defineConfig } from 'vite' import path from "path"; import vue from [email protected]/plugin-vue' // https://vitejs.dev/config/ export default defineConfig({ resolve: { alias: [{ find: '@', replacement: path.resolve(__dirname, 'src') }, { find: 'components', replacement: path.resolve(__dirname, 'src/components') } ], }, plugins: [vue()], });注意要导入path啊，还有vite.config配置要关项目重启————————————————版权声明：本文为CSDN博主「yusirxiaer」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/yusirxiaer/article/details/115440738
