Tornado Auto Etag 机制

为了研究缓存看了 tornado web.py 里的 finish 函数
代码如下

    def finish(self, chunk: Union[str, bytes, dict] = None) -> "Future[None]":
        """Finishes this response, ending the HTTP request.

        Passing a ``chunk`` to ``finish()`` is equivalent to passing that
        chunk to ``write()`` and then calling ``finish()`` with no arguments.

        Returns a `.Future` which may optionally be awaited to track the sending
        of the response to the client. This `.Future` resolves when all the response
        data has been sent, and raises an error if the connection is closed before all
        data can be sent.

        .. versionchanged:: 5.1

           Now returns a `.Future` instead of ``None``.
        """
        if self._finished:
            raise RuntimeError("finish() called twice")

        if chunk is not None:
            self.write(chunk)

        # Automatically support ETags and add the Content-Length header if
        # we have not flushed any content yet.
        if not self._headers_written:
            if (
                self._status_code == 200
                and self.request.method in ("GET", "HEAD")
                and "Etag" not in self._headers
            ):
                self.set_etag_header()
                if self.check_etag_header():
                    self._write_buffer = []
                    self.set_status(304)
            if self._status_code in (204, 304) or (
                self._status_code >= 100 and self._status_code < 200
            ):
                assert not self._write_buffer, (
                    "Cannot send body with %s" % self._status_code
                )
                self._clear_headers_for_304()
            elif "Content-Length" not in self._headers:
                content_length = sum(len(part) for part in self._write_buffer)
                self.set_header("Content-Length", content_length)

        assert self.request.connection is not None
        # Now that the request is finished, clear the callback we
        # set on the HTTPConnection (which would otherwise prevent the
        # garbage collection of the RequestHandler when there
        # are keepalive connections)
        self.request.connection.set_close_callback(None)  # type: ignore

        future = self.flush(include_footers=True)
        self.request.connection.finish()
        self._log()
        self._finished = True
        self.on_finish()
        self._break_cycles()
        return future

从代码中可以看出, 满足下面条件的请求:

  • self._headers_written 为不为True
  • http status 为 200GETHEAD 请求
  • 同时没有 Etagresponse header 的情况下

tornado 会自动计算返回结果的 sha1, 并设置 Etag 若客户端支持 Etag 机制, 正确返回 If-None-Match, 就能节约一波流量, 美滋滋.

2019/4/24 posted in  Tech

树-数据结构(Python)

树是计算机科学中常用的数据结构之一,常见的地方有,Java 的继承树等。
还有一些基于树的特殊数据结构,比如二叉树,B 树,等等。

本篇会讲述一些关于简单关于树的操作。

Read more   2018/4/8 posted in  算法

KMP 算法

在计算机科学中,Knuth-Morris-Pratt字符串查找算法(简称为KMP算法)可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符。

这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终由三人于1977年联合发表。

原理

将待匹配字符串命名为 m 源字符串命名为 S 。
本算法对待匹配字符串做处理之后,找到他的真前缀和真后缀。并通过真前缀与后缀重合的数量的值,这个值是在匹配状态中发生矢配时,位于原始字符串上 S 的指针移动的方向与距离。

简单的说就是匹配失败时。通过之前的真前缀和后缀表,直接移动在匹配字符串上的指针,达到减少无用匹配的效果。

优点

节约时间,相比于朴素的匹配方式,新的匹配算法只需要 O(m + n)的时间复杂度 和 额外 O(m)的空间,这个空间是用来保存真前缀和真后缀的结果的。

实现

KMP 匹配的关键在于初始化匹配字符串。

def partial_table(pattern:str):
    """
    当字符串长度为1的时候,不需要进行查表,直接循环匹配时间复杂度就是 O(n)
    """
    front = [pattern[:x+1] for x in range(len(pattern))]

    def cal_table_val(sub_pattern):
        return max([0]+[len(front[:i]) for i in range(len(sub_pattern)) if sub_pattern[-i:] in front[:i]])

    return [cal_table_val(pattern[:i + 1]) for i in range(len(pattern))]


def kmp(pattern, string, first=True):
    if not pattern or not string:
        return -1
    
    res = []
    # 匹配字符串长度为1 不需要建表
    if len(pattern) == 1:
        for i, k in enumerate(string):
            if k == pattern:
                if first:
                    return i
                res.append(i)
        return res

    pt = partial_table(pattern)
    i, j = 0, 0
    lp, ls = len(pattern), len(string)
    compile_flag = False
    while j - i < ls - lp:
        if string[j] == pattern[i]:
            i += 1
            j += 1          
            compile_flag = True
            if i == len(pattern):
                if first:
                    return j - i
                res.append(j - i)
                i = 0
        elif string[j] != pattern[i] and compile_flag:
            # 之前为匹配状态 需要移动匹配数组指针
            compile_flag = False
            i -= i - pt[i-1]
        elif string[j] != pattern[i] and not compile_flag:
            # 之前为不匹配状态 匹配指针归 0 
            i = 0
            j += 1

    return res

partial_table('ABCDABD') # [0, 0, 0, 0, 1, 2, 0]
kmp('ABCDABD','BBC ABCDAB ABCDABCDABDE') # 15


2018/4/8 posted in  算法

Pipenv + Autoenv 更友善的工作环境

Python 包管理一直都是一个问题,如今 3.6 推荐采用 Pipenv 出自 Requests 的大牛做所。配合上他写的 Autoenv 切换环境再也不是问题。

Read more   2018/3/14 posted in  Tech

485 Max Consecutive Ones 最长1的序列

题干

Link

Given a binary array, find the maximum number of consecutive 1s in this array.

Read more   2018/2/27 posted in  LeetCode

118 Pascal's Triangle 杨辉三角

题干

Link

Given numRows, generate the first numRows of Pascal's triangle.

Read more   2018/2/27 posted in  LeetCode

136 Single Number 只出现一次的数字

题干

Link

给定一个整数数组,除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注:
你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗?

Read more   2018/2/25 posted in  LeetCode

2017 技术总结

年初辞职分手
年中颓废学习
年末工作恋爱
也算是人生的大落大起

也颠覆了曾经的自己,重新拾起信念与目标。不扯这些虚的,就讲讲今年掌握的技术或者工具吧。

Read more   2017/12/31 posted in  Tech

爬虫代理池设计

缘起

鉴于最近在做爬虫工作,而我司代理池,并不带有很多比较高级的功能,使用体验可以说是比较差吧,同时也不支持配置,也不支持插件式扩展。更别说什么筛选、代理评分、等功能了。

所以就有自己来在做一个新的这样的想法,最近对 aiohttp 的使用可以说是比较熟练了。

Read more   2017/12/17 posted in  Tech

树莓派打造家庭数据中心(一)基本环境

首先你需要有一块可以 USB 接口的移动硬盘,或者大容量的 U 盘(不建议使用)。

你需要拥有这些东西:

  • 树莓派

  • 移动硬盘 USB 接口

  • 稳定的网

  • 树莓派镜像

Read more   2017/10/5 posted in  Tech