cpython3.7 dict 对象的内在原理

众所周知,python 中有一个应用得极其广泛内建对象——dict(字典)。cpython 解释器本身,以及大量的 python 程序,都依赖于 dict 对象。因此,dict 对象在 python 中设计得极其高效,其插入、删除、查询等操作的时间复杂度都是O(1)。

dict 对象可以这样使用:

1
2
3
4
5
6
7
8
>>> scores = {'Mike': 90, 'Jack': 100}
>>> scores['Ariana'] = 0
>>> scores['Jack']
100
>>> scores['Tim']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'Tim'

本文将从 cpython3.7 源码的角度出发,探讨 dict 对象的内部原理。主要将探讨以下几个内容:

  • dict 对象的结构、组成
  • dict 解决哈希冲突的方式
  • cpython 对 dict 的内部优化,如缓冲池、split table
  • 遍历 dict 保持插入顺序的原理

本文的剖析基于 https://github.com/python/cpython/blob/bb86bf4c4eaa30b1f5192dab9f389ce0bb61114d/Objects/dictobject.c 这份源码。

值得夸耀的 bottle 微框架源代码之剖析

在这片天空中张开双翼

自在地飞翔啊

bottle 是一个快速、简单、轻量的 web 框架,它以一个单文件的形式发布,并且不依赖 python 标准库以外的任何库。bottle 为使用者提供了诸多便利,如:

  • 支持将动态 url 的请求映射到函数调用。
  • 提供了一个简单的内置模板引擎,同时能够十分容易的替换为流行的 Mako、Jinja 等引擎。
  • 同时提供了如文件上传、cookie读取等的实用工具。
  • 并且内建了对许多常用兼容 python wsgi 规范的服务器的支持。

值得称道的是,bottle 主要文件只有不到 5000 行的代码。小巧、精简,却五脏俱全,被运用于诸多生成环境。

本文将简要剖析尚未发布的 bottle 0.12.14 版的最新 commit 版本。

深具传统的 bobo 微框架源代码之阅读

不做也行的事情就不做,非做不可的事情一切从简。

bobo 是一个诞生于上世纪的,直到近两年仍然在更新的 python web 微框架。可以说深具传统,从侧面上见证了这么多年来 python 在 web 开发领域的种种发展。据说,正是这个框架将 fluend python 的作者 Luciano Ramalho 带入了 python 编程的生涯。

翻译:HTTP 缓存

原文章

通过网络获取一些东西总是缓慢并且昂贵的。多数的响应需要在客户端和服务器之间往返多次。当它们可用并且浏览器能够处理它们的时候,就会发生延迟,还会访问者带来数据成本。因此,缓存和重用之前获取的资源的能力,是优化效率的一个至关重要的方面。

python3.7一些有趣的新特性

其实python3.7在两个多月前就发布了,因为各种原因(主要懒就是了qaq,一直没怎么仔细关注,所以拖到了现在。唉,转眼八月就到尾巴上了。

总之,本文将介绍python3.7中比较有趣的一些新特性。让我们开始吧。

使用位运算实现加减乘除

加法

加法可以拆分成几个步骤,首先是每位上的数对应相加,将结果与对应的基数取模,设置为当前位,然后处理相加之后产生进位的位,给它们的上一个拥有更大权值的位加上一,如果又产生进位,就如此循环,直到没有进位为止。

在python中延迟执行函数

js有一个常用的函数叫做setTimeout,可以延迟函数的执行而又不阻塞当前上下文。这是一个奇特的行为,因为js本身运行在单线程中。因此,在某些时候,可以发现,js上下文中的函数会影响setTimeout排定函数的运行。例如,如果此时有一个while true的函数阻塞,传递给setTimeout的函数也永远不会执行。

在python中,也可以实现类似js 中setTimeout的行为。主要发现了以下几种方法:

LZ77编码简介

LZ77是一个由Abraham Lempel于1977年发表的无损压缩算法,其思想与霍夫曼编码有很大差别。霍夫曼编码主要是用较短的编码代替出现频率较高的字符,用较长的编码代替出现频率较低的字符;LZ77编码的核心思想则是将重复出现的较长字符串(短语),使用较短的、指向前面第一次出现的字符串的标记来代替。标记与原序列之间是一种映射,因此,LZ77算法可以说成是基于字典的算法。

实现霍夫曼编码

霍夫曼编码是一种使用变长编码表编码源符号的无损压缩算法。它的核心思想是计算各个符号的权重,出现次数较多的符号拥有较大的权重,出现次数较少的符号拥有较小的权重。然后对符号进行前缀编码,用较短的编码表示拥有较长权重的符号,用较长的编码表示拥有较短权重的符号。这样,总体来说,对于符号出现次数不均衡的序列,霍夫曼编码就能够拥有较好的表现。

十种常见的排序方法

简介

本文介绍了十种常见简单排序算法的python实现。

将要介绍的这十种排序算法分别是——冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、计数排序、基数排序、桶排序