登录
  • 人们都希望被别人需要 却往往事与愿违
  • 在软件'可重用'之前先得'可用'@Ralph Johnson (设计模式四人帮之一)

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

编程 Benny小土豆 4298次浏览 2404字 6个评论
文章目录[显示]

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

需求

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

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

b.json内容大致如下(大概16M的一个大文件):

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

想要的结果如下:

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

就是把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方法了。要不用[]直接取数据速度应该会再快点的。

优化结构之前:

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

优化之后:

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

大概提升了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在Windows下的使用

安装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

 


文章版权归原作者所有丨本站默认采用CC-BY-NC-SA 4.0协议进行授权|
转载必须包含本声明,并以超链接形式注明原作者和本文原始地址:
https://dmesg.app/list-dict-performance.html
喜欢 (10)
分享:-)
关于作者:
If you have any further questions, feel free to contact me in English or Chinese.
发表我的评论(代码和日志请使用Pastebin或Gist)
取消评论

                     

去你妹的实名制!

  • 昵称 (必填)
  • 邮箱 (必填,不要邮件提醒可以随便写)
  • 网址 (选填)
(6)个小伙伴在吐槽
  1. python 程序都能使用 Cython 编译吗?
    nels0n2019-04-16 17:48 回复
    • 不一定吧:-(
      Benny小土豆2019-04-17 09:38 回复
  2. 何为cython??
    hjh2019-04-13 15:26 回复
    • Cython是结合了Python和C的语法的一种语言,可以简单的认为就是给Python加上了静态类型后的语法,但由于会直接编译为二进制程序,所以性能较Python会有很大提升。
      Benny小土豆2019-04-14 08:11 回复
  3. 给大佬顶顶
    弦上韫玉2019-04-13 14:51 回复
    • 萌新瑟瑟发抖
      Benny小土豆2019-04-13 14:54 回复