什么是内存管理

内存是数据存储的介质，其访问速度比硬盘快，但是容量相对更小，且断电后数据会丢失。由于内存的种种性质，其成为了计算机开机后访问数据的最佳位置，操作系统或者用户进程所访问的数据大都也都是在内存上。

内存管理实际上管理的是内存物理介质的状态。内存作为一种物理介质，每一个bit都是0/1两种状态，它并不清楚自身存储的数据含义，甚至也并不清楚自身是否被使用了。

通常来说，操作系统为我们管理了作为物理介质的内存，即使用虚拟内存和分页的方式，使得我们的用户进程能够访问连续的/不受物理内存大小限制的虚拟地址空间。其次，c运行库中的malloc/calloc函数在操作系统层面之上提供了堆空间内存分配的接口。而python在此基础之上，为所有PyObject提供了统一的内存分配/管理接口。

为什么要进行内存管理

个人认为，主要原因是为了减少内存分配调用而产生的开销；此外，通用的内存管理也方便在此基础上进行垃圾回收等其他操作。当调用malloc函数时，我们通常会陷入内核进行系统调用，甚至会产生缺页异常从而分配新的页并更新页表，这样的操作是相对费时的。python内存管理的核心目的就是减少小对象的内存分配次数，从而提高程序运行性能。

什么是super

super实际上就是抽象的父类对象，用面向对象的方式来调用父类方法的一层封装。典型的使用方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Base(object):
    def __init__(self):
        pass
    
    @classmethod
    def test(cls):
        pass

class Derived(Base):
    def __init__(self):
        super(Derived, self).__init__()     # (1)
        # super().__init__()                # python3
        # Base.__init__(self)               # 非面向对象
    
    @classmethod
    def test(cls):
        super(Derived, cls).test()          # (3)
        # super().test()                    # python3

super的四种用法

根据super的文档，其一共有三种用法：

• super(type, obj) -> bound super object; requires isinstance(obj, type)
• super(type) -> unbound super object
• super(type, type2) ->bound super object; requires issubclass(type2, type)

其中，第二种用法相对少见。除此之外，在python3中，可以使用无参数的super。

前言

早在去年11月下旬，我就想自己实现一个LR语法分析器，可自身主观能动性不足，拖延了一个多月的时间才正式开工。终于在上班前夕的自我隔离期间，花了两个下午的时间完成了一个LR(0)语法分析器的雏形，因而写下该篇日志记录一下。

什么是LR(k)语法分析技术

L/R/k分别是什么意思

• L的意思是from Left to right，即从左到右来分析输入
• R的意思是构造出的是最右推导，即Rightmost
• k的意思是在语法分析决定时向前看k个符号，k省略则为1

自底向上的语法分析技术

LR语法分析技术是一种自底向上的语法分析技术，自底向上也就是从一个非终结符串开始规约的过程，每次归约会使用一个产生式将其中的一个子串（称为句柄）替换为该产生式左侧的非终结符，中间产物被称为是一个最右句型。例如，对于以下的文法：

WHY SQLite

为什么要学SQLite？起因来源于云风的《Lua源码赏析》这本小册子，里面提到了reddit上的一个问题，问的是最值得阅读的well-designed的开源项目，其中SQLite广受好评，此外就是Lua的虚拟机（等我python再学习深入后也可以对照着看看Lua，毕竟Lua相对简单，其实更容易上手）。此外，作为一个非科班出生的客户端程序，对于服务端的一些知识了解其实是相对缺乏的，数据库一直是我的知识盲区之一，也希望乘此机会了解数据库的相关知识。

什么是闭包

闭包closure指的是引用了上层函数作用域的变量。当编程语言支持函数能够作为返回值，则闭包的实现则不可或缺，在函数内定义的子函数引用了父函数的变量，就是使用了语言的闭包特性。python中，一个通常会令人困惑的例子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def generate_funcs():
	ret = []
	for i in range(10):
		def new_func():
			print i
		ret.append(new_func)
	return ret

for func in generate_funcs():
	func()
    
// output
// 9
// 9
// ...

大多数初学者的直觉反应，程序最终会依次输出0到9，然而最终所有的函数都输出了9。因为闭包所绑定的是变量的名字，而不是变量的值，变量真正的值需要在运行时才能够确定。而当运行这几个内部函数时，变量i已经走完了循环，定格在了9这个值。如果想要绑定值，可以使用函数的默认参数来进行传递。

前言

在python中，一切皆是对象，函数也不例外。函数也是python中的一等对象first-class object之一。所谓一等对象，代表了这类对象能够被动态地创建，销毁，作为函数的参数和返回值，拥有和其他变量一样的特权。在C语言中，函数以指针的方式存在，函数指针指向的是什么呢？我不确定，但我猜想是函数编译成的机器指令的地址，函数的调用也就是指令跳转的过程。python中的函数实际上也是类似的思想，不止函数如此，整个python虚拟机也都非常类似操作系统执行c代码的过程。

函数作为对象

函数虽然更像是一种动作，但是动作也能够以数据的方式存在，这样的数据也就是指令。python中的函数，也就是类型为function的对象，在CPython中对应的结构体为PyFunctionObject。函数对象的定义在funcobject.h中，摘抄定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

typedef struct {
    PyObject_HEAD
    PyObject *func_code;		/* A code object */
    PyObject *func_globals;		/* A dictionary (other mappings won't do) */
    PyObject *func_defaults;	/* NULL or a tuple */
    PyObject *func_closure;		/* NULL or a tuple of cell objects */
    PyObject *func_doc;			/* The __doc__ attribute, can be anything */
    PyObject *func_name;		/* The __name__ attribute, a string object */
    PyObject *func_dict;		/* The __dict__ attribute, a dict or NULL */
    PyObject *func_weakreflist;	/* List of weak references */
    PyObject *func_module;		/* The __module__ attribute, can be anything */

    /* Invariant:
     *     func_closure contains the bindings for func_code->co_freevars, so
     *     PyTuple_Size(func_closure) == PyCode_GetNumFree(func_code)
     *     (func_closure may be NULL if PyCode_GetNumFree(func_code) == 0).
     */
} PyFunctionObject;

前言

很久之前我就尝试过编译python源码，但是最后好像以失败告终，今天偶然想起竟然异常顺利，终于把编译python源码的心愿完成了。之后就可以通过修改源码的方式来学习python了。

准备工具：

• python2.7.15源码
• Windows10 sdk

步骤

总的来说，编译python源码其实很简单，直接进入PCBuild文件路径调用build.bat即可。但是我这里会遇到了几个编译错误，估计大家也都会遇到。

1

C:\Program Files (x86)\MSBuild\Microsoft.Cpp\v4.0\V140\Microsoft.Cpp.Platform.targets(56,5): error MSB8020:The build tools for Visual Studio 2008 (Platform Toolset = 'v90') cannot be found. To build using the v90 build tools, please install Visual Studio 2008 build tools.  Alternatively, you may upgrade to the current Visual Studio tools by selecting the Project menu or right-click the solution, and then selecting "Retarget solution". [E:\game_development\books\Python-2.7.15\PCbuild\pythoncore.vcxproj]

首先是一个编译工具版本错误，我这里是visual studio 2015版本，重新打开解决方案vs会自动提示升级项目，直接升级即可。

前言

新开了一个分类，来学习python源码。python源码的结构还是比较清晰，刚开始我们可以从Objects目录入手，该目录下存放的是python中内置对象的实现(built-in objects)，所谓的内置对象，其实就是cpython中用c实现的对象。我们可以从一个比较简单的基本对象tuple入手，来了解一下python对象的实现。

tuple对象的定义

tuple对象的定义位于Include/tupleobject.h中，这是一种c语言中声明可变长度对象的常用做法，即在结构体末尾声明一个长度为1的数组，在申请内存的时候，多申请的内存都会作为该数组的存储空间。可以看出，tuple中存储的python对象是直接放置在结构体中的，而list由于其是可变的，其只存放了指向python对象的指针。

1
2
3
4
5
6
7
8
9

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];

    /* ob_item contains space for 'ob_size' elements.
     * Items must normally not be NULL, except during construction when
     * the tuple is not yet visible outside the function that builds it.
     */
} PyTupleObject;

前言

今天遇到一道有趣的题目，开始以为时间是离散，于是遍历了每一秒时刻的情况，发现和答案有一定的误差。后来意识到了指针都是连续移动的，当天想了很久也没想出啥好方法，看网上的讨论给的方法也很暴力。第二天灵光一闪想出了一个不那么粗暴的的方法，在这里记录一下。

从点到线

我的思路一直是离散的，也就是“点”的思想，总想要计算某个时刻指针的位置，判断某个时刻能不能满足条件。但是在连续的情况下，这样的思路是非常耗费计算资源的，这有点像微分的思想，我可以把时间间隔缩小到0.0001秒，这样的误差可能就可以忽略不计，但肯定会超时。

另一种思路去考虑刚好满足条件的时刻，与刚好不满足条件的时刻，这个区间内的所有时间也就是满足条件的时间。由于三个指针都是匀速运动的，它们两两之间的角度差也是线性变化的，函数图像如下图所示。

一些无关的感想

最近在看编译原理龙书，词法分析一章看的差不多了，但仍然处于一种似懂非懂的状态，这又让我想起，大学期末考试之前复习的时候，反而是我能够真正将所有知识串联起来，融汇贯通的时候，这也就是总结和复习的重要性，因而萌生了将最近的所学所想总结一下的想法。另外，这两天忙里偷闲一直在看云风的博客，十分佩服，更加坚定了总结与记录的念头。

词法分析的作用

词法分析是编译过程的第一阶段，它接触到的是第一手的程序源代码。它只处理词法而不处理语法，也就是他不在意串的含义，只在意串的模式，但实际上这是一种简化，因为计算机识别不了语义，只能用转化为识别模式。就像收营员结账用的条形码扫描机，扫描机并不知道你买的到底是什么东西，它只知道符合某种模式的条形码，以此来区分不同类型的物品。而不同的物品有不同的条形码这样的前提条件，也就是不同语义的串有不同的模式，是需要设计者来保证的。

也就是说，词法分析的作用是识别出程序代码中具有某种模式的串。再类比一下，就是从一串潘多拉手链中识别出每颗珠子的类型。（注意珠子之间可能有联系，可能多颗珠子合起来才是一个配件）