Python后端技术栈(二)

小闫同学啊

发布于 2019-07-18 15:43:02

1.6K0

发布于 2019-07-18 15:43:02

文章被收录于专栏：小闫笔记小闫笔记

正文共：12497 字 6 图预计阅读时间：32分钟

每日分享

Darkness cannot drive out darkness; only light can do that. Hate cannot drive out hate; only love can do that.

黑暗无法驱除黑暗; 只有光可以做到这一点。仇恨无法驱走仇恨; 只有爱才能做到这一点。

小闫笔记：

不知你苦难，无法劝你向善。但你要知道，爱会让你过的更轻松。最后送给大家泰戈尔的《飞鸟集》中的一句『世界以痛吻我，我要回报以歌』。

1.2算法与数据结构

上篇文章传送门『我是个链接』

上篇文章对本系列整体情况作了说明。并且回顾了 Python 语言基础部分。美中不足的是上篇文章的结构有些混乱，从这篇文章开始，严格按照导航的编号进行编写。

本篇文章将要开始 Python 算法与数据结构相关知识的总结回顾。废话少说，开始吧....

1.2.1 Python 内置数据结构算法

常用内置数据结构和算法：

线性结构：

语言内置：list（列表）、tuple（元组）

内置库：array（数组，不常用）、collections.namedtuple

链式结构：

语言内置：无

内置库：collections.deque（双端队列）

字典结构：

语言内置：dict（字典）

内置库：collections.Counter（计数器）、OrderedDict（有序字典）

集合结构：

语言内置：set（集合）、frozenset（不可变集合）

内置库：无

排序算法：

语言内置：sorted

内置库：无

二分算法：

语言内置：无

内置库：bisect模块

堆算法：

语言内置：无

内置库：heapq模块

缓存算法：

语言内置：无

内置库： functools.lru_cache(Least Recent Used, python3)

1.2.2 collections 模块

collections 模块提供了一些内置数据结构的扩展

name	description
namedtuple()	factory function for creating tuple subclasses with named fields
deque	list-like container with fast appends and pops on either end
Counter	dict subclass for counting hashable objects
OrderedDict	dict subclass that remembers the order entries were added
defaultdict	dict subclass that calls a factory function to supply missing values

namedtuple

作用：让 tuple 属性可读。

示例：

In [1]: import collections

In [2]: Point = collections.namedtuple('Ponint', 'x, y')

In [3]: p = Point(1, 2)

In [4]: p.x
Out[4]: 1

In [5]: p.y
Out[5]: 2

In [6]: p[0]
Out[6]: 1

In [7]: p[1]
Out[7]: 2

In [8]: p.x == p[0]
Out[8]: True

deque

deque 可以方便的实现 queue 以及 stack（堆栈）

示例：

In [9]: de = collections.deque()

In [10]: de.append(1)

In [11]: de.appendleft(0)

In [12]: de
Out[12]: deque([0, 1])

In [13]: de.pop()
Out[13]: 1

In [14]: de.popleft()
Out[14]: 0

Counter

需要计数器的地方可以使用 Counter

示例：

In [15]: c = collections.Counter()

In [16]: c = collections.Counter('abcab')

In [17]: c
Out[17]: Counter({'a': 2, 'b': 2, 'c': 1})

In [18]: c['a']
Out[18]: 2

In [19]: c.most_common()
Out[19]: [('a', 2), ('b', 2), ('c', 1)]

OrderedDict

OrderedDict 的 key 顺序是第一次插入的顺序。使用它实现 LRUCache（最近最少使用算法）

它是如何实现有序的呢？大家感兴趣可以通过源码了解一下。其实它底层实现了一个循环双端链表保存 key 记录循序。

示例：

In [20]: od = collections.OrderedDict()

In [21]: od['c'] = 'c'

In [22]: od['a'] = 'a'

In [23]: od['b'] = 'b'

In [25]: list(od.keys())
Out[25]: ['c', 'a', 'b']

defaultdict

带有默认值的字典

示例：

In [26]: dd = collections.defaultdict(int)

In [27]: dd['a']
Out[27]: 0

In [28]: dd['b']
Out[28]: 0

In [29]: dd['b'] += 1

In [30]: dd
Out[30]: defaultdict(int, {'a': 0, 'b': 1})

1.2.3 Python dict 底层结构

为了支持快速查找使用了哈希表作为底层结构。哈希表平均查找时间复杂度可以达到 O(1)，以至于我们根据 key 能非常快的查找到 value 值。同时 CPython 解释器使用二次探查解决了哈希冲突的问题。

哈希冲突和扩容需要格外注意。哈希冲突的解决办法有链接法和探查法，探查法又分为线性探查和二次探查。

简单的解释一下哈希冲突。我们首先在元素的关键字 K 和元素的位置 P 之间建立一个对应关系 f，使得 P=f(K)，其中 f 就是哈希函数。创建哈希表的时候，将关键字 K 的元素直接存入 f(K) 的单元，查找的时候也简单，就是利用哈希函数计算出该元素的存储位置 P=f(K) 。当关键字集合很大的时候，有可能出现一种现象，就是关键字不同的元素映射到哈希表的相同地址上，这就是哈希冲突。

也许这么说你不理解，那么就用人话来说一遍：不同的 value 通过哈希计算，得出的 key 一样，也就相当于俩人的身份证号重了。

简单的说一下线性探查法和二次探查法。在发生哈希冲突的时候，我们自动往下一个位置放，也就是加1，加2......直到后面的位置由空，然后插入。二次探查法就是平方操作，加1^2，2^2......直到后面的位置为空，进行插入。探查法也就是利用一个探测算法，当某个槽位已经被占的时候，继续查找下一个可以使用的槽位。而链表法则是将相同的 hash 值的对象组织成一个链表（同义词链）放在 hash 值对应的槽位。

同时为了减少冲突的概率，当哈希表的数组长度到一个临界值的时候就会触发扩容，把所有的元素 rehash 再放入到扩容后的容器中。临界值由加载因子和当前容器的容量大小来确定：

DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR

默认情况下是 16 x 0.75 = 12 时触发。也许你会问为什么加载因子是0.75。这个不是平白无故的定的，而是有依据。使用随机哈希码，节点出现的频率在 hash 桶中遵循泊松分布，根据桶中元素个数和频率，我们可以知道当桶中元素到达8个时，概率非常小，也就是用 0.75 作为加载因子，每个碰撞位置的链表长度超过8个是几乎不可能的。

1.2.4 Python list/tuple 区别

它们都是线性结构，支持下标访问。但是 list 是可变对象， tuple 保存的引用是不可变的。

也许你会想 tuple 是不可变对象，但是有一种情况，tuple 保存的元素中有一个列表，那么列表可变，它也可变。利用代码进行说明：

In [31]: t = ([1], 2, 3)

In [32]: t[0]
Out[32]: [1]

In [33]: t[0].append(1)

In [34]: t
Out[34]: ([1, 1], 2, 3)

保存的引用不可变指的是你没法替换掉这个对象，但是如果对象本身是可变对象，那么是可以修改这个引用指向的可变对象的。

list 不能作为字典的 key ，但是 tuple 是可以的（可变的对象是不可 hash 的）

1.2.5什么是 LRUCache

Least-Recently-Used 替换掉最近最少使用的对象。

1.缓存剔除策略，当缓存空间不够用的时候，需要一种方式剔除 key。

2.常见的有 LRU、LFU（剔除最近使用次数最少的对象）。一个是从使用的次数，一个是从使用时间两个角度来考虑。

3.LRU 通过使用一个循环双端队列不断把最新访问的 key 放在表头实现。

原理：首先我们需要有一个链表，每次访问其中一个对象的时候，我们将其移动到链表的最前边，这样我们不断的将最近使用的放到链表的最前边，不常使用的留到链表的最尾端，每次我们只需要剔除尾部的对象即可。

1.2.6如何实现 LRUCache

字典用来缓存，循环双端链表用来记录访问顺序。

1.利用 Python 内置的 dict + collections.OrderedDict 实现。

2.dict 用来当做 k/v 键值对的缓存。

3.OrderedDict 用来实现更新最近访问的 key

实现：

from collections import OrderedDict


class LRUCache(object):
    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
            # 判断当前容量是否已经满了
            if len(self.od) > self.capacity:
                self.od.popitem(last=False)

1.2.7 Python 常用算法

排序 + 查找，重中之重。

1.排序算法：冒泡排序、快速排序、归并排序、堆排序。

2.线性查找，二分查找

能独立实现代码（手写），能够分析时间空间复杂度。

1.2.8常用排序算法的时空复杂度

排序算法	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n^2)	O(n^2)	稳定	O(1)
选择排序	O(n^2)	O(n^2)	不稳定	O(1)
插入排序	O(n^2)	O(n^2)	稳定	O(1)
快速排序	O(n^2)	O(n*log2n)	不稳定	O(log2n)~O(n)
堆排序	O(n*log2n)	O(n*log2n)	不稳定	O(1)

1.2.9 Python web后端数据结构总结

1.常见的数据结构链表、队列、栈、二叉树、堆

2.使用内置结构实现高级数据结构，比如内置的 list/deque 实现栈

3.可以多看一下 LeetCode 或者《剑指 offer》上的经典题

1.2.10链表

链表有单链表、双链表、循环双端链表。大家要掌握的是如下：

1.如何使用 Python 来表示链表结构

2.实现链表常见操作，比如插入节点，反转链表，合并多个链表

3.LeetCode 练习常见链表题目

单链表倒序：

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur:
            nextnode = cur.next
            cur.next = pre
            pre = cur
            cur = nextnode
        return pre

删除链表节点：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        nextnode = node.next
        after_next_node = node.next.next
        node.val = nextnode.val
        node.next = after_next_node

因为题目中只给我们传了一个节点，没有前面的节点。为了实现删除的操作。我们可以将传入的节点用下一个节点的值替换掉，然后将指针指向下一个的下一个节点。相当于删除此节点。

合并两个有序的链表：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        root = ListNode(None)
        cur = root
        while l1 and l2:
            if l1.val < l2.val:
                node = ListNode(l1.val)
                l1 = l1.next
            else:
                node = ListNode(l2.val)
                l2 = l2.next
            cur.next = node
            cur = node
        # l1 或者 l2 可能还有剩余元素
        cur.next = l1 or l2
        return root.next

1.2.11队列

队列（queue）是先进先出结构

1.使用 Python 实现队列

2.实现队列的 apend 和 pop 操作，如何做到先进先出

3.使用 Python 的 list 或者 collections.deque 实现队列

双端队列可以非常方便的从队列两端进行追加值或者弹出值。

示例：

# 使用deque实现队列
from collections import deque


class Queue(object):
    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

1.2.12栈（stack）

栈是后进先出的结构

1.如何使用 Python 实现栈？

2.实现栈的 push 和 pop 操作，如何做到后进先出。

3.同样可以用 Python list 或者 collections.deque 实现栈

借助内置的数据结构非常容易实现一个栈（stack），后入先出：

from collections import deque
class Stack(object):
    def __init__(self):
        self.deque = deque()

    def push(self, value):
        self.deque.append(value)

    def pop(self):
        return self.deque.pop()

如何用两个栈实现队列

LeetCode真题实现：

from collections import deque

# python 里面没有栈，我们先来手动实现一个
class Stack(object):
    def __init__(self):
        self.items = deque()

    def push(self, val):
        return self.items.append(val)

    def pop(self):
        return self.items.pop()

    def top(self):
        """返回栈顶值"""
        return self.items[-1]

    def empty(self):
        return len(self.items) == 0


class MyQueue(object):
    def __init__(self):
        """
        Initialize your data structure here
        """
        self.s1 = Stack()
        self.s2 = Stack()

    def push(self, x):
        """
        Push element x to the back of queue
        :type x: int
        :rtype: void
        """
        self.s1.push(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if not self.s2.empty():
            return self.s2.pop()
        while not self.s1.empty():
            val = self.s1.pop()
            self.s2.push(val)
        return self.s2.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if not self.s2.empty():
            return self.s2.top()
        while not self.s1.empty():
            val = self.s1.pop()
            self.s2.push(val)
        return self.s2.top()

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.s1.empty() and self.s2.empty()

另一种：

class QueueWithTwoStacks(object):
    def __init__(self):
        self._stack1 = []
        self._stack2 = []

    def appendTail(self,x):
        self._stack1.append(x)

    def deleteHead(self):
         if self._stack2:
             return self._stack2.pop()
         else:
             if self._stack1:
                while self._stack1:
                    self._stack2.append(self._stack1.pop())
                return self._stack2.pop()
             else:
                 return None

两个队列实现一个栈

class StackWithTwoQueues(object):
    def __init__(self):
        self._stack1 = []
        self._stack2 = []

    def push(self,x):
        if len(self._stack1) == 0:
            self._stack1.append(x)
        elif len(self._stack2) == 0:
            self._stack2.append(x)
        if len(self._stack2) == 1 and len(self._stack1) >= 1:
            while self._stack1:
                self._stack2.append(self._stack1.pop(0))
        elif len(self._stack1) == 1 and len(self._stack2) > 1:
            while self._stack2:
                self._stack1.append(self._stack2.pop(0))

    def pop(self):
        if self._stack1:
            return self._stack1.pop(0)
        elif self._stack2:
            return self._stack2.pop(0)
        else:
            return None

实现获取最小值的栈 MinStack

class MinStack(object):
    def __init__(self):
        # do some intialize if necessary
        self.s = []
        self.m = []

    def push(self, number):
        # write yout code here
        self.s.append(number)
        if len(self.m) == 0:
            self.m.append(number)
        else:
            self.m.append(min(number, self.m[-1]))

    def pop(self):
        # pop and return the top item in stack
        self.m.pop()
        return self.s.pop()

    def min(self):
        # return the minimum number in stack
        return self.m[-1]

1.2.13字典和集合

Python dict/set 底层都是哈希表

1.哈希表的实现原理：底层其实就是一个数组

2.根据哈希函数快速定位一个元素，平均查找 O(1) ，非常快

3.不断加入元素会引起哈希表重新开辟空间，拷贝之前元素到新数组。

1.2.14哈希表如何解决冲突

前面我们简单的提了一下解决冲突的方法，此处我们详细解释一下。

1.链接法和开放寻址法：元素 key 冲突之后使用一个链表填充相同 key 的元素（既然你们的 key 相同，那么你们统一组成一个链表，然后把这个链表放在 key 的元素位置）。

2.开放寻址法：开放寻址法是冲突之后根据一种方式（二次探查）寻找下一个可用的槽。

CPython 其实使用的就是二次探查

1.2.15二叉树

先序、中序、后序遍历

1.先（根）序：先处理根，之后是左子树，然后是右子树。

2.中（根）序：先处理左子树，然后是根，然后是右子树。

3.后（根）序：先处理左子树，然后是右子树，然后是根。

先序遍历：

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

class BinTree(object):
    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 inorder(self, root):
      """递归实现中序遍历"""
      if root == None:
          return
      self.inorder(root.left)
      print(root.data)
      self.inorder(root.right)

后序遍历：

def postorder(self, root):
    if root == None:
        return
    self.postorder(root.left)
    self.postorder(root.right)
    print(root.data)

二叉树的操作很多都可以用递归的方式解决

二叉树的镜像

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root:
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root

如何层序遍历二叉树（广度优先搜索）

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            # 注意： root 可能为空
            return []
        res = []
        cur_nodes = [root]
        next_nodes = []
        res.append([i.val for i in cur_nodes])
        while cur_nodes or next_nodes:
            for node in cur_nodes:
                if node.left:
                    next_nodes.append(node.left)
                if node.right:
                    next_nodes.append(node.right)
            if next_nodes:
                res.append(
                    [i.val for i in next_nodes]
                )
            cur_nodes = next_nodes
            next_nodes = []
        return res

扩展

输出左右视角的二叉树结果。也就是从左边看二叉树只能看到最左边的一列。

可以通过层序遍历，然后将每一层的最左侧或者最右侧的元素进行输出即可。

1.2.16堆

堆其实就是完全二叉树，有最大堆和最小堆

1.最大堆：对于每个非叶子节点 V，V 的值都比它的两个孩子大。

2.最大堆支持每次 pop 操作获取最大的元素，最小堆获取最小元素。

常见问题：用堆来完成 topk 问题，从海量数字中寻找最大的 k 个。示例代码如下：

import heapq


class TopK(object):
    """获取大量元素 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:
                # 返回并且 pop 堆顶最小值，推入新的 val 值并调整堆。
                heapq.heapreplace(self.minheap, val)
        else:
            # 前面 k 个元素直接放入最小堆
            heapq.heapreplace(self.minheap, val)

    def get_topk(self):
        for val in self.iterable:
            self.push(val)
        return self.minheap

LeetCode：merge-k-sorted-list

合并 k 个有序链表：使用堆来实现

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

from heapq import heapify, heappop
class Solution:
    def mergeKList(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # 读取所有节点值
        h = []
        for node in lists:
            while node:
                h.append(node.val)
                node = node.next
        # 构建一个最小堆
        if not h:
            return None
        heapify(h) # 转换成最小堆

        # 构造链表
        root = ListNode(heappop(h))
        curnode = root
        while h:
            nextnode = ListNode(heappop(h))
            curnode.next = nextnode
            curnode = nextnode
        return root

1.2.17白板编程

传说中的手写算法题，白纸或者白板上手写代码

1.如果参加过大学的 ACM/蓝桥杯之类算法竞赛的同学来说会好一点。

2.可以通过刷题来提高能力。LeetCode，《剑指offer》，看 github 等等。

3.对于算法要经常练习保持手感。

很多人其实会问，工作中又用不到，为什么经常见一些公司面试考算法？这个原因就是多方面的了，比如一些公司为了筛选一些编程能力强的同学。而且近几年互联网的发展，更多的是对代码的优化，而非是写业务逻辑了。针对一些刚毕业的大学生来说，没有工程经验，只能通过算法来辨别能力。近来互联网行业竞争日益激烈，公司裁员等等，那么如何在大家水平差不多的情况下挑选出一些人才呢？那就是考算法了。所以，一定要重视这一块的内容。

1.2.18字符串

我们需要了解常用的字符串操作：

1.Python 内置了很多字符串操作，比如 split（分割）、upper（大写）、replace（替换）等等。

《剑指offer》上的原题：

反转一个字符串:

# 题目：输入一个字符串数组，输出一个反转的字符串数组，不能占用额外的空间
# 方法一：
list.reverse()
# 方法二：可以使用两个指针，一个从前往后移，一个从后往前移，然后交换字符位置，当两个指针重合的时候，退出。
class Solution:
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: void Do not return anything, modify s in-place instead.
        """
        beg = 0
        end = len(s) - 1
        while beg < end:
            s[beg], s[end] = s[end], s[beg]
            beg += 1
            end -= 1

判断一个数字是否是回文数：

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        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