[Python知识库]python_audition面试笔记

Python_audition笔记

• with用法

with的用法，上下文管理器。一般打开文件用，打开文件在进行读写时可能会出现异常状况，如果不用with自己要
try,except,finally。with实现了finally中的f.close

• 函数中*args,**kwargs含义：

用来处理可变参数
*args被打包成tuple
**kwargs被打包成dict

def print_all(a,*args,**kwargs):
    print(a)
    if args:
        print(args)
    if kwargs:
        print(kwargs)
print_all("hello", "world", "amber", name="amberli")

控制台输出结果：
    hello
    ('world', 'amber')
    {'name': 'amberli'}

print_all(*["a",'b','c'],**{"name":"amberli","age":30})
控制台输出结果：
    a
    ('b', 'c')
    {'name': 'amberli', 'age': 30}

• Python可变、不可变对象

不可变对象：bool/int/float/tuple/str/frozenset
可变对象：list/set/dict

frozenset()返回一个冻结的集合，冻结后集合不能再添加或删除任何元素
set(可变集合)与frozenset(不可变集合)的区别：
    set无序排序且不重复，是可变的，有add()，remove()等方法，既然是可变的，所以不存在哈希值
    frozenset是冻结的集合，是不可变的，存在哈希值，好处是可以作为字典的key，也可以作为其他集合的元素
    缺点是一旦创建便不能更改，没有add,remove方法
set()和frozenset()工厂函数分别用来生成可变和不可变的集合，如果不提供任何参数默认会生成空集合。
如果提供一个参数，则参数必须是可迭代的，即，一个序列，或迭代器，或支持迭代的一个对象，例如一个列表或一个字典。

• enumerate()函数

enumerate()函数用于将一个可遍历的数据对象（如列表、元祖或字符串）组合为一个索引序列，同时列出数据和数据下标，
一般用在for循环当中。
>>> e = enumerate("amberli")
>>> for i, v in e:
...     print(i,v)
...
0 a
1 m
2 b
3 e
4 r
5 l
6 i
>>>

• 如何自定义异常

如何自定义自己的异常？为什么需要定义自己的异常？
    * 继承Exception实现自定义异常
    * 给异常加上一些附加信息
    * 处理一些业务相关的特定异常（raise MyException)

class MyException(Exception):
    pass
    
try:
    ...
    raise MyException("my exception")
except MyException as e:
    print(e)

• python性能分析与优化，GIL全局解释器锁

GIL: Global Interpreter Lock
    Cpython解释器的内存管理并不是线程安全的
    保护多线程情况下对python对象的访问
    Cpython使用简单的锁机制避免多个线程同时执行字节码
GIL的影响：
    限制了程序的多核执行
        同一个时间只能有一个线程执行字节码
        CPU密集程序难以利用多核优势
        IO期间会释放GIL，对IO密集程序影响不大
如何避免GIL影响：
    区分CPU和IO密集程序
        CPU密集可以使用多进程+进程池
        IO密集使用多线程/协程
        cpython扩展
为何有了GIL还要关注线程安全
    python中什么操作才是原子的？一步到位执行完
        一个操作如果是一个字节码指令可以完成就是原子的
        原子的是可以保证线程安全的
        使用dis操作来分析字节码
以加锁的方式确保线程安全：
不加锁后：
import threading

n = [0]
def foo():
    n[0] = n[0] + 1
    n[0] = n[0] + 1
threads = []
for i in range(5000):
    t = threading.Thread(target=foo)
    threads.append(t)
for t in threads:
    t.start()
print(n)    # 不一定为10000

加锁：
import threading

lock = threading.Lock() # 以加锁的方式确保线程安全
n = [0]
def foo():
    with lock:
        n[0] = n[0] + 1
        n[0] = n[0] + 1
threads = []
for i in range(5000):
    t = threading.Thread(target=foo)
    threads.append(t)
for t in threads:
    t.start()
print(n)    # 10000

如何剖析程序性能
    使用各种profile工具（内置或第三方）
        二八定律，大部分时间耗时在少量代码上
        内置的profile/cprofilee等工具
        使用pyflame(uber开源）的火焰图工具
服务端性能优化措施
    web应用一般语言不会成为瓶颈
        数据结构与算法优化
        数据库层：索引优化，慢查询消除，批量操作减少IO，NoSQL
        网络IO：批量操作，pipeline操作，减少IO
        缓存：使用内存数据库 redis/memcached
        异步：asyncio, celery
        并发：gevent/多线程
        

• python生成器与协程

Generator:生成器
   生成器就是可以生成值的函数
   当一个函数里有了yield关键字就成了生成器
   生成器可以挂起执行并且保持当前的执行状态
def simple_gen():
    yield "hello"
    yield "world"

gen = simple_gen()
print(type(gen))    # <class 'generator'>
print(next(gen))    # hello
print(next(gen))    # world

基于生成器的协程
    python3之前没有原生协程，只有基于生成器的协程
    pep 342(Coroutines via Enhanced Generators)增强生成器功能
    生成器可以通过yield暂停执行和产出数据
    同时支持send()向生成器发送数据和throw()向生成器抛异常
    python3.5引入async/await支持原生协程（native coroutine)

• python常用内置算法和数据结构

sorted
dict/list/set/tuple...

• python常用内置数据结构和算法

• python dict底层结构

dict底层使用的是哈希表
    为了支持快速查找使用了哈希表作为底层结构
    哈希表平均查找时间复杂度0(1)
    Cpython解释器使用二次探查解决哈希冲突问题

• python list/tuple区别

list vs tuple
都是线性结构，支持下标访问
list是可变对象，tuple保存的引用不可变
list没法作为字典的key,tuple可以（可变对象不可哈希）

• 什么是LRUCache

Least-Recently-Used替换掉最近最少使用的对象
    缓存剔除策略，当缓存空间不够用的时候需要一种方式剔除key
    常见的有LRU、LFU等
    LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现

• 如何实现LRUCache

字典用来缓存，循环双端链表用来记录访问顺序
    利用python内置的dict+collections.OrderedDict实现
    dict用来当做k/v键值对的缓存
    OrderedDict用来实现更新最近访问的key
    
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity=128):
        self.od = OrderedDict()
        self.capacity = capacity

    def get(self,key):  # 每次访问更新最新使用的key
        if key in self.od:
            val = self.od[key]
            self.od.move_to_end(key)
            return val
        else:
            return -1
    def put(self, key,value):   # 更新k/v
        if key in self.od:
            del self.od[key]
            self.od[key] = value    # 更新key到表头
        else:
            self.od[key] = value    # insert
            if len(self.od) > value.capacity:   # 判断容量是否满了
                self.od.popitem(last=False)

• 算法（排序+查找）

排序算法：冒泡排序、快速排序、归并排序、堆排序
线性查找。二分查找等
能独立实现代码（手写），能够分析时间空间复杂度

• python数据结构

常见的数据机构链表、队列、栈、二叉树、堆
使用内置结构实现高级数据结构，比如内置的list/deque实现栈
Leetcode或者<<剑指offer>>上的常见题
链表有单链表、双链表、循环双端链表
如何使用python来表示链表结构
实现链表常见操作，比如插入节点，反转链表，合并多个链表等

• 数据结构之队列，队列是先进先出结构

如何使用python实现队列？
实现队列的append和pop操作，如何做到先进先出
使用python的list或者collections.deque实现队列

from collections import deque
class Queue:
    def __init__(self):
        self.items = deque()
    def append(self, val):
        return self.items.append(val)
    def pop(self):
        return self.items.popleft()
    def empty(self):
        return len(self.items) == 0
q = Queue()
q.append(1)
q.append(2)
q.append(3)
print(q.pop())  # 1
print(q.pop())  # 2
print(q.pop())  # 3
print(q.empty())

• 数据结构之栈，栈是后进先出

如何使用python实现栈？
实现栈的push和pop操作，如何做到后进先出
同样可以用python list或者collections.deque实现栈

from collections import deque

class Stack:
    def __init__(self):
        self.deque = deque()
    def push(self,val):
        self.deque.append(val)
    def pop(self):
        return self.deque.pop()
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

• 数据结构之二叉树

先序、中序、后序遍历
先（根）序：先处理根，之后是左子树，然后是右子数
中（根）序：先处理左子树，然后是跟，然后是右子树
后（根）序：先处理左子树，然后是右子树，最后是根

class BinTreeNode:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data,left,right

class BinTree:
    def __init__(self, root=None):
        self.root = root
    def preorder_trav(self, subtree):
        # 先（根）序遍历
        if subtree is not None:
            print(subtree.data)     # 递归函数里先处理根
            self.preorder_trav(subtree.left)    # 递归处理左子树
            self.preorder_trav(subtree.right)   # 递归处理右子树


    def preorder_trav(self, subtree):
        # 中（根）序遍历
        if subtree is not None:
            self.preorder_trav(subtree.left)    # 递归处理左子树
            print(subtree.data)     # 递归函数里先处理根
            self.preorder_trav(subtree.right)   # 递归处理右子树
            
    def preorder_trav(self, subtree):
        # 后（根）序遍历
        if subtree is not None:
            self.preorder_trav(subtree.left)    # 递归处理左子树
            self.preorder_trav(subtree.right)   # 递归处理右子树
            print(subtree.data)     # 递归函数里先处理根

• 数据结构之堆

堆其实是完全二叉树，有最大堆和最小堆
    最大堆：对于每个非叶子节点V，V的值都比它的两个孩子大
    最大堆支持每次pop操作获取最大的元素，最小堆获取最小元素
    常见问题：用堆来完成topk问题，从海量的数据中寻找最大的K个
    
import heapq

class TopK:
    """
    获取最大元素 topk 个大元素，固定内存
    思路：
        1.先放入元素前K个建立一个最小堆
        2.迭代剩余元素
            如果当前元素小于堆顶元素，跳过该元素（肯定不是前K大）
            否则替换堆顶元素为当前元素，并重新调整堆
    """
    def __init__(self, iterable, k):
        self.minheap = []
        self.capacity = k   # 容量
        self.iterable = iterable

    def push(self, val):
        if len(self.minheap) >= self.capacity:
            min_val = self.minheap[0]
            if val < min_val:   # 当然可以直接 if val > min_val操作，这里只是显示指出跳过这个元素
                pass
            else:
                heapq.heapreplace(self.minheap,val) # 返回并且pop堆顶最小值，推入新的val值并调整堆
        else:
            heapq.heappush(self.minheap, val)
    def get_topk(self):
        for val in self.iterable:
            self.push(val)
        return self.minheap
        
import random
i = list(range(100))    # 这里可以是一个可迭代的元素，节省内存
random.shuffle(i)
print(i)
top10 = TopK(i,10)
print(top10.get_topk())

• 数据结构之字典与集合

python dict/set底层都是哈希表
    哈希表的实现原理，底层其实就是一个数组
    根据哈希函数快速定位一个元素，平均查找0(1),非常快
    不断加入元素会引起哈希表重新开辟空间，拷贝之前元素到新数组

• 哈希表如何解决冲突

链接法和开放寻址法
    元素key冲突之后使用一个链表填充相同key的元素
    开放寻址法是冲突之后根据一种方式（二次探查）寻找下一个可用的槽
    cpython使用的二次探查

• 查找结构进化史

线性查找：一个个查找；实现简单，太慢
二分查找：有序；简单；要求是有序的，插入特别慢
HASH：查询快；占用空间，不太适合存储大规模数据
二叉查找树：插入和查询很快（log(n))；无法存储大规模数据，复杂度退化
平衡树：解决bst退化的问题，树是平衡的；节点非常多的时候，依然树高很高
多路查找树：一个父亲多个孩子节点，节点过多数高不会特别深

• 回文数

class Solution:
    def isPalindrome(self,x):
        if x < 0:
            return False
        s = str(x)
        beg, end = 0, len(s) -1
        while beg < end:
            if s[beg] == s[end]:
                beg += 1
                end -= 1
            else:
                return False
        return True

print(Solution().isPalindrome(12521))

• 字符串反转

class Solution:
    def reverseString(self,s):
        beg = 0
        end = len(s) -1
        s = list(s)
        print(s)
        while beg < end:
            s[beg], s[end] = s[end], s[beg]
            beg += 1
            end -= 1
        return s
print(Solution().reverseString('hello2'))

• 什么是面向对象编程

Object Oriented Programming(OOP)
    把对象作为基本单元，把对象抽象成类（Class），包含成员和方法
    数据封装、继承、多态
    Python中使用类来实现。过程式编程（函数），OOP（类）

• 组合与继承

优先使用组合而非继承
    组合是使用其他的类实例作为自己的一个属性（Has-a关系）
    子类继承父类的属性和方法（Is a关系）
    优先使用组合保持代码简单

• 类的专有方法

__init__: 构造函数，在生成对象时调用，是一个实例方法，__init__什么都不返回，初始化实例时用__init__
__new__: 是一个静态方法，__new__方法会返回创建的实例，创建实例时用__new__
__del__：析构函数，释放对象时使用
__repr__：打印，转换
__setitem__：按照索引赋值
__getitem__：按照索引获取值
__len__: 获得长度
__cmp__: 比较运算
__call__: 函数调用
__add__: 加运算
__sub__:减运算
__mul__:乘运算
__truediv__: 除运算
__mod__: 求余运算
__pow__:乘方

• 函数式编程

python支持部分函数式编程特性
    把电脑的运算视作数学上的函数计算（lambda演算）
    高阶函数：map/reduce/filter
    无副作用，相同的参数调用始终产生同样的结果

• 闭包（closure)

绑定了外部作用域的变量函数
即使程序离开外部作用域，如果闭包仍然可见，绑定变量不会销毁
每次运行外部函数都会重新创建闭包

闭包：引用了外部自由变量的函数
自由变量：不在当前函数定义的变量
特性：自由变量会和闭包函数同时存在

from functools import wraps

def cache(func):    # 装饰器
    store = {}      # 外部变量

    @wraps(func)
    def _(n):       # 闭包函数
        if n in store:
            return store[n]
        else:
            res = func(n)
            store[n] = res
            return res
    return _

@cache
def f(n):   # 斐波那契
    if n <= 1:
        return 1
    return f(n-1) + f(n-2)

print(f(5))

• 进程和线程的区别

进程是对运行时程序的封装，是系统资源调度和分配的基本单位
线程是进程的子任务，cpu调度和分配的基本单位，实现进程内并发
一个进程可以包含多个线程，线程依赖进程存在，并共享进程内存

• 进程间通信的方式

Inter-Process Communication进程间传递信号或者数据
    共享内存（share memory)
    信号量（Semaphore)
    套接字（socket)：最常用的方式，一般web应用都是这种方式

• python中如何使用多线程

threading模块
    threading.Thread类用来创建线程
    start()方法启动线程
    可以用join()等待线程结束

• python中如何使用多进程

python有GIL，可以用多进程实现cpu密集程序
    multiprocessing多进程模块
    Multiprocessing.Process类实现多进程
    一般用在cpu密集程序里，避免GIL的影响
   
import multiprocessing

def fib(n):
    if n <= 1:
        return 1
    return fib(n-1) + fib(n-2)
if __name__ == '__main__':
    jobs = []
    for i in range(10,20):
        p = multiprocessing.Process(target=fib, args=(i,))
        jobs.append(p)
        p.start()
f = fib(5)
print(f)

• python的垃圾回收机制原理

python无需手动回收内存，它的回收是如何实现的呢？
    引用计数为主（缺点：循环引用无法解决）
    引入标记清除和分代回收解决引用计数的问题
    引用计数为主+标记清除和分代回收为辅