列表与字典的查找、Cython 在 Windows 下的使用

昨天在工作时遇到一个小问题，同事的某 API 返回太慢了，我帮他优化下。简单的探究了下需求，发现了一点得优化的地方。

需求

需求很简单，就是对数据结构进行初步的整理。a.json 内容大致如下：

b.json 内容大致如下（大概 16M 的一个大文件）：

想要的结果如下：

就是把 sent_id 和 received_id 的值去 b.json 里查找对应的 itemid，然后在原始的 a.json 的结构中增加一项 data 列，记录 b 中的值。

在开始鼓捣之前，我们需要先了解下，在 Python 中，列表是一种非常重要的数据结构，特性有点像数据结构中的链表。列表结构简单，容易扩展，但是却有一个比较致命的弱点——查找元素比较慢。完全就是看命的操作，查找的元素是第一个还好，万一是最后一个，那就要全部遍历完才知道是否有对应的元素。

还有另外一种同样重要的数据结构，被称作字典。字典的特点就是查找很快，很快很快的那种。

原始实现

实现起来其实很容易，就是循环判断嘛，按照常规的思路，可能会这样实现：

for item_dict in a_list:
    re_data = []
    se_data = []
    for value_dict in b_list:
        if item_dict.get('received_id') == value_dict['itemid']:
            re_data.append(value_dict)
        elif item_dict.get('sent_id') == value_dict['itemid']:
            se_data.append(value_dict)

优化

老夫掐指一算，看出来几个这段代码中制约性能的因素：

1. 双循环增加时间复杂度
2. b_list 非常大，查找它恐怕不会是比较理想的解决方案。再加上它外面还有个循环，简直就是雪上加霜了

由于 b.json 是个大列表，列表里还有字典，因此不仅导致多了一层循环，还增大了列表不适合查找的特性。因此正确的解决思路是，将 b.json 的格式转换成字典，key 对应 item_id，值是一个列表，列表中的每个元素为字典。

由于我们并不预先知道字典的 key 是什么，因此只能动态的创建字典，使得它的值为空列表，然后追加数据。

完成这个操作大概有三个方法：

方法 1：跑两个循环

result = {}
for item in item_list:
    result[item['itemid']] = []
for item in item_list:
    result[item['itemid']].append(item)

思路很简单，时间复杂度也是线性的，可以接受

方法 2：使用 defaultDict

我们使用 defaultDict 定义字典，这样当访问不存在的 key 时返回列表，直接 append 就可以了。当然了要从 collections 里 import 这个好东西

from collections import defaultdict
 
d = defaultdict(list)
for item in item_list:
    d[item['itemid']].append(item)

方法 3：利用 setdefault

利用字典的 setdefault 方法，如果 key 不存在，我们可以让他返回个空列表，然后 append 呗~

result = {}
for item in item_list:
    result.setdefault(item['itemid'], []).append(item)

这三者性能上，肯定是方法 1 稍微差一点啦，至于 2 和 3，2 比 3 稍好一点的。

这样的字典创造出来之后，后面的事情就很好处理了

for item in a_list:
    item.setdefault("data", []).extend(d.get(item.get('received_id'), []))
    item.setdefault("data", []).extend(d.get(item.get('sent_id'), []))
 

由于 a.json 的数据不纯，有些元素没有 received_id，因此只能用 get 方法了。要不用 [] 直接取数据速度应该会再快点的。

优化结构之前：

优化之后：

大概提升了 30 倍吧。

还需要更快？

这个时候除了换个解释器（如 PyPy），提升配置，其实还有一个办法！那就是 Cython。如果你用的是 Anaconda 或者是 Linux，那就好办多了，那可真是太幸福了。但是 Windows……

安装编译环境

要么就用 mingw，要么就用 visual c++ build tools，以后者为例……

根据你的 Python 版本选择不同的 build tools 版本，

Python 3.6 对应 VS2015

Python 3.7 对应 VS2017

我就直接安装 Visual Studio Build Tools 2017

安装时选择如下组件就可以了

1. Visual C++ Build tools core features.
2. VC++ 2017 v141 toolset (x86,x64)
3. Visual C++ 2017 Redistributable Update
4. Windows 10 SDK (10.0.16299.0) for Desktop C++

安装 Cython

pip install cython

然后新建一个 pyx 文件，写代码……

再新建一个 setup.py

from distutils.core import setup
from Cython.Build import cythonize
setup(
name='Hello pyx',
ext_modules=cythonize('hello.pyx')
)

然后运行 python setup.py build

之后把 build/lib 下的那个 pyd（Linux 为 so）拷贝走，就可以 import 了……

参考资料

https://matthew-brett.github.io/pydagogue/python_msvc.html

https://www.cnblogs.com/freeweb/p/6548208.html