# Python后端技术栈(二)

## 每日分享

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

## 1.2算法与数据结构

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

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

```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（最近最少使用算法）

```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 底层结构

`DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR`

### 1.2.4 Python list/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.线性查找，二分查找

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):
"""
:rtype: ListNode
"""
pre = None
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队列

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 实现栈

```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):
"""
"""
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)

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

```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 操作获取最大的元素，最小堆获取最小元素。

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

```# 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```

Django相关知识点回顾

0 条评论

• ### 多线程如何获取结果

"Do what you feel in your heart to be right. You’ll be criticized anyway.—— Elea...

• ### Python后端技术栈(三)--设计模式

Somewhere, something incredible is waiting to be known.

• ### python技术面试题(十七)

People will forget what you said, people will forget what you did, but people wi...

• ### iOS 自定义分段控制器

最近做项目时遇到一些问题，就是项目里原有分段控制器的适用范围有些局限，虽然网上也有很多分段控制器的demo，但自己写的，可控性和项目适用性自己能很明白，所以我专...

• ### Python魔术方法-Magic Method

目录[-] 介绍 在Python中，所有以“__”双下划线包起来的方法，都统称为“Magic Method”,例如类的初始化方法 __init__ ,Pyt...

• ### Tiknter例子3

============================================

• ### Python魔法方法指南

什么是魔法方法呢？它们在面向对象的Python的处处皆是。它们是一些可以让你对类添加“魔法”的特殊方法。 它们经常是两个下划线包围来命名的（比如 __init_...

• ### python 长连接 mysql数据库

python链接mysql中没有长链接的概念，但我们可以利用mysql的ping机制，来实现长链接功能

• ### 高效处理流量加解密——Burpy

先来地址：Github: https://github.com/mr-m0nst3r/Burpy

• ### Seleninum&PhamtomJS爬取煎蛋网妹子图

mylog.py  日志模块，记录一些爬取过程中的信息,在大量爬取的时候，没有log帮助定位，很难找到错误点