注意

该文件中的代码存在 Python2 和 Python3 共存的问题，需要读者根据自己使用的 Python 版本进行相应调整。

Python 语言特性

Python 的函数参数传递

看两个例子:

a = 1
def fun(a):
    a = 2
fun(a)
print(a)  # 1

a = []
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 中，str， tuple 和 number 是不可更改的对象，而 list， dict， set 等则是可以修改的对象。 (这就是这个问题的重点)

当一个引用传递给函数的时候，函数自动复制一份引用，这个函数里的引用和外边的引用没有半毛关系了。所以第一个例子里函数把引用指向了一个不可变对象，当函数返回的时候，外面的引用没半毛感觉。而第二个例子就不一样了，函数内的引用指向的是可变对象，对它的操作就和定位了指针地址一样，在内存里进行修改。

如果还不明白的话，这里有更好的解释:

• python - How do I pass a variable by reference? - Stack Overflow (opens new window)

• Is Python pass-by-reference or pass-by-value? (opens new window)

  • Python 传值还是传引用？| 通过对象引用传递 | 别院牧志 (opens new window)

• Python pass by reference or value? (opens new window)

特殊的，对于元祖，可参考：https://inventwithpython.com/blog/2018/02/05/python-tuples-are-immutable-except-when-theyre-mutable/ (opens new window)

Python 中的元类(metaclass)

这个非常的不常用，但是像 ORM 这种复杂的结构还是会需要的，详情请看：Python 中的元类

@staticmethod 和@classmethod

Python 其实有 3 个方法，即静态方法(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 的约定是这俩,还是不要改的好。

对于实例方法，调用时会把实例instance作为第一个参数传递给 self 参数。因此，调用instance.foo(1)时输出了实例 ik 的地址。

对于类方法，调用时会把类class作为第一个参数传递给 cls 参数。因此，调用instance.class_foo(1)时输出了class类型信息，所以可以通过类也可以通过实例来调用类方法。

• 类方法

类方法使用 @classmethod 装饰器来定义，第一个参数是 cls，表示类本身。 类方法可以通过类直接调用，也可以通过实例调用。 类方法可以访问和修改类属性，但不能访问和修改实例属性。 类方法可以用来创建工厂函数，从而创建类的实例。

• 静态方法

静态方法使用 @staticmethod 装饰器来定义，没有特殊的参数。 静态方法可以通过类直接调用，也可以通过实例调用。 静态方法不能访问和修改类属性和实例属性。 静态方法通常用于定义不依赖于类或实例状态的函数，可以在没有创建类实例时直接使用。

• 总结

类方法可以访问和修改类属性，而静态方法不能。静态方法通常用于不依赖于类或实例状态的操作，而类方法在处理和操作类相关的属性和方法时更加方便。

对于静态方法，调用时并不需要传递类或者实例。其实，静态方法很像我们在类外定义的函数，只不过静态方法可以通过类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)

更多关于这个问题的讨论：

1. python - Difference between staticmethod and classmethod - StackOverflow (opens new window)
2. https://realpython.com/blog/python/instance-class-and-static-methods-demystified/ (opens new window)
3. Python 实例方法、类方法和静态方法_Leo 的博客-CSDN 博客 (opens new window)

一个应用示例：

class DateMaker:

    def __init__(self,year=0,month=0,day=0):
        self.year = year
        self.month = month
        self.day = day

    def date_out(self):
        print('year:{y},month:{m},day:{d}'.format(y=self.year,m=self.month,d=self.day))

    @classmethod
    def make_date(cls,date_string):
        date = None
        if '-' in date_string:
            y,m,d = date_string.split('-')
            date = cls(y,m,d)
        return date

if __name__ == '__main__':
    r=DateMaker.make_date("2019-09-16")
    r.date_out()

类变量和实例变量

类变量：

可在类的所有实例之间共享的值（也就是说，它们不是单独分配给每个实例的）。例如下例中，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]

当类变量值为可变对象（列表、字典等）时，共享类变量可能会造成意外的结果。

为了避免变量混淆，推荐使用 self 来定义实例变量，使用类名或 cls 来定义类变量。对于可变对象的类变量，可以在类定义时使用深复制来避免共享。

Python 自省与反射

Python 中的 自省（Introspection） 和 反射（Reflection） 是动态获取和操作对象信息的机制，它们是 Python 动态特性的重要体现。

1. 自省（Introspection）

自省是指程序在运行时能够查看对象的类型、属性、方法等信息。Python 提供了多种工具来实现自省。

常用自省工具

方法	作用
help()	查看函数或模块用途的详细说明
dir()	返回对象所有属性
type()	查看对象类型
hasattr()	查看对象是否有特定属性
getattr()	得到对象的特定属性
setattr()	设置对象的特定属性
isinstance()	判断一个对象是否是一个已知的类型
issubclass()	判断一个类是不是另一个类的子类
id()	返回地址值
callable()	判断对象是否可调用

• type()：获取对象的类型。

  num = 42
  print(type(num))  # 输出: <class 'int'>
  

• isinstance()：检查对象是否是某个类的实例。

  print(isinstance(num, int))  # 输出: True
  

• dir()：返回对象的所有属性和方法。

  print(dir(num))  # 输出: ['__abs__', '__add__', ...]
  

• hasattr()：检查对象是否具有某个属性或方法。

  print(hasattr(num, '__add__'))  # 输出: True
  

• getattr()：获取对象的属性或方法。

  print(getattr(num, '__add__'))  # 输出: <method-wrapper '__add__' of int object at 0x...>
  

• id()：获取对象的内存地址。

  print(id(num))  # 输出: 内存地址（如 140735784123456）
  

2. 反射（Reflection）

反射是指程序在运行时可以动态地修改对象的状态或行为。Python 的反射能力非常强大，允许动态访问、修改和调用对象的属性和方法。

常用反射工具

• setattr()：动态设置对象的属性。

  class MyClass:
      pass
  
  obj = MyClass()
  setattr(obj, 'new_attr', 100)  # 动态添加属性
  print(obj.new_attr)  # 输出: 100
  

• delattr()：动态删除对象的属性。

  delattr(obj, 'new_attr')  # 删除属性
  print(hasattr(obj, 'new_attr'))  # 输出: False
  

• getattr()：动态获取对象的属性或方法。

  class MyClass:
      def greet(self):
          return "Hello!"
  
  obj = MyClass()
  method = getattr(obj, 'greet')  # 获取方法
  print(method())  # 输出: Hello!
  

• 动态调用方法：通过反射调用对象的方法。

  method_name = 'greet'
  if hasattr(obj, method_name):
      method = getattr(obj, method_name)
      print(method())  # 输出: Hello!
  

3. 自省与反射的区别

特性	自省（Introspection）	反射（Reflection）
目的	查看对象的类型、属性、方法等信息	动态修改对象的状态或行为
工具	type()、dir()、hasattr() 等	setattr()、getattr() 等
动态性	只读操作	可读写操作

4. 实际应用场景

• 插件系统：通过反射动态加载和调用插件。
• 配置文件驱动：根据配置文件动态调用类或方法。
• 调试工具：通过自省查看对象的状态。
• ORM（对象关系映射）：动态生成和操作数据库模型。

5. 示例：动态调用方法

class Calculator:
    def add(self, a, b):
        return a + b

    def subtract(self, a, b):
        return a - b

calc = Calculator()
method_name = input("Enter method name (add/subtract): ")  # 用户输入方法名
if hasattr(calc, method_name):
    method = getattr(calc, method_name)
    result = method(10, 5)  # 动态调用方法
    print(f"Result: {result}")
else:
    print("Method not found!")

---

6. 总结

• 自省：查看对象的类型、属性和方法。
• 反射：动态修改对象的状态或行为。
• Python 的自省和反射机制使其具有极高的灵活性和动态性，广泛应用于框架开发、插件系统等场景。

python 自省与反射_面向对象的笔记-CSDN 博客 (opens new window)

字典推导式

可能你见过列表推导式，却没有见过字典推导式，在 2.7 中才加入的:

d = {key: value*2 for key, value in iterable.items()}

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 这样的方式可以访问.

详见：关于 Python 中的下划线用法的记录 | 别院牧志 (opens new window)

字符串格式化:%->.format->f-string

.format 在许多方面看起来更便利。对于%最烦人的是它无法同时传递一个变量和元组，你可能会想下面的代码不会有什么问题:

"hi there %s" % name

但是,如果 name 恰好是(1,2,3),它将会抛出一个 TypeError 异常.为了保证它总是正确的,你必须这样做:

"hi there %s" % (name,)   # 提供一个单元素的数组而不是一个参数

但是有点丑。.format 就没有这些问题。

你为什么不用它?

• 不知道它(在读到此处之前)
• 为了和 Python2.5 兼容(譬如 logging 库建议使用%(issue #4 (opens new window)))

python - String formatting: % vs. .format vs. string literal - Stack Overflow (opens new window)

此外，f-string是用于字符串格式化的最新 Python 语法。从 Python 3.6 开始就可以使用。Python f-string提供了一种更快、更可读、更简洁、更不易出错的 Python 字符串格式化方式。

参见：Python 字符串格式化

迭代器和生成器

特性	迭代器（Iterator）	生成器（Generator）
定义方式	需要实现__iter__()和__next__()	使用yield关键字定义函数
代码复杂度	代码较多，需要手动实现协议方法	代码简洁，自动实现迭代器协议
内存占用	可能占用较多内存（取决于实现）	占用较少内存（惰性计算）
适用场景	需要自定义迭代逻辑时使用	处理大数据流或无限序列时使用
性能	性能较低（手动实现）	性能较高（Python 优化）

• 迭代器

它是一个带状态的对象，它能在你调用 next()方法的时候返回容器中的下一个值，任何实现了__iter__()和__next__()（python2 中实现 next()）方法的对象都是迭代器，__iter__返回迭代器自身，__next__返回容器中的下一个值，如果容器中没有更多元素了，则抛出 StopIteration 异常。

# 菲波那切数列示例

class Fib:
    def __init__(self, n):
        self.prev = 0
        self.cur = 1
        self.n = n

    def __iter__(self):
        return self

    def __next__(self):
        if self.n >0:
            self.prev,self.cur = self.prev+self.cur,self.prev
            self.n-=1
            return self.prev
        raise StopIteration
    # 兼容python2
    # def __next__(self):
    #     return self.next()

f = Fib(10)
print([i for i in f])
#[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

• 生成器(generator)

生成器其实是一种特殊的迭代器，不过这种迭代器更加优雅。它不需要再像上面的类一样写__iter__()和__next__()方法了，只需要一个 yiled 关键字。 生成器一定是迭代器（反之不成立），因此任何生成器也是以一种懒加载的模式生成值。而由于它惰性求值的特点，在处理大型数据时，可以节省大量内存空间。

# 生成器实现斐波纳切


def fib(num):
    n,a,b = 0,0,1
    while n < num:
        yield b
        a,b = b,a+b
        n += 1

for i in fib(5):
    print(i)

• Python 迭代器，生成器--精华中的精华 - Winter_Ding - 博客园 (opens new window)
• 完全理解 Python 迭代对象、迭代器、生成器 - FooFish-Python 之禅 (opens new window)
• 如何更好地理解 Python 迭代器和生成器？ - 知乎 (opens new window)
• python 生成器和迭代器有这篇就够了 - 战争热诚 - 博客园 (opens new window)

这个是 stackoverflow 里 Python 排名第一的问题，值得一看: python - What does the "yield" keyword do? - StackOverflow (opens new window)

这是中文版: 3. (译)Python 关键字 yield 的解释(stackoverflow) — 一起写 Python 文章，一起看 Python 文章 (opens new window)

这里有个关于生成器的创建问题面试官有考：

Q：将列表生成式中[]改成()之后数据结构是否改变？

A：是，生成器表达式是一种更简洁的生成器定义方式。

>>> 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 中，我们可以采用生成器：边循环，边计算的机制—>generator

1. 生成器的“按需生成”是什么意思

生成器的“按需生成”指的是：

• 生成器不会一次性将所有数据加载到内存中。
• 每次调用next()或通过for循环迭代时，生成器才会生成下一个值。
• 生成器在生成一个值后，会暂停执行，直到下一次请求。

---

2. 代码执行过程分析

以下面的代码为例：

def my_generator(data):
    for item in data:
        yield item

# 使用生成器
gen = my_generator([1, 2, 3, 4, 5])
for num in gen:
    print(num)

理解生成器的“按需生成”特性需要从生成器的工作机制入手。虽然在上面的代码中，for循环最终会打印出所有数据，但生成器的“按需生成”特性体现在数据的生成时机和内存占用上，而不是最终的结果。

执行步骤

1. 创建生成器：

   • gen = my_generator([1, 2, 3, 4, 5]) 只是创建了一个生成器对象，此时生成器函数my_generator并未执行。

2. 第一次迭代：

   • for循环第一次调用next(gen)，生成器开始执行：
     • 进入my_generator函数，执行到yield item。
     • 此时item是1，生成器返回1并暂停。
   • for循环接收到1，执行print(1)。

3. 第二次迭代：

   • for循环再次调用next(gen)，生成器从上次暂停的位置继续执行：
     • 继续for循环，item变为2，生成器返回2并暂停。
   • for循环接收到2，执行print(2)。

4. 重复上述过程：

   • 每次for循环调用next(gen)，生成器都会从上次暂停的位置继续执行，生成下一个值，直到数据遍历完毕。

5. 结束：

   • 当for循环遍历完所有数据后，生成器抛出StopIteration异常，for循环捕获该异常并结束。

---

3. “按需生成”的关键点

• 生成器不会一次性加载所有数据：

  • 生成器每次只生成一个值，并在生成后暂停。
  • 即使数据量很大，生成器也只会占用当前生成值的内存，而不是整个数据集的内存。

• 生成器的执行是分段进行的：

  • 生成器函数在每次yield时暂停，等待下一次调用。
  • 这种分段执行的特性使得生成器非常适合处理大数据流或无限序列。

---

4. 与列表的对比

如果使用列表而不是生成器，代码可能是这样的：

def my_list(data):
    result = []
    for item in data:
        result.append(item)
    return result

# 使用列表
my_list_result = my_list([1, 2, 3, 4, 5])
for num in my_list_result:
    print(num)

区别

• 列表：

  • my_list函数会一次性将所有数据加载到内存中，并存储在result列表中。
  • 如果数据量很大，可能会占用大量内存。

• 生成器：

  • my_generator函数不会一次性加载所有数据，而是按需生成。
  • 即使数据量很大，生成器也只会占用当前生成值的内存。

5. 验证生成器的“按需生成”

可以通过以下代码验证生成器的惰性特性：

def my_generator(data):
    print("生成器开始执行")
    for item in data:
        print(f"生成器生成: {item}")
        yield item

# 使用生成器
gen = my_generator([1, 2, 3, 4, 5])
print("生成器创建完成")

# 第一次调用
print("第一次调用next(gen)")
print(next(gen))  # 输出: 生成器生成: 1，然后输出: 1

# 第二次调用
print("第二次调用next(gen)")
print(next(gen))  # 输出: 生成器生成: 2，然后输出: 2

输出结果

生成器创建完成
第一次调用next(gen)
生成器开始执行
生成器生成: 1
1
第二次调用next(gen)
生成器生成: 2
2

从输出可以看出：

• 生成器在调用next(gen)时才开始执行。
• 每次调用next(gen)，生成器只生成一个值并暂停。

---

6. 总结

• 生成器的“按需生成”体现在数据的生成时机和内存占用上。
• 生成器不会一次性加载所有数据，而是每次只生成一个值并暂停。
• 这种特性使得生成器非常适合处理大数据流或无限序列，同时节省内存。

*args 和 **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 = {a}, b = {b}, c = {c}')
...
>>> mylist = ['aardvark', 'baboon', 'cat']
>>> print_three_things(*mylist)

a = aardvark, b = baboon, c = cat

就像你看到的一样,它可以传递列表(或者元组)的每一项并把它们解包。注意必须与它们在函数里的参数相吻合。当然，你也可以在函数定义或者函数调用时用。

http://stackoverflow.com/questions/3394835/args-and-kwargs (opens new window)

面向切面编程 AOP 和装饰器

这个 AOP 一听起来有点懵，同学面阿里的时候就被问懵了...

装饰器是一个很著名的设计模式，经常被用于有切面需求的场景，较为经典的有插入日志、性能测试、事务处理等。装饰器是解决这类问题的绝佳设计，有了装饰器，我们就可以抽离出大量函数中与函数功能本身无关的雷同代码并继续重用。概括的讲，装饰器的作用就是为已经存在的对象添加额外的功能。

这个问题比较大,推荐: http://stackoverflow.com/questions/739654/how-can-i-make-a-chain-of-function-decorators-in-python (opens new window)

Python 装饰器✨

常用的一些包：retry、deprecated 等

鸭子类型

“当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子，那么这只鸟就可以被称为鸭子。”

我们并不关心对象是什么类型，到底是不是鸭子，只关心行为。

比如在 python 中，有很多 file-like 的东西，比如 StringIO,GzipFile,socket。它们有很多相同的方法，我们把它们当作文件使用。

又比如 list.extend()方法中，我们并不关心它的参数是不是 list，只要它是可迭代的即可。所以它的参数可以是 list/tuple/dict/字符串/生成器等。

鸭子类型在动态语言中经常使用，非常灵活，使得 Python 不像 Java 那样专门去弄一大堆的设计模式。

Python 中重载

引自知乎：为什么 Python 不支持函数重载？而其他语言大都支持？ - 知乎 (opens new window)

函数重载主要是为了解决两个问题。

1. 可变参数类型。
2. 可变参数个数。

另外，一个基本的设计原则是，仅仅当两个函数除了参数类型和参数个数不同以外，其功能是完全相同的，此时才使用函数重载，如果两个函数的功能其实不同，那么不应当使用重载，而应当使用一个名字不同的函数。

好吧，那么对于情况 1 ，函数功能相同，但是参数类型不同，Python 如何处理？答案是根本不需要处理，因为 Python 可以接受任何类型的参数，如果函数的功能相同，那么不同的参数类型在 Python 中很可能是相同的代码，没有必要做成两个不同函数。

那么对于情况 2 ，函数功能相同，但参数个数不同，Python 如何处理？大家知道，答案就是缺省参数。对那些缺少的参数设定为缺省参数即可解决问题。因为你假设函数功能相同，那么那些缺少的参数终归是需要用的。

好了，鉴于情况 1 跟 情况 2 都有了解决方案，Python 自然就不需要函数重载了。

新式类和旧式类

class - What is the difference between old style and new style classes in Python? - StackOverflow (opens new window)

INFO

类分为两种：旧式类和新式类。

截止到 python2.1，只存在旧式类。

旧式类中，类的概念和 type 是无关的：如果 x 是一个旧式类，那么 x.__class__定义了 x 的类名，但是 type(x)总是返回<type 'instance'>。这反映了所有的旧式类的实例是通过一个单一的叫做 instance 的内建类型来实现的，这是它和类不同的地方。

新式类是在 python2.2 为了统一类和实例引入的。一个新式类只能由用户自定义。如果 x 是一个新式类的实例，那么 type(x)和 x.__class__是一样的结果（尽管这不能得到保证，因为新式类的实例的__class__方法是允许被用户覆盖的）。

引入新式类的主要动机是提供一个具有完整元模型（full meta-model）的统一对象模型。当然它也有很多实用的功能，比如继承了大部分的内建类型，引入了“描述符（descriptors）”，它可以启用计算属性。

因为兼容性的原因，（在 Python2 中）类依然是默认的旧式类。

新式类只能通过继承另一个新式类或所有类的根类 object 来创建（如果没有其他类需要继承的话）。新式类的表现在 type()函数的返回值上有几个和旧式类不同的地方。其中有一些对于新对象模型来说是根本的变化，比如调用了特殊的方法。其他的是作了一些“修正”，那些在考虑兼容性之前不太可能被用到的地方，比如多重继承的方法的区分逻辑。

新样式类通过指定另一个新样式类(即类型)作为父类来创建，如果不需要其他父类，则指定“顶级类型”对象。新型类的行为与旧式类的行为不同，除了类型返回的内容之外，还有许多重要的细节。其中一些更改是新对象模型的基础，比如调用特殊方法的方式。其他的是之前由于兼容性问题无法实现的“修复”，比如多重继承时的方法解析顺序。

旧式类在 python3 中被移除，只留下了新式类。不管是否继承 object，都是如此。

这篇文章很好的介绍了新式类的特性: http://www.cnblogs.com/btchenguang/archive/2012/09/17/2689146.html (opens new window)

在 Python 的新式类中，方法解析顺序并非是广度优先的算法，而是采用 C3 算法。

更多参见Python 中的 MRO 与多继承

一个旧式类的深度优先的例子

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()
# py2
# A
# py3
# C

按照经典类的查找顺序从左到右深度优先的规则，在访问d.foo1()的时候，D 这个类是没有的。那么往上查找，先找到 B，里面没有，深度优先,访问 A，找到了 foo1()，所以这时候调用的是 A 的 foo1()，从而导致 C 重写的 foo1()被绕过。

__new__和__init__和__call__的区别

笔记

Use __new__ when you need to control the creation of a new instance.

Use __init__ when you need to control initialization of a new instance.

__new__ is the first step of instance creation. It's called first, and is responsible for returning a new instance of your class.

In contrast, __init__ doesn't return anything; it's only responsible for initializing the instance after it's been created.

In general, you shouldn't need to override __new__ unless you're subclassing an immutable type like str, int, unicode or tuple.

[Tutor] When to use __new__ vs. __init__ ? (opens new window)

翻译

当你需要控制新实例的创建时，使用 __new__。

当你需要控制新实例的初始化时，使用__init__。

__new__是实例创建的第一步。它被首先调用，负责返回类的一个新实例。

相比之下，__init__不返回任何内容; 它只负责在实例创建后对其进行初始化。

一般来说，你不需要覆盖__new__方法，除非你子类化了一个不可变的类型，比如 str，int，unicode 或者 tuple。

在 Python 中，构造函数是指 __init__ 方法，它用于初始化一个类的实例。在创建一个类的实例时，__init__ 方法会被自动调用，用于设置实例的初始状态，如初始化属性等。

__init__ 方法

__init__ 方法是一个实例方法，它的第一个参数通常为 self，代表类的实例。__init__ 方法不会返回值，它的作用是初始化实例的属性和执行其他初始化操作。

class MyClass:
    def __init__(self, name, age):
        self.name = name
        self.age = age

obj = MyClass("Alice", 30)
print(obj.name)  # 输出: Alice
print(obj.age)   # 输出: 30

在这个例子中，__init__ 方法接受两个参数 name 和 age，并将它们赋值给实例的属性 self.name 和 self.age。

__new__ 方法

• __new__ 方法是一个静态方法，在实例创建之前被调用，是在类实例化对象时第一个调用的方法，它负责创建并返回一个新的实例对象。
• __new__ 方法通常用于自定义类的实例化过程，特别是在需要控制实例的创建时。
• __new__ 方法始终都是类方法（即第一个参数为 cls），如果要得到当前类的实例，应当在当前类中的 __new__方法语句中调用当前类的父类的 __new__ 方法

class MyClass:
    def __new__(cls, *args, **kwargs):
        instance = super(MyClass, cls).__new__(cls)
        print("Creating instance")
        return instance

    def __init__(self, name, age):
        self.name = name
        self.age = age
        print("Initializing instance")

obj = MyClass("Alice", 30)

# 输出结果：
# Creating instance
# Initializing instance
# Alice

在这个例子中：

1. __new__ 方法首先被调用，用于创建一个新的实例。在 __new__ 方法中，调用 super(MyClass, cls).__new__(cls) 创建实例。
2. __init__ 方法随后被调用，用于初始化实例的属性。

__new__ 和 __init__ 的区别

1. 调用顺序：

   • __new__ 方法在实例创建之前被调用。
   • __init__ 方法在实例创建之后被调用。

2. 作用：

   • __new__ 方法负责创建并返回一个新的实例。它通常用于自定义实例的创建过程，特别是在需要继承不可变类型（如 int、str 等）时。
   • __init__ 方法负责初始化实例的属性。它不返回值，只用于设置实例的初始状态。

3. 参数：

   • __new__ 方法的第一个参数是类本身（通常命名为 cls），后续参数与 __init__ 方法相同。
   • __init__ 方法的第一个参数是实例（通常命名为 self）。

何时使用 __new__

__new__ 方法通常在以下情况下使用：

1. 继承不可变类型：当你需要继承不可变类型（如 int、str 等）时，必须重写 __new__ 方法，因为这些类型的实例在创建后不能修改。

class MyInt(int):
    def __new__(cls, value):
        return super(MyInt, cls).__new__(cls, value)

    def __init__(self, value):
        self.value = value

obj = MyInt(5)
print(obj)  # 输出: 5

2. 控制实例创建：在需要控制实例创建过程时，如实现单例模式或池化对象时，可以使用 __new__ 方法。

class Singleton:
    _instance = None

    def __new__(cls, *args, **kwargs):
        if cls._instance is None:
            cls._instance = super(Singleton, cls).__new__(cls)
        return cls._instance

    def __init__(self, value):
        self.value = value

obj1 = Singleton(1)
obj2 = Singleton(2)

print(obj1 is obj2)  # 输出: True
print(obj1.value)    # 输出: 2
print(obj2.value)    # 输出: 2

在这个例子中，Singleton 类确保只有一个实例存在。

总结

• __new__负责创建并返回实例，用于控制实例的创建过程。；而__init__是构造方法，一个实例化方法，负责对对象的属性进行初始化赋值，用于初始化类的实例。
• __new__方法会返回一个创建的实例，而__init__什么都不返回；
• 只有在__new__返回一个 cls 的实例时，后面的__init__才能被调用；
• 当创建一个新实例时调用__new__，初始化一个实例时用__init__；

参考阅读

Python use of new and init (opens new window)

python - Why is init() always called after new()? - Stack Overflow (opens new window)

详解类 class 类的构造函数__new__和初始化函数__init__及定制一个类（终章）_brucewong0516 的博客 (opens new window)

__call__方法

Python 中所有的东西都被称为对象，对象分为可以被调用和不可以被调用。 可调用对象：许多 Python 对象都是我们所说的可调用的，即是任何通过函数操作符()来调用的对象，例如函数：

def func():
    pass

func()

Python 给类提供了名为__call__的特别方法，该方法允许程序员创建可调用的对象(实例)。默认情况下，__call__方法是没有实现的，这意味着大多数情况下实例是不可调用的。

class Foo:

    def bar(self):
        print('This is bar func.')

f = Foo()
f()
# 返回报错：
Traceback (most recent call last):
  File "C:\Users\imoyao\Desktop\bar.py", line 11, in <module>
    f()
AttributeError: Foo instance has no __call__ method

class Foo:

    def bar(self):
        print('This is bar func.')

    def __call__(self):
        print('You get call func!')

f = Foo()
f()
# 正常返回
You get call func!

关于什么时候用__call__：python - When is using call a good idea? - Stack Overflow (opens new window)

从历史上看，可调用对象(或者我有时听到的所谓“函数”)在 OO 世界中被用来模拟闭包。在 C++ 中，它们经常是不可或缺的。

然而，__call__ 在 Python 世界中有相当多的竞争者:

• 一个常规的命名方法，其行为有时可以更容易地从名称中推断出来。可以转换为一个绑定的方法，这个方法可以像函数一样调用。
• 闭包，通过返回在嵌套块中定义的函数获得。
• 一个 lambda 表达式，这是一个有限但是快速的解决方式。
• 生成器和协程，它们本身像函数那样保持累积状态。

我想说，使用 __call__ 的时机是你没法选择上述选项之一。也许可以检查以下标准:

• 对象具有状态。
• 您的类有一个明确的“主要”行为，命名起来有点傻。例如，如果你发现自己正在写 run()或 doStuff()或 go()或者一直很受欢迎并且经常冗余的 doRun () ，你可能就有了一个候选者。
• 对象的状态超过了对生成器函数的期望值。
• 您的对象包装、模拟或抽象函数的概念。
• 对象还有其他辅助方法，这些辅助方法在概念上属于您的主要行为。

我喜欢的一个例子是 UI 命令对象。它们的主要任务是执行 comnand 命令，但是有额外的方法来控制它们作为菜单项的显示，例如，在我看来，这似乎是你仍然需要一个可调用对象的类型。

• What is the difference between __init__ and __call__? (opens new window)
• 简述 __init__、__new__、__call__ 方法 (opens new window)
• Python __call__ special method practical example (opens new window)

应用：如 Django 中的表单验证，增强代码的可扩展性和可读性。

ps: __metaclass__是创建类时起作用.所以我们可以分别使用__metaclass__,__new__和__init__来分别在类创建、实例创建和实例初始化的时候做一些小手脚。参阅元类

单例模式

单例模式是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问，从而方便对实例个数的控制并节约系统资源。如果希望在系统中某个类的对象只能存在一个，单例模式是最好的解决方案。

__new__()在__init__()之前被调用，用于生成实例对象。利用这个方法和类的属性的特点可以实现设计模式的单例模式。单例模式是指创建唯一对象，单例模式设计的类只能实例化一次。

使用__new__方法

# python2
class Singleton(object):
    _instance = {}
    def __new__(cls, *args, **kwargs):
        if cls not in cls._instance:
            cls._instance[cls] = super(Singleton,cls).__new__(cls,*args,**kwargs)
        return cls._instance[cls]

class A(Singleton):
    pass

class B(A):
    pass

a = A()
b = B()
print(isinstance(b,B))
print(isinstance(b,A))


# Python3
class Singleton:

    _instance = None

    def __new__(cls,*args,**kwargs):
        if not cls._instance:
            cls._instance = super().__new__(cls,*args,**kwargs)

        return cls._instance


a = Singleton()
b = Singleton()

print(a is b)

# 变种实现
class SingleTon:

    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self._instance = None

    def __new__(cls, *args, **kwargs):
        if not hasattr(cls, '_instance'):
            cls._instance = super().__new__(cls, *args, **kwargs)

        return cls._instance


a = SingleTon()
b = SingleTon()
print(a is b)

共享属性

所谓单例就是所有引用(实例、对象)拥有相同的状态(属性)和行为(方法)。 同一个类的所有实例天然拥有相同的行为(方法),只需要保证同一个类的所有实例具有相同的状态(属性)即可，所有实例共享属性的最简单最直接的方法就是__dict__属性指向(引用)同一个字典(dict)。

可参阅此文 (opens new window)

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 = 1

装饰器版本

from functools import wraps


def singleton(cls):
    _instance = {}

    @wraps(cls)
    def wrapper(*args, **kwargs):
        if cls not in _instance:
            _instance[cls] = cls(*args, **kwargs)

        return _instance[cls]

    return wrapper


@singleton
class Singleton:
    pass


a = Singleton()
b = Singleton()
print(a is b)

import 方法

作为 python 的模块是天然的单例模式

# mysingleton.py
class Singleton(object):
    def foo(self):
        pass

my_singleton = Singleton()

# to use
from mysingleton import my_singleton

my_singleton.foo()

修改元类

# python2
class Singleton(type):
    _instance = {}

    def __call__(cls, *args, **kwargs):
        if cls not in cls._instance:
            cls._instance[cls] = super(Singleton, cls).__call__(*args, **kwargs)
        return cls._instance[cls]


class A(object):
    __metaclass__ = Singleton

# Python3
class Singleton(type):

    def __init__(self, *args, **kwargs):
        self._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 A(metaclass=Singleton):
    pass


a = A()
b = A()
print(a is b)

• 单例模式伯乐在线详细解释 (opens new window)

• Python 中的单例模式的几种实现方式及优化 (opens new window)

Python 中的作用域

Python 中，一个变量的作用域总是由在代码中被赋值的地方所决定的。

在一个 python 程序中，直接访问一个变量，会从内到外依次访问所有的作用域直到找到，否则会报未定义的错误。

Python 中，程序的变量并不是在哪个位置都可以访问的，访问权限决定于这个变量是在哪里赋值的。

变量的作用域决定了在哪一部分程序可以访问哪个特定的变量名称。Python 一共有四种作用域，分别是：

• L（Local）：最内层，包含局部变量，比如一个函数/方法内部。
• E（Enclosing）：包含了非局部(non-local)也非全局(non-global)的变量。比如两个嵌套函数，一个函数（或类） A 里面又包含了一个函数 B ，那么对于 B 中的名称来说 A 中的作用域就为 nonlocal。

def deco(func):
    string = 'I am deco'
    def wrapper():
        print(string)
        func()
    return wrapper
    
@deco
def foo():
    print('I am foo')
    
    
foo()  
"""
# 输出:
I am deco
I am foo
"""

内层函数会把外层函数作用域里面自已引用的对象放到__closure__属性里，以供自己查找。如果内部函数引用到外层函数作用域的对象，这个内部函数就称为闭包。

>>> foo.__closure__
(<cell at 0x00000156A60C0C48: str object at 0x00000156A626B340>, <cell at 0x00000156A615FE28: function object at 0x00000156A68A3A60>)

• G（Global）：当前脚本的最外层，比如当前模块的全局变量。

• B（Built-in）： 包含了内建的变量/关键字等，最后被搜索。

  规则顺序： L –> E –> G –> B。

当 Python 遇到一个变量的话它会按照这样的顺序进行搜索：

本地作用域（Local）→当前作用域被嵌入的本地作用域（Enclosing locals）→全局/模块作用域（Global）→内置作用域（Built-in） 作用域就是一个 Python 程序可以直接访问命名空间的正文区域。

在局部找不到，便会去局部外的局部找（例如闭包），再找不到就会去全局找，再去内置中找。

python 变量作用域 - 刘江的 python 教程 (opens new window)

Python3 命名空间和作用域 | 菜鸟教程 (opens new window)

Python 命名空间

Python 的命名空间可以分为三种：内置命名空间、全局命名空间和局部命名空间。

1. 内置命名空间（Built-in Namespace）：包含了 Python 解释器中预定义的内置函数和对象（如 print()、len()等），这个命名空间在启动 Python 解释器时自动加载，无需导入任何模块，全局可见。

2. 全局命名空间（Global Namespace）：在模块中定义的函数、类和变量的命名空间。在模块级别定义的名称都存在于该命名空间中，可以通过模块名来访问这些名称。

3. 局部命名空间（Local Namespace）：在函数体或类的方法中定义的变量名的命名空间。这些变量名只在其定义的函数或方法体内可见，函数执行时创建，并在函数执行结束后销毁。

这三种命名空间之间存在着层级关系。Python 解释器在查找变量名时，会首先在局部命名空间中查找，然后是全局命名空间，最后是内置命名空间。如果变量在当前命名空间中不存在，解释器会沿着命名空间链逐级向上查找直到找到或到达最顶层的内置命名空间。

了解命名空间的概念对于理解 Python 中的作用域和可见性非常重要，可帮助我们避免命名冲突和编写更清晰的代码。

GIL 线程全局锁

线程全局锁(Global Interpreter Lock),即 Python 为了保证线程安全而采取的独立线程运行的限制，说白了就是一个核只能在同一时间运行一个线程。对于 io 密集型任务，Python 的多线程起到作用，但对于 cpu 密集型任务，Python 的多线程几乎占不到任何优势，还有可能因为争夺资源而变慢。

见Python 最难的问题 (opens new window)

解决办法就是多进程和下面的协程(协程也只是单 CPU,但是能减小切换代价提升性能)。

协程

协程是一种用户态的轻量级线程，它不需要操作系统的支持，完全由用户程序控制。协程具有自己的寄存器上下文和栈空间，可以在执行过程中暂停、恢复和切换执行上下文。协程之间可以通过协作的方式进行通信和同步，不需要使用锁机制。它可以在执行过程中暂停，将控制权交给其他协程，在适当的时间恢复执行，相比于传统的函数调用，这种暂停和恢复不消耗额外的系统资源，而是将协程状态保存下来，因此更加灵活高效。

使用协程的优势主要有以下几点：

1. 协程的切换开销极低：协程的切换只涉及保存和恢复寄存器上下文，几乎没有什么开销，远小于进程切换和线程切换。
2. 协程是在用户态下调度的，不涉及内核态和用户态之间的切换。
3. 协程能保留上一次调用时的状态，即所有局部状态的一个特定组合，每次过程重入时，就相当于进入上一次调用的状态。
4. 不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了。
5. 协程是面向任务的，更加适合处理 IO 密集型任务，如网页爬取、网络请求等。

Python 中通常使用 yield 实现控制协程暂停，send 将数据发送给协程实现恢复。高级版本中引入 asyncio 实现协程。

简单点说协程是进程和线程的升级版，进程和线程都面临着内核态和用户态的切换问题而耗费许多切换时间，而协程就是用户自己控制切换的时机，不再需要陷入系统的内核态。Python 里最常见的 yield 就是协程的思想。

闭包

闭包(closure)是函数式编程的重要的语法结构。闭包也是一种组织代码的结构，它同样提高了代码的可重复使用性。

当一个内嵌函数引用其外部作用域的变量，我们就会得到一个闭包。 总结一下，创建一个闭包必须满足以下几点：

1. 必须有一个内嵌函数
2. 内嵌函数必须引用外部函数中的变量
3. 外部函数的返回值必须是内嵌函数

重点是函数运行后并不会被撤销，就像 16 题的 instance 字典一样，当函数运行完后，instance 并不被销毁，而是继续留在内存空间里。这个功能类似类里的类变量，只不过迁移到了函数上。

闭包就像个空心球一样，你知道外面和里面，但你不知道中间是什么样。

参见闭包

lambda 函数

其实就是一个匿名函数，为什么叫 lambda？因为和后面的函数式编程有关。

推荐: Lambda 表达式有何用处？如何使用？ - 知乎 (opens new window)

map(lambda x: x*2, range(10))

# 这个写法要好过

def sq(x):
    return x * 2

map(sq, range(10))

Python 函数式编程

这个需要适当的了解一下吧，毕竟函数式编程在 Python 中也做了引用。

推荐: 酷壳 (opens new window)

Python 中函数式编程支持:

filter 函数的功能相当于过滤器。调用一个布尔函数bool_func来迭代遍历每个 seq 中的元素；返回一个使bool_seq返回值为 true 的元素的序列。

>>>a = [1,2,3,4,5,6,7]
>>>b = filter(lambda x: x > 5, a)
>>>print(list(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))
6

Python 里的拷贝

在 Python 中，赋值操作、copy和deepcopy这三者都可以用于复制对象，但是它们之间存在一些重要的区别。

1. 赋值操作：这是最简单的复制操作。它只是复制了对象的引用，而不是对象本身。也就是说，赋值后的两个变量实际上指向的是同一个对象。如果对其中一个变量进行修改，那么另一个变量也会受到影响。

a = [1, 2, 3]
b = a
b.append(4)
print(a)  # 输出：[1, 2, 3, 4]

2. copy：这是一种浅复制。它创建了一个新的对象，但是这个新对象中的元素仍然是对原对象中的元素的引用。也就是说，如果原对象中的元素是可变的（例如列表或字典），那么对这些元素的修改会影响到复制后的对象。

import copy
a = [1, 2, [3, 4]]
b = copy.copy(a)
b[2].append(5)
print(a)  # 输出：[1, 2, [3, 4, 5]]

3. deepcopy：这是一种深复制。它创建了一个新的对象，并且递归地复制了原对象中的所有元素。也就是说，无论原对象中的元素是可变的还是不可变的，对这些元素的修改都不会影响到复制后的对象。

import copy
a = [1, 2, [3, 4]]
b = copy.deepcopy(a)
b[2].append(5)
print(a)  # 输出：[1, 2, [3, 4]]

如果你需要完全复制一个对象，并且希望复制后的对象与原对象完全独立，那么应该使用 deepcopy。但是，如果你只需要复制对象的一部分，或者不希望复制过程中产生大量的内存开销，那么使用 copy 可能会更合适。另外，对于一些简单的对象（例如整数或字符串），copy 和 deepcopy 的效果是一样的，因此没有必要使用 deepcopy。

Python 全栈之路系列之深浅拷贝

Python 内存管理机制

Python 有内存池机制，Pymalloc 机制，用于对内存的申请和释放管理。

为什么有内存池

当创建大量消耗小内存的对象时，c 中频繁调用 new/malloc 会导致大量的内存碎片，致使效率降低。

内存池的概念就是预先在内存中申请一定数量的，大小相等的内存块留作备用，当有新的内存需求时，就先从内存池中分配内存给这个需求，不够了之后再申请新的内存。这样做最显著的优势就是能够减少内存碎片，提升效率。

python 中的内存管理机制为 Pymalloc，python 的对象管理主要位于 Level+1~Level+3 层

Level+3 层：对于 python 内置的对象（比如 int,dict 等）都有独立的私有内存池，对象之间的内存池不共享，即 int 释放的内存，不会被分配给 float 使用

Level+2 层：当申请的内存大小小于 256KB 时，内存分配主要由 Python 对象分配器（Python’s object allocator）实施

Level+1 层：当申请的内存大小大于 256KB 时，由 Python 原生的内存分配器进行分配，本质上是调用 C 标准库中的 malloc/realloc 等函数

面试必备：Python 内存管理机制 (opens new window)

Python 垃圾回收机制

Python GC 主要使用引用计数（reference counting）来跟踪和回收垃圾。在引用计数的基础上，通过“标记-清除”（mark and sweep）解决容器对象可能产生的循环引用问题，通过“分代回收”（generation collection）以空间换时间的方法提高垃圾回收效率。

Python 的内存管理与垃圾回收机制

Python 的 List

推荐: Python 中 list 的实现 - 简书 (opens new window)

Python 的 is

is 是对比地址，==是对比值

read,readline 和 readlines

• read 读取整个文件
• readline 读取下一行,使用生成器方法
• readlines 读取整个文件到一个列表以供我们遍历

Python2 和 3 的区别

推荐：Python 2.7.x 与 Python 3.x 的主要差异 (opens new window)

super()与__init__

Python 受推崇的 super | 别院牧志知识库

使用 super()可以避免显式引用基类，这可能是个不错的主意。 但主要优势在于多重继承，可以发生各种有趣的事情 (opens new window)。 请参阅标准文档上的 super()章节 (opens new window)，如果您还没有来得及阅读的话。

请注意，Python 3.0 中的语法发生了变化：可以用super().__init__()替代super（ChildB，self）.__ init __()，在我看来相对更好一些。 标准文档也引用了super()使用指南 (opens new window)，解释得非常明确。

• 区别是什么？

SomeBaseClass.__init__(self)意味着调用 SomeBaseClass's __init__。而super(Child, self).__init__()表示从实例的方法解析顺序（MRO|Method Resolution Order）中的Child后面的父类调用绑定的__init__。

如果实例是Child的子类，则 MRO 中可能会有另一个父级。

编写类时，你希望其他类能够使用它。 super()使其他类可以更容易使用你所编写的类。一个好的架构可以让你尽可能地推迟决策。而super()可以启用这种架构。

使用super()会为你提供一个具有向前兼容性的间接层。

class A(object):
    def __init__(self):
        print('init in a')


class UnSuperChild(A):
    def __init__(self):
        print('init in UnSuper')
        A.__init__(self)


class SuperChild(A):
    def __init__(self):
        print('init in Super')
        super(SuperChild,self).__init__()


class B(A):
    def __init__(self):
        print('init in B')
        super(B,self).__init__()


class C(UnSuperChild,B):
    pass

class D(SuperChild,B):
    pass

c = C()
print('*'*20)
d = D()

# 输出
init in UnSuper
init in A
# ********************
init in Super
init in B
init in A

• Understanding Python super() with __init__() methods (opens new window)
• what does superdo in Python (opens new window)
• Python2.7 中的super方法浅见 (opens new window)

range 和 xrange

在 Python2.*中 range()和 xrange()有什么区别？

range()会在内存中创建一个 list,而 xrange()会惰性生成一个序列对象，只有在需要的时候才产生元素。（类似于生成器）如果是类似for i in range(10000000)的语句，会非常的消耗内存。

注意：Python3 中已经废弃原来的 range()方法，当前的 range()等效于原来的 xrange()实现。

那么在 Python3 中如何使用 range()生成一个列表呢？☞ list(range(10))

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 (opens new window)

Mixin

Python mixin 是一种用于重用代码的技术，通过将一些方法或属性定义在 mixin 类中，然后通过多继承的方式将 mixin 类与其他类组合在一起，或者希望某个特性用在多个类中，从而实现代码的复用。

Mixin 类通常不会单独使用，而是与其他类一起使用。它的作用类似于一个装饰器，可以为其他类添加额外的功能，而不需要修改原始类的代码。通过将功能性代码定义在 mixin 类中，可以在多个类中共享这些功能，避免了代码重复。

使用 mixin 类的主要优点是可以将功能模块化，使代码更加清晰和可维护。此外，由于 Python 支持多继承，因此可以在不同的类之间组合不同的 mixin 类，从而实现更灵活的代码组合。

要使用 mixin 类，只需将其作为其他类的父类之一即可。当多个 mixin 类具有相同的方法或属性时，Python 中的方法解析顺序（MRO）规定了方法的查找顺序。通常，方法解析顺序是按照从左到右的顺序进行查找，即先在当前类中查找，然后按照继承顺序依次查找父类。

使用 mixin 类时需要注意以下几点：

1. mixin 类应该只包含方法和属性，而不应该包含实例变量。
2. mixin 类应该命名为以 Mixin 结尾，以便清楚地表示其作用。
3. mixin 类应该尽量保持独立性，不要依赖于其他类或模块。

总结起来，Python mixin 是一种用于将代码功能模块化的技术，通过多继承的方式将 mixin 类与其他类组合在一起，实现代码的复用和功能的扩展。

class Vehicle(object):
    pass

class PlaneMixin(object):
    def fly(self):
        print('I am flying')

class Airplane(Vehicle, PlaneMixin):
    pass

可以看到，上面的 Airplane 类实现了多继承，不过它继承的第二个类我们起名为 PlaneMixin，而不是 Plane，这个并不影响功能，但是会告诉后来读代码的人，这个类是一个"Mixin"类。所以从含义上理解，Airplane 只是一个 Vehicle，不是一个 Plane。这个 Mixin，表示混入(mix-in)，它告诉别人，这个类是作为功能添加到子类中，而不是作为父类

关于 Python 的 Mixin 模式 | 思诚之道 (opens new window)

既然 python 中可以使用类装饰器，为什么还需要 mixin 方式？

虽然 Python 中可以使用类装饰器来实现类的功能扩展，但是 Mixin 方式有一些优势和适用场景，因此仍然有存在的价值：

1. Mixin 方式使得代码更具有可复用性和模块化。通过将功能模块拆分成多个 Mixin 类，可以在不同的类中引入需要的功能，从而实现代码的复用和可维护性。而装饰器更多用于给现有对象或函数添加额外的功能，比如日志记录、性能监测等。

2. Mixin 方式可以更方便地实现多继承。Python 中的多继承可能会导致类之间的关系复杂，而 Mixin 方式可以将功能模块进行拆分，避免多继承导致的混乱。

3. Mixin 方式更灵活和可定制。通过 Mixin 方式，可以根据具体的需求组合不同的功能模块，实现定制化的功能组合，而类装饰器方式更为固定。

因此，Mixin 方式在一些情况下仍然有其独特的优势，可以更好地满足特定的需求和设计目的。

操作系统

select,poll 和 epoll

select, poll 和 epoll 是三种常见的 I/O 多路复用机制，用于在一个线程中同时处理多个 I/O 事件。

1. select 是最早出现的一种多路复用机制，它通过一个位图来表示所有需要关注的文件描述符集合，并通过系统调用来等待其中任意一个文件描述符就绪。但是 select 存在一些问题，比如文件描述符集合大小有限，每次调用 select 都需要重新构建位图，效率较低。

   笔记

   在使用 select 函数时，文件描述符集合大小是通过一个整数值来表示的，通常称为 nfds。这个值是需要监视的最大文件描述符加 1。也就是说，select 函数会检查从 0 到 nfds-1 的文件描述符是否就绪。

   在使用 select 函数之前，需要将需要监视的文件描述符添加到一个位图中，通常使用 fd_set 结构体来表示。fd_set 结构体有一个 fd_array 数组，数组元素是一个位图，每个位代表一个文件描述符是否需要监视。

   在 Linux 中，默认情况下，nfds 的最大值为 FD_SETSIZE，它的值通常是 1024。这意味着 select 函数最多可以监视 1024 个文件描述符。

   需要注意的是，select 函数在每次调用时都需要重新构建位图，这会带来一定的开销。而且 select 函数的性能在文件描述符较多时可能会下降。因此，在高并发的网络编程中，通常会使用更高效的多路复用机制，如 poll 或 epoll。

2. poll 是 select 的改进版本，它通过一个 pollfd 数组来表示所有需要关注的文件描述符集合，并通过系统调用来等待其中任意一个文件描述符就绪。相比于 select，poll 没有了文件描述符集合大小的限制，但是效率仍然较低。

   poll 的缺陷

   poll 的主要缺陷包括以下几点：

   1. 效率问题：虽然相对于 select，poll 没有了文件描述符集合大小的限制，但是每次调用 poll 都需要传入一个 pollfd 数组，这个数组的大小取决于需要监视的文件描述符数量，而且每次调用 poll 都需要将整个数组传递给内核，这样会带来一定的开销。

   2. 线性扫描：poll 的实现方式是线性扫描，即每次调用 poll 都需要遍历整个 pollfd 数组来查找就绪的文件描述符，这样在文件描述符较多时，效率会降低。而且，当有大量文件描述符需要监视时，即使只有很少的文件描述符就绪，也需要遍历整个数组。

   3. 内存复制：每次调用 poll 都需要传递一个 pollfd 数组给内核，这涉及到内存的复制操作。当监视的文件描述符数量较多时，这个复制操作会带来一定的开销。

   4. 没有提供更高级的事件通知机制：poll 只能检测文件描述符是否就绪，而没有提供更高级的事件通知机制。这意味着在处理就绪的文件描述符时，仍然需要遍历整个数组来找到具体的就绪事件。

   综上所述，poll 在一些特定的场景下可能会存在一些性能上的限制，特别是在文件描述符较多时。因此，在高并发的网络编程中，通常会选择使用更高效的多路复用机制，如 epoll。

3. epoll 是 Linux 上引入的一种高效的 I/O 多路复用机制，它通过一个 epoll 对象来管理所有需要关注的文件描述符集合，并通过系统调用来等待其中任意一个文件描述符就绪。相比于 select 和 poll，epoll 的效率更高，因为它使用了回调机制，只有就绪的文件描述符才会被处理，而不需要遍历整个集合。此外，epoll 还支持三种工作模式：LT (Level-Triggered) 模式、ET (Edge-Triggered) 模式和 ONESHOT 模式，可以根据需要选择不同的模式。

   epoll 如何解决这些问题

   epoll 是为了解决 select 和 poll 的性能问题而引入的，它通过以下方式来解决这些问题：

   1. 高效的事件通知机制：epoll 使用了回调机制，只有就绪的文件描述符才会被处理，而不需要遍历整个集合。这样可以避免了线性扫描的问题，大大提高了效率。

   2. 内核管理文件描述符集合：epoll 通过一个 epoll 对象来管理需要关注的文件描述符集合，而不需要每次调用都传递一个数组。这样避免了内存复制的开销。

   3. 事件驱动的工作模式：epoll 提供了三种工作模式：LT (Level-Triggered) 模式、ET (Edge-Triggered) 模式和 ONESHOT 模式。其中，ET 模式是默认模式，只有当文件描述符状态发生变化时才会通知，这样可以避免了重复通知的问题。

   4. 支持大量文件描述符：epoll 没有了文件描述符集合大小的限制，可以支持大量的文件描述符，而且只有就绪的文件描述符会被处理，不需要遍历整个集合。

   综上所述，epoll 通过高效的事件通知机制、内核管理文件描述符集合和事件驱动的工作模式，解决了 select 和 poll 存在的性能问题，提供了更高效的 I/O 多路复用机制。在高并发的网络编程中，epoll 是首选的多路复用机制。

select,poll 和 epoll 区别总结 (opens new window)

基本上 select 有 3 个缺点:

1. 每次调用 select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大
2. 同时每次调用 select 都需要在内核遍历传递进来的所有 fd，这个开销在 fd 很多时也很大
3. select 支持的文件描述符数量太小了，默认是 1024

epoll

epoll 既然是对 select 和 poll 的改进，就应该能避免上述的三个缺点。那 epoll 都是怎么解决的呢？在此之前，我们先看一下 epoll 和 select 和 poll 的调用接口上的不同，select 和 poll 都只提供了一个函数——select 或者 poll 函数。而 epoll 提供了三个函数，epoll_create,epoll_ctl 和 epoll_wait，epoll_create 是创建一个 epoll 句柄；epoll_ctl 是注册要监听的事件类型；epoll_wait 则是等待事件的产生。

对于第一个缺点，epoll 的解决方案在 epoll_ctl 函数中。每次注册新的事件到 epoll 句柄中时（在 epoll_ctl 中指定 EPOLL_CTL_ADD），会把所有的 fd 拷贝进内核，而不是在 epoll_wait 的时候重复拷贝。epoll 保证了每个 fd 在整个过程中只会拷贝一次。

对于第二个缺点，epoll 的解决方案不像 select 或 poll 一样每次都把 current 轮流加入 fd 对应的设备等待队列中，而只在 epoll_ctl 时把 current 挂一遍（这一遍必不可少）并为每个 fd 指定一个回调函数，当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的 fd 加入一个就绪链表）。epoll_wait 的工作实际上就是在这个就绪链表中查看有没有就绪的 fd（利用 schedule_timeout()实现睡一会，判断一会的效果，和 select 实现中的第 7 步是类似的）。

对于第三个缺点，epoll 没有这个限制，它所支持的 FD 上限是最大可以打开文件的数目，这个数字一般远大于 2048,举个例子,在 1GB 内存的机器上大约是 10 万左右，具体数目可以cat /proc/sys/fs/file-max查看，一般来说这个数目和系统内存关系很大。

关于 epoll 的: http://www.cnblogs.com/my_life/articles/3968782.html (opens new window)

总结

1. select，poll 实现需要自己不断轮询所有 fd 集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而 epoll 其实也需要调用 epoll_wait 不断轮询就绪链表，期间也可能多次睡眠和唤醒交替，但是它是设备就绪时，调用回调函数，把就绪 fd 放入就绪链表中，并唤醒在 epoll_wait 中进入睡眠的进程。虽然都要睡眠和交替，但是 select 和 poll 在“醒着”的时候要遍历整个 fd 集合，而 epoll 在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的 CPU 时间。这就是回调机制带来的性能提升。
2. select，poll 每次调用都要把 fd 集合从用户态往内核态拷贝一次，并且要把 current 往设备等待队列中挂一次，而 epoll 只要一次拷贝，而且把 current 往等待队列上挂也只挂一次（在 epoll_wait 的开始，注意这里的等待队列并不是设备等待队列，只是一个 epoll 内部定义的等待队列）。这也能节省不少的开销。

调度算法

1. 先来先服务(FCFS, First Come First Serve)
2. 短作业优先(SJF, Shortest Job First)
3. 最高优先权调度(Priority Scheduling)
4. 时间片轮转(RR, Round Robin)
5. 多级反馈队列调度(multilevel feedback queue scheduling)

常见的调度算法总结:http://www.jianshu.com/p/6edf8174c1eb (opens new window) 我猜，每个程序员对着电梯都想过调度算法吧? (opens new window)

实时调度算法:

1. 最早截至时间优先 EDF
2. 最低松弛度优先 LLF

死锁

什么是死锁

所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 因此我们举个例子来描述，如果此时有一个线程 A，按照先锁 a 再获得锁 b 的的顺序获得锁，而在此同时又有另外一个线程 B，按照先锁 b 再锁 a 的顺序获得锁。如下图所示：

产生死锁的原因

可归结为如下两点：

a. 竞争资源

• 系统中的资源可以分为两类：

  1. 可剥夺资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU 和主存均属于可剥夺性资源；
  2. 另一类资源是不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

• 产生死锁中的竞争资源之一指的是竞争不可剥夺资源（例如：系统中只有一台打印机，可供进程 P1 使用，假定 P1 已占用了打印机，若 P2 继续要求打印机打印将阻塞）

• 产生死锁中的竞争资源另外一种资源指的是竞争临时资源（临时资源包括硬件中断、信号、消息、缓冲区内的消息等），通常消息通信顺序进行不当，则会产生死锁

b. 进程间推进顺序非法

• 若 P1 保持了资源 R1,P2 保持了资源 R2，系统处于不安全状态，因为这两个进程再向前推进，便可能发生死锁
• 例如，当 P1 运行到 P1：Request（R2）时，将因 R2 已被 P2 占用而阻塞；当 P2 运行到 P2：Request（R1）时，也将因 R1 已被 P1 占用而阻塞，于是发生进程死锁

死锁产生的 4 个必要条件

1. 互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
2. 请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
4. 环路等待条件：在发生死锁时，必然存在一个进程--资源的环形链。

解决死锁的基本方法

预防死锁

• 资源一次性分配：一次性分配所有资源，这样就不会再有请求了：（破坏请求条件）
• 只要有一个资源得不到分配，也不给这个进程分配其他的资源：（破坏请保持条件）
• 可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）
• 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）

1、以确定的顺序获得锁

如果必须获取多个锁，那么在设计的时候需要充分考虑不同线程之前获得锁的顺序。按照上面的例子，两个线程获得锁的时序图如下：

如果此时把获得锁的时序改成：

那么死锁就永远不会发生。 针对两个特定的锁，开发者可以尝试按照锁对象的 hashCode 值大小的顺序，分别获得两个锁，这样锁总是会以特定的顺序获得锁，那么死锁也不会发生。问题变得更加复杂一些，如果此时有多个线程，都在竞争不同的锁，简单按照锁对象的 hashCode 进行排序（单纯按照 hashCode 顺序排序会出现“环路等待”），可能就无法满足要求了，这个时候开发者可以使用银行家算法，所有的锁都按照特定的顺序获取，同样可以防止死锁的发生，该算法在这里就不再赘述了，有兴趣的可以自行了解一下。

2、超时放弃

当使用 synchronized 关键词提供的内置锁时，只要线程没有获得锁，那么就会永远等待下去，然而 Lock 接口提供了 boolean tryLock(long time, TimeUnit unit) throws InterruptedException 方法，该方法可以按照固定时长等待锁，因此线程可以在获取锁超时以后，主动释放之前已经获得的所有的锁。通过这种方式，也可以很有效地避免死锁。 还是按照之前的例子，时序图如下：

避免死锁

• 预防死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得 较满意的系统性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。
• 银行家算法：首先需要定义状态和安全状态的概念。系统的状态是当前给进程分配的资源情况。因此，状态包含两个向量 Resource（系统中每种资源的总量）和 Available（未分配给进程的每种资源的总量）及两个矩阵 Claim（表示进程对资源的需求）和 Allocation（表示当前分配给进程的资源）。安全状态是指至少有一个资源分配序列不会导致死锁。当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态。如果是，同意这个请求；如果不是，阻塞该进程知道同意该请求后系统状态仍然是安全的。

检测死锁

1. 首先为每个进程和每个资源指定一个唯一的号码；
2. 然后建立资源分配表和进程等待表。

解除死锁

当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有：

• 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；
• 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态.消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。

死锁概念处理策略详细介绍：

• 死锁面试题（什么是死锁，产生死锁的原因及必要条件）_hd12370 的博客-CSDN 博客 (opens new window)
• 2.4、死锁 | 王道考研操作系统知识点整理 (opens new window)

import threading
from contextlib import contextmanager
# Thread-local state to stored information on locks already acquired
_local = threading.local()  # 用于记录锁已经释放

def acquire(*locks):
    pass

程序编译与链接

推荐: http://www.ruanyifeng.com/blog/2014/11/compiler.html (opens new window)

Bulid 过程可以分解为 4 个步骤:预处理(Prepressing), 编译(Compilation)、汇编(Assembly)、链接(Linking)

以 C 语言为例:

预处理

预编译过程主要处理那些源文件中的以“#”开始的预编译指令，主要处理规则有：

1. 将所有的“#define”删除，并展开所用的宏定义
2. 处理所有条件预编译指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”
3. 处理“#include”预编译指令，将被包含的文件插入到该编译指令的位置，注：此过程是递归进行的
4. 删除所有注释
5. 添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或警告时可显示行号
6. 保留所有的#pragma 编译器指令。

编译

编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。这个过程是整个程序构建的核心部分。

汇编

汇编器是将汇编代码转化成机器可以执行的指令，每一条汇编语句几乎都是一条机器指令。经过编译、链接、汇编输出的文件成为目标文件(Object File)

链接

链接的主要内容就是把各个模块之间相互引用的部分处理好，使各个模块可以正确的拼接。 链接的主要过程包块 地址和空间的分配（Address and Storage Allocation）、符号决议(Symbol Resolution)和重定位(Relocation)等步骤。

静态链接和动态链接

静态链接方法：静态链接的时候，载入代码就会把程序会用到的动态代码或动态代码的地址确定下来 静态库的链接可以使用静态链接，动态链接库也可以使用这种方法链接导入库

动态链接方法：使用这种方式的程序并不在一开始就完成动态链接，而是直到真正调用动态库代码时，载入程序才计算(被调用的那部分)动态代码的逻辑地址，然后等到某个时候，程序又需要调用另外某块动态代码时，载入程序又去计算这部分代码的逻辑地址，所以，这种方式使程序初始化时间较短，但运行期间的性能比不上静态链接的程序

虚拟内存技术

虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储系统.

分页和分段

分页: 用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

分段: 将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

分页与分段的主要区别

1. 页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.
2. 页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.
3. 分页的作业地址空间是一维的.分段的地址空间是二维的.

页面置换算法

1. 页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.
2. 页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分。
3. 分页的作业地址空间是一维的、分段的地址空间是二维的。

页面置换：在地址映射过程中，若所要访问的页面不在内存中，则产生了‘缺页中断(page fault)’。此时操作系统必须在内存中选择一个页面将其移出内存，为即将调入的页面让出空间。

1. 最佳置换算法 OPT (optional replacement)：被替换的页面为在未来最长时间内不会被访问的页面，可保证最低的缺页率，但不可能实现，主要用于评估算法。
2. 先进先出 FIFO：最易实现，但会频繁换页，性能差。
3. 最近最久未使用算法 LRU (Least Recently Used)：最近一段时间里最久没有使用过的页面予以置换。
4. 时钟替换算法 (Clock)：依照使用位替换页面。

边沿触发和水平触发

边缘触发是指每当状态变化时发生一个 io 事件，条件触发是只要满足条件就发生一个 io 事件

1. 边沿触发 (Edge Trigger)：自上次状态改变后有新的 I/O 事件就会触发通知，需要尽可能多的执行 I/O 操作。
2. 水平触发 (Level Trigger)：准备就绪时（可非阻塞地执行 I/O 系统调用）触发通知，可在任意时刻重复检测 I/O 状态。

数据库

事务

数据库事务(Database Transaction) ，是指作为单个逻辑工作单元执行的一系列操作，要么完全地执行，要么完全地不执行。 参见MySQL 事务

数据库索引

参见MySQL 索引原理

Redis

这里有一个我本人整理的PPT知识分享,有兴趣的话可以看看： PPT 知识分享 (opens new window)

Redis 是什么

1. 是一个完全开源免费的 key-value 内存数据库
2. 通常被认为是一个数据结构服务器，主要是因为其有着丰富的数据结构 strings、hash、 list、sets、 sorted sets

Redis 数据库

通常局限点来说，Redis 也以消息队列的形式存在，作为内嵌的 List 存在，满足实时的高并发需求。在使用缓存的时候，redis 比 memcached 具有更多的优势，并且支持更多的数据类型，把 redis 当作一个中间存储系统，用来处理高并发的数据库操作。

• 速度快：使用标准 C 写，所有数据都在内存中完成，读写速度分别达到 10 万/20 万
• 持久化：对数据的更新采用 Copy-on-write 技术，可以异步地保存到磁盘上，主要有两种策略，一是根据时间，更新次数的快照（save 300 10 ）二是基于语句追加方式(Append-only file，aof)
• 原子操作：对不同数据类型的操作都是原子的（automatic），很安全
• 快速的主——从复制，官方提供了一个数据，Slave 在 21 秒即完成了对 Amazon 网站 10G key set 的复制。
• Sharding 技术： 很容易将数据分布到多个 Redis 实例中，数据库的扩展是个永恒的话题，在关系型数据库中，主要是以添加硬件、以分区为主要技术形式的纵向扩展解决了很多的应用场景，但随着 web2.0、移动互联网、云计算等应用的兴起，这种扩展模式已经不太适合了，所以近年来，像采用主从配置、数据库复制形式的，Sharding 这种技术把负载分布到多个特理节点上去的横向扩展方式用处越来越多。

Redis 缺点

• 是数据库容量受到物理内存的限制,不能用作海量数据的高性能读写,因此 Redis 适合的场景主要局限在较小数据量的高性能操作和运算上。
• Redis 较难支持在线扩容，在集群容量达到上限时在线扩容会变得很复杂。为避免这一问题，运维人员在系统上线时必须确保有足够的空间，这对资源造成了很大的浪费。

如何保证 Redis 缓存和数据库的一致性

缓存服务（Redis）和数据服务（底层数据库）是相互独立且异构的系统，在更新缓存或更新数据的时候无法做到原子性的同时更新两边的数据，因此在并发读写或第二步操作异常时会遇到各种数据不一致的问题。 缓存更新的设计模式有四种：

Cache aside：查询：先查缓存，缓存没有就查数据库，然后加载至缓存内；更新：先更新数据库，然后让缓存失效；或者先失效缓存然后更新数据库；
Read through：在查询操作中更新缓存，即当缓存失效时，Cache Aside 模式是由调用方负责把数据加载入缓存，而 Read Through 则用缓存服务自己来加载；
Write through：在更新数据时发生。当有数据更新的时候，如果没有命中缓存，直接更新数据库，然后返回。如果命中了缓存，则更新缓存，然后由缓存自己更新数据库；
Write behind caching：俗称write back，在更新数据的时候，只更新缓存，不更新数据库，缓存会异步地定时批量更新数据库；

Writing Policies (opens new window)

• write-through

  直写模式，在数据更新时，同时写入缓存 Cache 和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢。

• write-behind

  回写模式，在数据更新时只写入缓存 Cache。只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快，因为不需要写存储；缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况，数据将无法找回。

  对于写操作，存在写入缓存缺失数据的情况，这时有两种处理方式：

Write allocate (aka Fetch on write) - Datum at the missed-write location is loaded to cache, followed by a write-hit operation. In this approach, write misses are similar to read-misses.

No-write allocate (aka Write-no-allocate, Write around) - Datum at the missed-write location is not loaded to cache, and is written directly to the backing store. In this approach, actually only system reads are being cached.

Write allocate 方式将写入位置读入缓存，然后采用 write-hit（缓存命中写入）操作。写缺失操作与读缺失操作类似。

No-write allocate 方式并不将写入位置读入缓存，而是直接将数据写入存储。这种方式下，只有读操作会被缓存。

无论是 Write-through 还是 Write-back 都可以使用写缺失的两种方式之一。只是通常 Write-back 采用 Write allocate 方式，而 Write-through 采用 No-write allocate 方式；因为多次写入同一缓存时，Write allocate 配合 Write-back 可以提升性能；而对于 Write-through 则没有帮助。

Write-through 模式处理流程

Write-back 模式处理流程

ref: Cache 写机制：Write-through 与 Write-back - 枫芸志 (opens new window)

Redis 为什么这么快

• 基于内存存储
• 单线程，避免上下文切换引起的资源竞争
• 在 epoll 的基础上实现的自己是事件库，实现 io 多路复用
• 数据结构：hash 存储，跳跃表，双端链表等底层数据结构实现数据存储

参阅为什么 Redis 这么快？

redis 支持事务吗

是的，Redis 支持事务。Redis 的事务是通过 MULTI、EXEC、WATCH 和 UNWATCH、DISCARD 等命令实现的。

1. MULTI 命令用于开启一个事务
2. WATCH 和 UNWATCH 命令用于对事务进行监视和取消监视。在事务中，所有的命令都会被放入一个队列中，直到执行 EXEC 命令时才会一起执行。如果在执行 EXEC 命令之前，有其他客户端对被监视的键进行了修改，那么事务将会被取消，不会执行任何命令。
3. DISCARD：取消事务并清空事务队列。当执行 DISCARD 命令后，Redis 会取消当前客户端的事务，并清空事务队列中的所有命令。这意味着事务中的所有命令都不会被执行。DISCARD 命令可以用于放弃之前的事务，重新开始一个新的事务。
4. EXEC 命令用于执行事务中的命令

• 是否满足 ACID

  1. Redis 具备了一定的原子性，但不支持回滚。

  笔记

  DISCARD 命令只能取消当前事务中的命令执行，并不能回滚已经执行的命令。

  在 Redis 事务中，如果 EXEC 命令执行过程中发生了错误，比如其中一个命令执行失败，那么事务中所有已经执行的命令都会被回滚，但是 Redis 并不会抛出异常或者提供回滚的机制。因此，Redis 的事务并不保证原子性。

  2. Redis 具备 ACID 中一致性的概念。
  3. Redis 具备隔离性。
  4. Redis 无法保证持久性。

Redis 事务支持 ACID 么？ - 知乎 (opens new window)

乐观锁和悲观锁

悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作

乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。

乐观锁与悲观锁的具体区别: https://my.oschina.net/feixuewuhen/blog/800346 (opens new window)

MVCC

MVCC（Multi-Version Concurrency Control）是一种并发控制机制，用于解决数据库系统中的并发读写冲突问题。它通过为每个事务创建不同的数据版本来实现并发控制，从而提高数据库系统的并发性能和事务的隔离性。

在 MVCC 中，每个事务都可以看到数据库中的一个一致性快照，即某个时间点的数据版本。事务读取数据时，会根据自己的事务 ID 和数据版本的时间戳来确定可见的数据。如果某个数据版本的时间戳早于事务开始的时间戳，则该数据对该事务不可见。

当一个事务修改数据时，会创建一个新的数据版本，并将新版本的时间戳设置为事务的开始时间戳。其他事务仍然可以读取旧版本的数据，不会受到该事务的修改影响。

MVCC 具有较好的并发性能，因为它允许多个事务同时读取数据库中的数据，只有在写入冲突时才会发生锁等待。同时，MVCC 也提供了较好的隔离性，事务之间不会相互干扰，读取到的数据是一致的。

MVCC 在许多数据库系统中得到了广泛应用，如 Oracle、PostgreSQL 等。它是实现高并发和事务隔离的重要技术之一。

需要注意的是，REPEATABLE READ 级别下仍然可能出现幻读问题。在 REPEATABLE READ 级别下，每个事务在开始时会创建一个一致性视图，该视图包含了事务开始时数据库中的所有数据版本。事务读取数据时，只能看到事务开始时的数据版本，而不会受到其他事务的修改影响。

然而，当其他事务在 REPEATABLE READ 级别下对数据进行插入或删除操作时，仍然有可能导致幻读问题。这是因为 REPEATABLE READ 级别只能保证读取过程中不会读取到其他事务已经修改的数据，但无法阻止其他事务在读取过程中插入新的数据或删除已有的数据。

为了解决幻读问题，可以使用更高级别的事务隔离级别，如 SERIALIZABLE。在 SERIALIZABLE 级别下，会对读取的数据范围进行锁定，防止其他事务在读取过程中插入或删除数据，从而避免幻读问题的发生。

总结起来，虽然 MySQL 的默认事务隔离级别（REPEATABLE READ）使用了 MVCC 机制来提供一致性视图，但仍然不能完全解决幻读问题。要彻底解决幻读问题，可以考虑使用更高级别的事务隔离级别（如 SERIALIZABLE）或使用锁机制来保证数据的一致性。

MySQL 的 innodb 引擎是如何实现 MVCC 的

MVCC 的原理如下：

每个事务在开始时都会被分配一个唯一的事务 ID（Transaction ID）。 在数据库中的每个数据行都会保存两个隐藏的列，分别是创建版本号（Creation Version）和删除版本号（Deletion Version），填入的是事务的版本号，这个版本号随着事务的创建不断递增。

• 当一个事务修改某个数据行时，会创建该数据行的新版本，并将该版本的创建版本号设置为当前事务的事务 ID。同时，将该数据行的删除版本号设置为无穷大。
• 当一个事务删除某个数据行时，会将该数据行的删除版本号设置为当前事务的事务 ID。
• 当一个事务查询某个数据行时，会根据该数据行的创建版本号和删除版本号来确定是否可见。具体规则如下：

1. 如果数据行的创建版本号大于当前事务的事务 ID，说明该数据行是由尚未提交的事务创建的，对于当前事务来说是不可见的。
2. 如果数据行的删除版本号小于或等于当前事务的事务 ID，说明该数据行是由已提交的事务删除的，对于当前事务来说是不可见的。
3. 如果数据行的创建版本号小于或等于当前事务的事务 ID，且删除版本号大于当前事务的事务 ID，说明该数据行是对于当前事务可见的。

通过 MVCC 机制，MySQL 可以在不加锁的情况下实现并发访问，提高了数据库的并发性能。同时，MVCC 也保证了事务之间的隔离性，每个事务只能看到自己开始之前的数据快照，不会受到其他事务的干扰。

innodb 会为每一行添加两个字段，分别表示该行创建的版本和删除的版本，填入的是事务的版本号，这个版本号随着事务的创建不断递增。在 repeated read 的隔离级别（事务的隔离级别请看这篇文章 (opens new window)）下，具体各种数据库操作的实现：

• select：满足以下两个条件 innodb 会返回该行数据：
  • 该行的创建版本号小于等于当前版本号，用于保证在 select 操作之前所有的操作已经执行落地。
  • 该行的删除版本号大于当前版本或者为空。删除版本号大于当前版本意味着有一个并发事务将该行删除了。
• insert：将新插入的行的创建版本号设置为当前系统的版本号。
• delete：将要删除的行的删除版本号设置为当前系统的版本号。
• update：不执行原地 update，而是转换成 insert + delete。将旧行的删除版本号设置为当前版本号，并将新行 insert 同时设置创建版本号为当前版本号。

其中，写操作（insert、delete 和 update）执行时，需要将系统版本号递增。

由于旧数据并不真正的删除，所以必须对这些数据进行清理，innodb 会开启一个后台线程执行清理工作，具体的规则是将删除版本号小于当前系统版本的行删除，这个过程叫做 purge。

通过 MVCC 很好的实现了事务的隔离性，可以达到 repeated read 级别，要实现 serializable 还必须加锁。

参考：MVCC 浅析 (opens new window)

当前读、快照读、MVCC

【MySQL】当前读、快照读、MVCC - wwcom123 - 博客园 (opens new window) Innodb MVCC 实现原理 - 勤劳的小手的文章 - 知乎 (opens new window)

MyISAM 和 InnoDB

MyISAM 和 InnoDB 是 MySQL 数据库中两种最常用的存储引擎。它们有以下几个区别：

1. 事务支持：MyISAM 不支持事务处理，而 InnoDB 支持事务。事务是一组关联操作的原子性单位，可以保证数据在一组操作中的完整性和一致性。

2. 行级锁定：InnoDB 支持行级锁定，即只锁定被操作的行，而 MyISAM 只支持表级锁定，即每次操作时锁定整个表。行级锁定提高了并发性和并发操作的吞吐量。

3. 外键支持：InnoDB 支持外键，而 MyISAM 不支持外键。外键是表与表之间的关联关系，可以确保数据的完整性和一致性。

4. 全文检索：MyISAM 支持全文检索，而 InnoDB 不支持。全文检索是一种高级的文本搜索功能，可以对数据库中的文本字段进行搜索和匹配。

   笔记

   从 MySQL 5.6 版本开始，InnoDB 引擎开始支持全文检索。全文检索功能的引入使得 InnoDB 成为一个更全面和综合的存储引擎选择，可以满足更广泛的应用需求。全文检索功能可以快速地搜索和匹配文本字段，使得文本搜索更加高效和灵活。

5. 崩溃恢复：InnoDB 支持崩溃恢复，具有自动回滚和故障恢复的能力，而 MyISAM 不支持。这意味着在出现故障或崩溃时，InnoDB 可以自动恢复数据库的稳定状态，而 MyISAM 则需要手动恢复。

总结来说，MyISAM 适用于读密集型的应用，而 InnoDB 适用于读写混合或写密集型的应用。选择合适的存储引擎取决于应用的需求和性能要求。

MyISAM 适合于一些需要大量查询的应用，但其对于有大量写操作并不是很好。甚至你只是需要 update 一个字段，整个表都会被锁起来，而别的进程，就算是读进程都无法操作直到读操作完成。另外，MyISAM 对于 SELECT COUNT(*) 这类的计算是超快无比的。

InnoDB 的趋势会是一个非常复杂的存储引擎，对于一些小的应用，它会比 MyISAM 还慢。但是它支持“行锁” ，于是在写操作比较多的时候，会更优秀。并且，他还支持更多的高级应用，比如：事务。

mysql 数据库引擎: http://www.cnblogs.com/0201zcr/p/5296843.html (opens new window)

MySQL 存储引擎－－MyISAM 与 InnoDB 区别: https://segmentfault.com/a/1190000008227211 (opens new window)

什么是 binlog、redo log

MySQL 的 binlog（二进制日志）和 redo log（重做日志）都是 MySQL 用于数据恢复和复制的重要日志文件，但它们的功能和工作方式存在一些区别。

1. 功能区别

   binlog 主要用于 MySQL 的主从复制和数据恢复。在主从复制中，主库的 binlog 事件会被复制到从库进行重放，从而达到主从数据一致的目的。在数据恢复中，可以通过回放 binlog 来恢复数据。

   redo log 是 InnoDB 存储引擎特有的日志，主要用于保证事务的持久性（Durability）。在事务提交时，先将修改记录到 redo log，然后再慢慢的刷新到磁盘，这样即使系统崩溃，也可以通过 redo log 恢复数据。

2. 格式区别

   binlog 是逻辑日志，记录了数据库的所有 DDL 和 DML 操作，但不包括 SELECT 操作和未提交的事务。

   redo log 是物理日志，记录的是对于数据页的物理修改操作，比如“在某个数据页的某个位置，将某个值修改为另一个值”。

3. 写入方式区别

   binlog 是追加写入，可以无限增大，直到磁盘满。需要定期进行清理。

   redo log 是循环写入，空间大小固定，不会因为业务的增长而增大。

4. 存储引擎区别

   binlog 是 MySQL Server 层实现的，所有存储引擎都可以使用。

   redo log 是 InnoDB 存储引擎特有的。

总的来说，binlog 更侧重于逻辑层面的操作记录，用于数据复制和恢复；而 redo log 更侧重于物理层面的数据修改，用于保证事务的持久性。

binlog 属于逻辑日志，是逻辑操作。innodb redo log 属于物理日志，是物理变更。逻辑日志有个缺点是难以并行，而物理日志可以比较好的并行操作。

1. binlog 是 MySQL Server 层记录的日志， redo log 是 InnoDB 存储引擎层的日志。 两者都是记录了某些操作的日志(不是所有)自然有些重复（但两者记录的格式不同）。
2. 选择 binlog 日志作为 replication

参阅Redo log, bin log, Undo log

• MySQL 中的重做日志（redo log），回滚日志（undo log），以及二进制日志（binlog）的简单总结 (opens new window)
• mysql 基础：binlog、redo log (opens new window)
• MySQL-重做日志 redo log -原理 (opens new window)

Redis如何保持和MySQL数据一致

1. MySQL 持久化数据,Redis 只读数据

   redis 在启动之后，从数据库加载数据。

   读请求：

   不要求强一致性的读请求，走 redis，要求强一致性的直接从 mysql 读取

   写请求：

   数据首先都写到数据库，之后更新 redis（先写 redis 再写 mysql，如果写入失败事务回滚会造成 redis 中存在脏数据）

2. MySQL 和 Redis 处理不同的数据类型

   MySQL 处理实时性数据，例如金融数据、交易数据；

   Redis 处理实时性要求不高的数据，例如网站最热贴排行榜，好友列表等。

• Redis 如何保持和 MySQL 数据一致 (opens new window)
• 如何保持 mysql 和 redis 中数据的一致性？ (opens new window)

CAP 理论

CAP 理论：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。 一致性（Consistency | all nodes see the same data at the same time）：更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致；

可用性（Availability | Reads and writes always succeed）：服务一直可用，而且是正常响应时间；

分区容错性（Partition tolerance | the system continues to operate despite arbitrary message loss or failure of part of the system）：即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求能够使应用虽然是一个分布式系统，而看上去却好像是在一个可以运转正常的整体。

比如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求；或者是机器之间有网络异常，将分布式系统分隔为独立的几个部分，各个部分还能维持分布式系统的运作，这样就具有好的分区容错性。

简单点说，就是在网络中断，消息丢失的情况下，系统如果还能正常工作，就是有比较好的分区容错性。 注意: CAP 理论中的 CA 和数据库事务中 ACID 的 CA 并不完全是同一回事儿。两者之中的 A 都是 C 都是一致性(Consistency)。CAP 中的 A 指的是可用性（Availability），而 ACID 中的 A 指的是原子性（Atomicity)，切勿混为一谈。

• 分布式系统的 CAP 理论 (opens new window)

网络

三次握手

1. 客户端通过向服务器端发送一个 SYN 来创建一个主动打开，作为三次握手的一部分。客户端把这段连接的序号设定为随机数 A。
2. 服务器端应当为一个合法的 SYN 回送一个 SYN/ACK。ACK 的确认码应为 A+1，SYN/ACK 包本身又有一个随机序号 B。
3. 最后，客户端再发送一个 ACK。当服务端受到这个 ACK 的时候，就完成了三路握手，并进入了连接创建状态。此时包序号被设定为收到的确认号 A+1，而响应则为 B+1。

四次挥手

注意: 中断连接端可以是客户端，也可以是服务器端. 下面仅以客户端断开连接举例, 反之亦然.

1. 客户端发送一个数据分段, 其中的 FIN 标记设置为 1. 客户端进入 FIN-WAIT 状态. 该状态下客户端只接收数据, 不再发送数据.
2. 服务器接收到带有 FIN = 1 的数据分段, 发送带有 ACK = 1 的剩余数据分段, 确认收到客户端发来的 FIN 信息.
3. 服务器等到所有数据传输结束, 向客户端发送一个带有 FIN = 1 的数据分段, 并进入 CLOSE-WAIT 状态, 等待客户端发来带有 ACK = 1 的确认报文.
4. 客户端收到服务器发来带有 FIN = 1 的报文, 返回 ACK = 1 的报文确认, 为了防止服务器端未收到需要重发, 进入 TIME-WAIT 状态. 服务器接收到报文后关闭连接. 客户端等待 2MSL 后未收到回复, 则认为服务器成功关闭, 客户端关闭连接.

图解: http://blog.csdn.net/whuslei/article/details/6667471 (opens new window)

ARP 协议

地址解析协议(Address Resolution Protocol)，其基本功能为透过目标设备的 IP 地址，查询目标的 MAC 地址，以保证通信的顺利进行。它是 IPv4 网络层必不可少的协议，不过在 IPv6 中已不再适用，并被邻居发现协议（NDP）所替代。

urllib 和 urllib2 的区别

这个面试官确实问过,当时答的 urllib2 可以 Post 而 urllib 不可以.

1. urllib 提供 urlencode 方法用来 GET 查询字符串的产生，而 urllib2 没有。这是为何 urllib 常和 urllib2 一起使用的原因。
2. urllib2 可以接受一个 Request 类的实例来设置 URL 请求的 headers，urllib 仅可以接受 URL。这意味着，你不可以伪装你的 User Agent 字符串等。

POST 和 GET

从标准上来看，GET 和 POST 的区别如下：

• GET 用于获取信息，是无副作用的，是幂等的，且可缓存；

• POST 用于修改服务器上的数据，有副作用，非幂等，不可缓存；

但是，既然本文从报文角度来说，那就先不讨论 RFC 上的区别，单纯从数据角度谈谈。

GET 和 POST 报文上的区别

先下结论，GET 和 POST 方法没有实质区别，只是报文格式不同。

GET 和 POST 只是 HTTP 协议中两种请求方式，而 HTTP 协议是基于 TCP/IP 的应用层协议，无论 GET 还是 POST，用的都是同一个传输层协议，所以在传输上，没有区别。

报文格式上，不带参数时，最大区别就是第一行方法名不同

POST 方法请求报文第一行是这样的 POST /uri HTTP/1.1 \r\n

GET 方法请求报文第一行是这样的 GET /uri HTTP/1.1 \r\n

常见问题及疑惑

• GET 使用 URL 或 Cookie 传参。而 POST 将数据放在 BODY 中。

  在约定中，我们的参数是写在 ? 后面，用 & 分割。

  我们知道，解析报文的过程是通过获取 TCP 数据，用正则等工具从数据中获取 Header 和 Body，从而提取参数。

  也就是说，我们可以自己约定参数的写法，只要服务端能够解释出来就行，一种比较流行的写法是 http://www.example.com/user/name/chengqm/age/22。

• GET 的 URL 会有长度上的限制，则 POST 的数据则可以非常大。

  说明一点，HTTP 协议没有 Body 和 URL 的长度限制，对 URL 限制的大多是浏览器和服务器的原因。

  浏览器原因就不说了，服务器是因为处理长 URL 要消耗比较多的资源，为了性能和安全（防止恶意构造长 URL 来攻击）考虑，会给 URL 长度加限制。

• POST 比 GET 安全，因为数据在地址栏上不可见。

  然而，这种安全是相对的。从传输的角度来说，他们都是不安全的。因为 HTTP 在网络上是明文传输的，只要在网络节点上捉包，就能完整地获取数据报文。

  要想安全传输，就只有加密，也就是 HTTPS。

其次:

"GET 和 POST 与数据如何传递没有关系" 是不对的，HTTP 协议有相关的规定。 参考: http://stackoverflow.com/questions/978061/http-get-with-request-body (opens new window)

"安全不安全和 GET、POST 没有关系"

这里的"安全"也可以理解为"幂等"，事实上需要避免通过 GET 请求执行会改变状态的操作。 参考: http://www.yining.org/2010/05/04/http-get-vs-post-and-thoughts/ (opens new window)

知乎回答 (opens new window)

9012 年了，还问 GET 和 POST 的区别 (opens new window)

GET: RFC 2616 - Hypertext Transfer Protocol -- HTTP/1.1 (opens new window) POST: RFC 2616 - Hypertext Transfer Protocol -- HTTP/1.1 (opens new window)

Cookie 和 Session

	Cookie	Session
储存位置	客户端	服务器端
目的	跟踪会话，也可以保存用户偏好设置或者保存用户名密码等	跟踪会话
安全性	不安全	安全

session 技术是要使用到 cookie 的，之所以出现 session 技术，主要是为了安全。

apache 和 nginx 的区别

nginx 相对 apache 的优点：

• 轻量级，同样起 web 服务，比 apache 占用更少的内存及资源
• 抗并发，nginx 处理请求是异步非阻塞的，支持更多的并发连接，而 apache 则是阻塞型的，在高并发下 nginx 能保持低资源低消耗高性能
• 配置简洁
• 高度模块化的设计，编写模块相对简单
• 社区活跃

apache 相对 nginx 的优点：

• rewrite ，比 nginx 的 rewrite 强大
• 模块超多，基本想到的都可以找到
• 少 bug ，nginx 的 bug 相对较多
• 超稳定

网站用户密码保存

1. 明文保存 2. 明文 hash 后保存,如 md5 3. MD5+Salt 方式,这个 salt 可以随机 4. 知乎使用了 Bcrypy(好像)加密

HTTP 和 HTTPS

状态码	定义
1xx 报告	接收到请求，继续进程
2xx 成功	步骤成功接收，被理解，并被接受
3xx 重定向	为了完成请求,必须采取进一步措施
4xx 客户端出错	请求包括错的顺序或不能完成
5xx 服务器出错	服务器无法完成显然有效的请求

403: Forbidden 404: Not Found

HTTPS 握手,对称加密,非对称加密,TLS/SSL,RSA

XSRF 和 XSS

• CSRF(Cross-site request forgery)跨站请求伪造
• XSS(Cross Site Scripting)跨站脚本攻击

CSRF 重点在请求,XSS 重点在脚本

幂等 Idempotence

HTTP 方法的幂等性是指一次和多次请求某一个资源应该具有同样的副作用。(注意是副作用)

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 方法具有幂等性。

RESTful 架构(SOAP,RPC)

推荐: http://www.ruanyifeng.com/blog/2011/09/restful.html (opens new window)

SOAP

SOAP（原为 Simple Object Access Protocol 的首字母缩写，即简单对象访问协议）是交换数据的一种协议规范，使用在计算机网络 Web 服务（web service）中，交换带结构信息。SOAP 为了简化网页服务器（Web Server）从 XML 数据库中提取数据时，节省去格式化页面时间，以及不同应用程序之间按照 HTTP 通信协议，遵从 XML 格式执行资料互换，使其抽象于语言实现、平台和硬件。

RPC

RPC（Remote Procedure Call Protocol）——远程过程调用协议，它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。RPC 协议假定某些传输协议的存在，如 TCP 或 UDP，为通信程序之间携带信息数据。在 OSI 网络通信模型中，RPC 跨越了传输层和应用层。RPC 使得开发包括网络分布式多程序在内的应用程序更加容易。

总结:服务提供的两大流派.传统意义以方法调用为导向通称 RPC。为了企业 SOA,若干厂商联合推出 webservice,制定了 wsdl 接口定义,传输 soap.当互联网时代,臃肿 SOA 被简化为 http+xml/json.但是简化出现各种混乱。以资源为导向,任何操作无非是对资源的增删改查，于是统一的 REST 出现了.

进化的顺序: RPC -> SOAP -> RESTful

CGI 和 WSGI

CGI 是通用网关接口，是连接 web 服务器和应用程序的接口，用户通过 CGI 来获取动态数据或文件等。 CGI 程序是一个独立的程序，它可以用几乎所有语言来写，包括 perl，c，lua，Python 等等。

WSGI, Web Server Gateway Interface，是 Python 应用程序或框架和 Web 服务器之间的一种接口，WSGI 的其中一个目的就是让用户可以用统一的语言(Python)编写前后端。

官方说明：PEP-3333 (opens new window)

中间人攻击

在 GFW 里屡见不鲜的,呵呵.

中间人攻击（Man-in-the-middle attack，通常缩写为 MITM）是指攻击者与通讯的两端分别创建独立的联系，并交换其所收到的数据，使通讯的两端认为他们正在通过一个私密的连接与对方直接对话，但事实上整个会话都被攻击者完全控制。

c10k 问题

所谓 c10k 问题，指的是服务器同时支持成千上万个客户端的问题，也就是 concurrent 10 000 connection（这也是 c10k 这个名字的由来）。 推荐: https://my.oschina.net/xianggao/blog/664275 (opens new window)

TCP

socket

推荐: http://www.360doc.com/content/11/0609/15/5482098_122692444.shtml (opens new window)

Socket=Ip address+ TCP/UDP + port

浏览器缓存

推荐: http://www.cnblogs.com/skynet/archive/2012/11/28/2792503.html (opens new window)

304 Not Modified

HTTP1.0 和 HTTP1.1

推荐: http://blog.csdn.net/elifefly/article/details/3964766 (opens new window)

1. 请求头 Host 字段,一个服务器多个网站
2. 长链接
3. 文件断点续传
4. 身份认证,状态管理,Cache 缓存

HTTP 请求 8 种方法介绍 HTTP/1.1 协议中共定义了 8 种 HTTP 请求方法，HTTP 请求方法也被叫做“请求动作”，不同的方法规定了不同的操作指定的资源方式。服务端也会根据不同的请求方法做不同的响应。

GET

GET 请求会显示请求指定的资源。一般来说 GET 方法应该只用于数据的读取，而不应当用于会产生副作用的非幂等的操作中。

GET 会方法请求指定的页面信息，并返回响应主体，GET 被认为是不安全的方法，因为 GET 方法会被网络蜘蛛等任意的访问。

HEAD

HEAD 方法与 GET 方法一样，都是向服务器发出指定资源的请求。但是，服务器在响应 HEAD 请求时不会回传资源的内容部分，即：响应主体。这样，我们可以不传输全部内容的情况下，就可以获取服务器的响应头信息。HEAD 方法常被用于客户端查看服务器的性能。

POST

POST 请求会 向指定资源提交数据，请求服务器进行处理，如：表单数据提交、文件上传等，请求数据会被包含在请求体中。POST 方法是非幂等的方法，因为这个请求可能会创建新的资源或/和修改现有资源。

PUT

PUT 请求会身向指定资源位置上传其最新内容，PUT 方法是幂等的方法。通过该方法客户端可以将指定资源的最新数据传送给服务器取代指定的资源的内容。

DELETE

DELETE 请求用于请求服务器删除所请求 URI（统一资源标识符，Uniform Resource Identifier）所标识的资源。DELETE 请求后指定资源会被删除，DELETE 方法也是幂等的。

CONNECT

CONNECT 方法是 HTTP/1.1 协议预留的，能够将连接改为管道方式的代理服务器。通常用于 SSL 加密服务器的链接与非加密的 HTTP 代理服务器的通信。

OPTIONS

OPTIONS 请求与 HEAD 类似，一般也是用于客户端查看服务器的性能。 这个方法会请求服务器返回该资源所支持的所有 HTTP 请求方法，该方法会用’*’来代替资源名称，向服务器发送 OPTIONS 请求，可以测试服务器功能是否正常。JavaScript 的 XMLHttpRequest 对象进行 CORS 跨域资源共享时，就是使用 OPTIONS 方法发送嗅探请求，以判断是否有对指定资源的访问权限。 允许

TRACE

TRACE 请求服务器回显其收到的请求信息，该方法主要用于 HTTP 请求的测试或诊断。

HTTP/1.1 之后增加的方法

在 HTTP/1.1 标准制定之后，又陆续扩展了一些方法。其中使用中较多的是 PATCH 方法：

PATCH

PATCH 方法出现的较晚，它在 2010 年的 RFC 5789 标准中被定义。PATCH 请求与 PUT 请求类似，同样用于资源的更新。二者有以下两点不同：

但 PATCH 一般用于资源的部分更新，而 PUT 一般用于资源的整体更新。 当资源不存在时，PATCH 会创建一个新的资源，而 PUT 只会对已有资源进行更新。

Ajax

AJAX,Asynchronous JavaScript and XML（异步的 JavaScript 和 XML）, 是与在不重新加载整个页面的情况下，与服务器交换数据并更新部分网页的技术。

WSGI、uWSGI、uwsgi、Nginx

原文链接 (opens new window)

WSGI

WSGI 的全称是 Web Server Gateway Interface（Web 服务器网关接口），它不是服务器、python 模块、框架、API 或者任何软件，只是一种描述 web 服务器（如 nginx，uWSGI 等服务器）如何与 web 应用程序（如用 Django、Flask 框架写的程序）通信的规范。

server 和 application 的规范在 PEP3333 中有具体描述，要实现 WSGI 协议，必须同时实现 web server 和 web application，当前运行在 WSGI 协议之上的 web 框架有 Bottle, Flask, Django。

uWSGI

uWSGI 是一个全功能的 HTTP 服务器，实现了 WSGI 协议、uwsgi 协议、http 协议等。它要做的就是把 HTTP 协议转化成语言支持的网络协议。比如把 HTTP 协议转化成 WSGI 协议，让 Python 可以直接使用。

uwsgi

与 WSGI 一样，是 uWSGI 服务器的独占通信协议，用于定义传输信息的类型(type of information)。每一个 uwsgi packet 前 4byte 为传输信息类型的描述，与 WSGI 协议是两种东西，据说该协议是 fcgi 协议的 10 倍快。（没有验证）

Nginx

Nginx 是一个 Web 服务器其中的 HTTP 服务器功能和 uWSGI 功能很类似，但是 Nginx 还可以用作更多用途，比如最常用的反向代理功能。 用一张图来描述一下上述过程：

总结

一个成熟的站点提供服务，需要 Web 服务器（静态数据）和 App 服务器（动态数据）。Web 服务器目前属Nginx最强大，用户请求代理过来后，把数据返回给请求客户端。但是目前的互联网发展时代，都是包含动态数据处理的，这样一般 Nginx 不处理业务逻辑，都外包给后端的 App 服务器，就是你的 Flask/Django。

在需要性能优化的场景，通常单单 nginx 和 uWSGI 也是不够的。nginx 主要优化的是连接数和静态文，uWSGI 主要优化的是wsgi 服务，这些都只是手段。其它手段包括，优化数据库，增加缓存，加入负载均衡器，引入异步 IO 框架（如 gunicorn 服务器的 gevent 框架），计算密集型模块用 C 重写等。安全性方面，也会有很多考虑。

简述 Django 请求生命周期

1. uWSGI 服务器通过 WSGI 协议, 将 HttpRequest 交给 web 框架
2. 首先到达 request 中间件，对请求对象进行校验或添加数据，例如：csrf、request.session，如果验证不通过直接跳转到 HttpResponse 中间件
3. 否则，通过 URL 配置文件找到 urls.py 文件进行匹配
4. 根据浏览器发送的 URL，通过视图中间件去匹配不同的视图函数或视图类_view_middleware，如果没有找到相对应的视图函数，就执行_exception_middleware跳转到 response 中间件
5. 在视图函数或视图类中进行业务逻辑处理，处理完返回到 response 中间件
6. 模型类通过 ORM 获取数据库数据，并返回序列化 json 或渲染好的 Template 到 response 中间件
7. 所有最后离开的响应都会到达 response 中间件_response_middleware，对响应的数据进行处理，返回 HttpResponse 给 WSGI
8. WSGI 经过 uWSGI 服务器, 将响应的内容发送给浏览器。

来源参考：

1. Django 从启动到请求到响应全过程分析-入门版 - 掘金 (opens new window)
2. 超详细的 Django 面试题_Alex-CSDN 博客 | 听风的小站 (opens new window)

简述 Flask 处理请求的过程

1. 创建请求上下文（RequestContext）

   • Request 请求的对象，封装了 Http 请求(environ)的内容
   • Session 根据请求中的 cookie，重新载入该访问者相关的会话信息。

   在 Flask 中处理请求时，就会产生一个 “请求上下文” 对象，整个请求的处理过程，都会在这个上下文对象中进行。 这保证了请求的处理过程不被干扰。包含了和请求处理相关的信息，同时 Flask 还根据 werkzeug.local 模块中实现的一种数据结构 LocalStack 用来存储“请求上下文”对象。

2. 创建应用上下文（AppContext）

• g 处理请求时用作临时存储的对象。每次请求都会重设这个变量

• current_app 当前激活程序的程序实例 它实现了 push、pop 等方法。 “应用上下文” 的构造函数也和 “请求上下文” 类似，都有 app、url_adapter 等属性。“应用上下文” 存在的一个主要功能就是确定请求所在的应用。

  1. 对于请求和响应的处理，Flask使用werkzeug库中的Request类和Response类。
  2. 实例化的 Flask 应用是一个可调用对象。在前面讲到，Web 应用要遵循WSGI规范，就要实现一个函数或者一个可调用对象webapp(environ, start_response)，以方便服务器或网关调用。Flask 应用通过__call__(environ, start_response)方法可以让它被服务器或网关调用。

  def __call__(self, environ, start_response):
      """Shortcut for :attr:`wsgi_app`"""
      return self.wsgi_app(environ, start_response)
  

  注意到调用该方法会执行wsgi_app(environ, start_response)方法，之所以这样设计是为了在应用正式处理请求之前，可以加载一些“中间件”，以此改变 Flask 应用的相关特性。

3. 把上下文压入栈

4. 请求分发

   response = self.full_dispatch_request()
   

   Flask 将调用full_dispatch_request函数进行请求的分发，之所以不用给参数，是因为我们可以通过request对象获得这次请求的信息。

   1. 执行请求钩子 before_first_request 的相关操作

   2. 执行请求钩子 before_request 的相关操作

   3. 路由匹配add_url_rule

   4. 对于 URL 模式的处理，Flask 应用使用werkzeug库中的Map类和Rule类，每一个 URL 模式对应一个Rule实例，这些Rule实例最终会作为参数传递给Map类构造包含所有 URL 模式的一个“地图”。这个地图可以用来匹配请求中的 URL 信息，关于Map类和Rule类的相关知识可以参考： Werkzeug 库——routing 模块。

   5. 进入 view_functions 执行 view 函数

        def wsgi_app(environ, start_response):
            with self.request_context(environ):
                rv = self.preprocess_request()
                if rv is None:
                    rv = self.dispatch_request()
                response = self.make_response(rv)
                response = self.process_response(response)
            return response(environ, start_response)
      

   6. 在请求正式被处理之前的一些操作，调用preprocess_request()方法，例如打开一个数据库连接等操作；

   7. 正式处理请求。这个过程调用dispatch_request()方法，这个方法会根据 URL 匹配的情况调用相关的视图函数；

   8. 将从视图函数返回的值转变为一个Response对象；

   9. 在响应被发送到WSGI服务器之前，调用process_response(response)做一些后续处理过程；

   10. 调用response(environ, start_response)方法将响应发送回WSGI服务器。关于此方法的使用，可以参考：Werkzeug 库——wrappers 模块；

   11. 退出上下文环境时，LocalStack会清理当前线程/协程产生的数据（请求上下文对象）。

   12. 执行请求钩子 after_request 的相关操作

   13. 执行请求钩子 teardown_request 的相关操作

5. 把上下文弹出栈

   这次 HTTP 的响应已经生成了，就不需要两个上下文对象了。分别将两个上下文对象出栈，为下一次的 HTTP 请求做出准备。

6. 返回响应结果

   调用 Response 对象，向 WSGI Server 返回其结果作为 HTTP 正文。Response 对象是一个可调用对象，当调用发生时，将首先执行 WSGI 服务器传入的 start_response()函数，发送状态码和 HTTP 报文头。

ref:

• Flask 中的请求上下文和应用上下文 - 知乎 (opens new window)
• Flask 进阶(一)——请求上下文和应用上下文完全解答(上)_sodawaterer 的博客-CSDN 博客_flask 请求上下文和应用上下文 (opens new window)
• Flask 如何处理一个请求 | EthanYan's Blog (opens new window)
• 一个 Flask 应用运行过程剖析 - 掘金 (opens new window)

*NIX

unix 进程间通信方式(IPC)

1. 管道（Pipe）：管道可用于具有亲缘关系进程间的通信，允许一个进程和另一个与它有共同祖先的进程之间进行通信。
2. 命名管道（named pipe）：命名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。命名管道在文件系统中有对应的文件名。命名管道通过命令 mkfifo 或系统调用 mkfifo 来创建。
3. 信号（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux 除了支持 Unix 早期信号语义函数 sigal 外，还支持语义符合 Posix.1 标准的信号函数 sigaction（实际上，该函数是基于 BSD 的，BSD 为了实现可靠信号机制，又能够统一对外接口，用 sigaction 函数重新实现了 signal 函数）。
4. 消息（Message）队列：消息队列是消息的链接表，包括 Posix 消息队列 system V 消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺
5. 共享内存：使得多个进程可以访问同一块内存空间，是最快的可用 IPC 形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。
6. 内存映射（mapped memory）：内存映射允许任何多个进程间通信，每一个使用该机制的进程通过把一个共享的文件映射到自己的进程地址空间来实现它。
7. 信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。
8. 套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由 Unix 系统的 BSD 分支开发出来的，但现在一般可以移植到其它类 Unix 系统上：Linux 和 System V 的变种都支持套接字。

• 代码实现 chaseSpace/IPC-Inter-Process-Communication: Code implemention for Inter-Process Communication (opens new window)

数据结构

红黑树

红黑树与 AVL 的比较：

AVL 是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；

红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；

所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择 AVL，如果搜索，插入删除次数几乎差不多，应该选择 RB。

红黑树详解: https://xieguanglei.github.io/blog/post/red-black-tree.html (opens new window)

教你透彻了解红黑树: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md (opens new window)

编程题

台阶问题/斐波那契

一只青蛙一次可以跳上 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 = 1,0
    for _ in range(n):
        a, b = b, a + b
    return b

变态台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

fib = lambda n: n if n < 2 else 2 * fib(n - 1)

矩形覆盖

我们可以用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)

杨氏矩阵查找

在一个 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 False

去除列表中的重复元素

用集合

list(set(list_x))

用字典

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]
print(l2)

sorted 排序并且用列表推导式.

l = ['b','c','d','b','c','a','a'] [single.append(i) for i in sorted(l) if i not in single] print single

链表成对调换

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 head

创建字典的方法

直接创建

dict = {'name':'earth', 'port':'80'}

工厂方法

items=[('name','earth'),('port','80')]
dict2=dict(items)
dict1=dict((['name','earth'],['port','80']))

fromkeys()方法

dict1={}.fromkeys(('x','y'),-1)
dict={'x':-1,'y':-1}
dict2={}.fromkeys(('x','y'))
dict2={'x':None, 'y':None}

合并两个有序列表

知乎远程面试要求编程

尾递归

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 tmp

pop 弹出

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)

交叉链表求交点

其实思想可以按照从尾开始比较两个链表，如果相交，则从尾开始必然一致，只要从尾开始比较，直至不一致的地方即为交叉点，如图所示

# 使用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/ (opens new window)

二分查找

#coding:utf-8
def binary_search(list,item):
    low = 0
    high = len(list)-1
    while low<=high:
        mid = (low+high)/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/76411718 (opens new window)

快排

#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 描述 (opens new window)

找零问题

#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 (opens new window)

方法: http://www.cnblogs.com/ChenxofHit/archive/2011/03/18/1988431.html (opens new window)

广度遍历和深度遍历二叉树

给定一个数组，构建二叉树，并且按层次打印这个二叉树

二叉树节点

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)))

层次遍历

def lookup(root):
    row = [root]
    while row:
        print(row)
        row = [kid for item in row for kid in (item.left, item.right) if kid]

深度遍历

def deep(root):
    if not root:
        return
    print root.data
    deep(root.left)
    deep(root.right)

if __name__ == '__main__':
    lookup(tree)
    deep(tree)

前中后序遍历

深度遍历改变顺序就 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 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)

求最大树深

def maxDepth(root):
        if not root:
            return 0
        return max(maxDepth(root.left), maxDepth(root.right)) + 1

求两棵树是否相同

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 False

前序中序求后序

推荐: http://blog.csdn.net/hinyunsin/article/details/6315502 (opens new window)

def 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.data

单链表逆置

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 (opens new window)

方法: http://www.xuebuyuan.com/2066385.html?mobile=1 (opens new window)

两个字符串是否是变位词

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'))

动态规划问题

可参考：动态规划(DP)的整理-Python 描述 (opens new window)

---

TODO

需要整理的：

• python_interview_question (opens new window)
• 315 道 Python 面试题，欢迎挑战 (opens new window)

来源

• Interview Python (opens new window)