红黑树

一、红黑树是什么

红黑树是允许节点里包含最多两个 Node 的二叉树。

二、红黑树要解决什么问题

普通二叉树最大的问题在于,插入有序的序列会使二叉树会成为 N 的深度。
红黑树允许每个节点上最多挂两个 Node, 每当第三个 Node 插入的时候, 把中间值的 Node 往上冒泡。
如果在 root 上有三个 Node, 把中间的 Node 上冒做为新的 root。
由此可见,红黑树的深度是通过 root 往上冒增加的, 从而保证了每条路径到 root 的深度一致为 lg N (黑 Node 数量一致)。

Read More

Python 的赋值和作用域

一、Python 中的赋值

1.1 Python 中万物皆对象

1
print(type(1))  # <class 'int'>

1.2 Python 中赋值的意义
2.1 如果 = 号右边是对象, 则让 = 号左边的变量指向该对象, 成为对该对象的一个 引用
2.2 如果 = 号右边是变量, 则让 = 号左边的变量指向右边变量所指的对象, 成为那个对象的 引用
2.3 通过其它表达式而不是等号进行赋值的操作, 意义与上面相同

Read More

Tornado 实现 decorator 路由

我也实现了一个 Flask decorator 风格的 Tornado 路由,实现的方式极大地参考了 Flask 的过程(add_url_rule 和 Blueprint)。
Tornado 在新建 Application 的时候, 需要传入一个 handlers 参数, 原本这个 handlers 需要自己手动构建: 收集各个 RequestHandler,给他们分配路径,组成一个 handlers tuple。 这样维护起来非常麻烦。
我实现的功能是:

  1. 通过 decorator 给每个 RequestHander 即时分配 url pattern;
  2. 支持根据 API 版本和 Resource 类型自动给 url pattern 添加前缀;
  3. 可以通过 RequestHander 的类名反向查出 url。
    功能一点都不复杂, 实现起来也简单, 不到 100 行代码。下面是我的实现过程。

Read More

读 Python: functools.wraps 做了什么

Python 标准库 functools 里面的 wraps 装饰器经常用于写装饰器,之前只知道它可以用来保留被装饰函数的元数据,但具体实现的方式和究竟保留了哪些数据都不清楚。最近看 Flask 源码时读到一行代码 return self.record(update_wrapper(wrapper, func))。 稍微看了一下原来 @wraps(func) 其实就是调用了 update_wrapper 这个函数,于是索性看个明白。

Read More

Flask-Admin 快速实现用户权限限制

这个办法基于以下两个事实:

  1. Flask Admin 本身是一个 Flask 蓝图
  2. Flask 的 ModelView 类可以通过 can_delete = True/False 等来关闭/开启相应的操作
    所以实现的办法是,给 Flask-Admin 蓝图的 before_request_funcs 注册一个 check_user_permission 函数,在每次请求之前根据用户的权限来刷新 ModelView 的设置。
    而蓝图的 before_request 必须要在 app.register_blueprint 调用之前,根据 Flask-Admin 创建蓝图和注册蓝图的流程来看,复写 ModelView 的 create_blueprint 这个函数就可以了。

Read More

读Flask: 一次完整的Request和Response周期

Flask只是一个python web框架,框架和server之间的数据交流,都是基于PEP3333所规范的WSGI, server调用framwork的某个callable进行数据交流。 这个callable, 可以是定义了__call__方法的类,或者任何函数等。
而Flask应用的数据入口和出口(callable)就是Flask类实例的wsgi_app函数。

1
2
3
4
5
6
7
8
def wsgi_app(self, 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)

wsgi_app接受从server发过来的environ环境变量,并且根据这个变量创建一个request context,然后在这个context下进行数据处理,最后返回数据到server。

Read More