用词典查找代替VLOOKUP

目录 编程

从上一篇《PYTHON操作EXCEL》可以看到,Python 操作 Excel 已非常自如方便。但是 Python 和相关库毕竟是一个额外的依赖,若能从 Excel 自身解决此类问题,自然是更为易用。

1. VBA 中的哈希表

用 Python 的着眼点主要是 VLOOKUP 公式太慢了,所以关键是要找到一种更高效的算法或数据结构定位数据。VLOOKUP 要求对列进行排序,内部应该是对列内数据进行二分查找,算法上不好再优化了,那就只好更换一种数据结构。搜索了一下,VBA 提供了 Scripting.Dictionary 这一词典结构,而且有文章说内部是哈希表实现,那就正是我要的东西了。

这样,VLOOKUP(lookup_value,table_array,col_index_num,range_lookup) 这一公式就转为下面的词典查找方式来实现:

  • 使用要从中进行查找的 table_array 内容构建词典。用 table_array 第一列作为 key,table_array 第 col_index_num 列作为 value,插入 Dictionary 中:Dictionary.Add key, value;
  • 查找时只需直接取 Dictionary 内的值 Dictionary.Item(lookup_value),即可完成查找;

若是仅仅 VLOOKUP 一次,倒也不必费劲先建立起一个词典。但当使用同样 VLOOKUP 公式的单元格很多时(比如几万个),就显得其必要了。因为 Dictionary 只需要建立一次,就可以用 O(1) 的复杂度进行多次查找了。

2. VLOOKUP 慢,主要问题不在算法上

从算法角度,词典查找的确快于二分查找,但优势并不是那么明显。所以在具体执行时,我发现使用词典查找的 VBA 宏运行速度并不比 VLOOKUP 快多少,运行时 Excel 仍然会导致系统假死几个小时。按说如此简单的程序不应该那么慢,问题究竟在哪里呢?

经过一段摸索,我才发现问题的根源所在:

  • VBA 往 Excel 表格中填内容时,会引发表格中已有公式的自动计算,非常耗时;
  • Excel 表格内容更新时,会触发屏幕显示内容的自动刷新,代价也很高;

所以提高 VBA 脚本执行性能的关键点,在于计算时关掉公式自动计算和屏幕刷新,这也是我始料未及的。在 VBA 中实现这两点很容易,但由于 VLOOKUP 本身即是公式,我没能想通直接调用 VLOOKUP 时如何避免这两点带来的性能损失。

3. 示例 VBA 代码

在做了上面提到的两次优化之后,原来 VLOOKUP N 个小时才能完成的任务,只用了 7 秒钟就执行结束了。

下面是我写的一段示例代码。我不熟悉 VBA 语言,只是照葫芦画瓢。代码规范程度相差甚远,但题意应是体现其中了。有心的朋友可以用作参考。

Sub 在机器表上生成一级分中心()
'
' 在机器表上生成一级分中心 Macro
'
Application.Calculation = xlCalculationManual
Application.ScreenUpdating = False

t0 = Timer
' 词典
Set map_dict = CreateObject("Scripting.Dictionary")

' 打开分中心映射表
Set map_sheet = Worksheets("分中心映射表")
map_nrows = map_sheet.Range("A300").End(xlUp).Row
Set my_rows = map_sheet.Range("A2:B" & map_nrows).Rows

' 遍历分中心映射表,获得 分中心 对应的一级分中心,插入词典
For Each my_row In my_rows
   center = my_row.Cells(1, 1).Value
   city = my_row.Cells(1, 2).Value
   If Not map_dict.Exists(center) Then
       map_dict.Add center, city
   End If
Next my_row

' 打开机器表
Set dispatch_sheet = Worksheets("机器表")
dispatch_nrows = dispatch_sheet.Range("G99999").End(xlUp).Row
Set my_rows = dispatch_sheet.Range("K2:L" & dispatch_nrows).Rows

' 遍历开通表,通过词典获得 machine_id 对应的一级分中心,插入开通表
For Each o_row In my_rows
   center = o_row.Cells(1, 1).Value
   o_row.Cells(1, 2).Value = map_dict.Item(center)
Next o_row

MsgBox "在机器表上生成一级分中心。共处理 " & dispatch_nrows & " 条记录,总耗时" & Timer - t0 & "秒。"

' 销毁建立的词典
Set map_dict = Nothing

' 打开自动计算和屏幕刷新
Application.Calculation = xlCalculationAutomatic
Application.ScreenUpdating = True
'
End Sub

最后补充一点:我先实现的词典查找,后发现性能问题根源,所以未能去比较 VLOOKUP 与词典查找两种方式的具体性能差异。我想如果差异可以忍受,那么直接在 VBA 中调用 VLOOKUP 公式或许是一种更为简单的实现。

Python操作Excel

目录 编程

老婆单位有时候有一些很大的 Excel 统计报表需要处理,其中最恶心的是跨表的 JOIN 查询。他们通常采取的做法是,把多个 Excel 工作簿合成一个工作簿的多个表格,然后再跑函数(VLOOKUP之类)去查。因为用的函数效率很低,在 CPU 打满的情况下还要跑几个小时。

然后我就看不过去了,我也不懂 Excel,不知道如何优化,但我想用 Python+SQLite 总归是能够实现的。于是就尝试了一把,效果还不错,一分钟以内完成统计很轻松,其中大部分时间主要花在读 Excel 内容上。

1. Python 操作 Excel 的函数库

我主要尝试了 3 种读写 Excel 的方法:

1> xlrd, xlwt, xlutils: 这三个库的好处是不需要其它支持,在任何操作系统上都可以使用。xlrd 可以读取 .xls, .xlsx 文件,非常好用;但因为 xlwt 不能直接修改 Excel 文档,必须得复制一份然后另存为其它文件,而且据说写复杂格式的 Excel 文件会出现问题,所以我没有选它来写 Excel 文件。

2> openpyxl: 这个库也是不需要其它支持的,而且据说对 Office 2007 格式支持得更好。遗憾地是,我经过测试,发现它加载 Excel 文件的效率比 xlrd 慢 3 倍以上,内存使用在 10 倍以上,于是就放弃了。

3> win32com: Python Win32 扩展,这个库需要运行环境为 Windows+Office 对应版本。由于 Python Win32 扩展只是把 COM 接口包装了一下,可以视为与 VBA 完全相同,不会有读写格式上的问题。尝试了一下用 win32com 读取 Excel 文件,效率还是比 xlrd 慢一些。

由于读取效率上 xlrd > win32com > openpyxl,所以我自然选择了 xlrd 用来读取统计报表;而最终输出的报表格式较复杂,所以选择了 win32com 直接操作 Excel 文件。

2. Python 里的关系型数据库

SQLite 是一个非常轻量级的关系型数据库,很多语言和平台都内置 SQLite 支持,也是 iOS 和 Android 上的默认数据库。Python 的标准库里也包含了 sqlite3 库,用起来非常方便。

3. 用 xlrd 读取 Excel 并插入数据库样例

如果数据量不大,直接用 Python 内部数据结构如 dict, list 就够了。但如果读取的几张表数据量都较大,增加个将数据插入数据库的预处理过程就有很大好处。一是避免每次调试都要进行耗时较长的 Excel 文件载入过程;二是能充分利用数据库的索引和 SQL 语句强大功能进行快速数据分析。

#!/usr/bin/python
# -*- coding: gbk -*-

import xlrd
import sqlite3

# 打开数据库文件
device_city_db = sqlite3.connect('device_city.db')
cursor = device_city_db.cursor()

# 建表
cursor.execute('DROP TABLE IF EXISTS device_city')
cursor.execute('CREATE TABLE device_city (device_id char(16) PRIMARY KEY, city varchar(16))')
 
# 打开 device 相关输入 Excel 文件
device_workbook = xlrd.open_workbook('输入.xlsx')
device_sheet = device_workbook.sheet_by_name('设备表')

# 逐行读取 device-城市 映射文件,并将指定的列插入数据库
for row in range(1, device_sheet.nrows):
   device_id = device_sheet.cell(row, 6).value
   if len(device_id) > 16:
       device_id = device_id[0:16]
   if len(device_id) == 0:
       continue
   city = device_sheet.cell(row, 10).value
   # 避免插入重复记录
   cursor.execute('SELECT * FROM device_city WHERE device_id=?', (device_id,))
   res = cursor.fetchone()
   if res == None:
       cursor.execute('INSERT INTO device_city (device_id, city) VALUES (?, ?)',
                      (device_id, city))
   else:
       if res[1] != city:
           print '%s, %s, %s, %s' % (device_id, city, res[0], res[1])
device_city_db.commit()

4. 将结果写入 Excel 文件样例

使用 win32com 写入 Excel 的时候要注意,一定要记得退出 Excel,否则下次运行会出错。这需要增加异常处理语句,我这里偷了个懒,出了异常后要手动杀死任务管理器中的 excel 进程。至于 win32com 中类的接口,可以从 MSDN 网站查阅。

import win32com.client as win32
import os
excel = win32.gencache.EnsureDispatch('Excel.Application')
excel.Visible = False
# 貌似这里只能接受全路径
workbook = excel.Workbooks.Open(os.path.join(os.getcwd(), '输出.xlsx'))
month_sheet = workbook.Worksheets(1)
# 计算文件中实际有内容的行数
nrows = month_sheet.Range('A65536').End(win32.constants.xlUp).Row
# 操作 Excel 单元格的值
for row in range(5, nrows-4):
   month_sheet.Cells(row, 1).Value += something
# 保存工作簿
workbook.Save()
# 退出 Excel
excel.Application.Quit()

Python JSON模块解码中文的BUG

目录 编程

很多语言或协议选择使用 ASCII 字符 “\”(backslash,0x5c) 作为字符串的转义符,包括 JSON 中的字符串。一般来说,使用 Python 中的 JSON 模块编码英文,不会存在转义符的问题。但如果使用 JSON 模块编解码中文,就可能面临着中文字符包含转义符带来的 bug。本篇文章给出了一个 badcase。

中文解码错误

测试用例文件里面包含繁体的“運動”二字,使用 GB18030 编码。使用 json 解码的错误如下:

$ cat decode.dat
{"a":"運動"}
$ python
>>> import json
>>> fp=open('decode.dat', 'r')
>>> json.load(fp, encoding='gb18030')
Traceback (most recent call last):
  File "", line 1, in 
  File "/home/yangwb/local/lib/python2.7/json/__init__.py", line 278, in load
    **kw)
  File "/home/yangwb/local/lib/python2.7/json/__init__.py", line 339, in loads
    return cls(encoding=encoding, **kw).decode(s)
  File "/home/yangwb/local/lib/python2.7/json/decoder.py", line 360, in decode
    obj, end = self.raw_decode(s, idx=_w(s, 0).end())
  File "/home/yangwb/local/lib/python2.7/json/decoder.py", line 376, in raw_decode
    obj, end = self.scan_once(s, idx)
UnicodeDecodeError: 'gb18030' codec can't decode byte 0xdf in position 0: incomplete
multibyte sequence

发生这个问题的原因,就存在于“運”字的编码之中。“運”的 GB18030 编码是 0xdf5c,由于第二个字符与转义符 “\” 编码相同,所以剩下的这个 0xdf 就被认为是一个 incomplete multibyte sequence。

我本来认为,既然已经提供了编码,json 模块就能够区分汉字与转义符(所以我觉得这应该是 json 的一个 bug)。但从实验来看,并非如此。对于一些不需提供字符编码的 JSON 解码器来说,我们倒可以用一种比较 tricky 的方法绕过上面这个问题,即在“運”字后面加一个额外的转义符:

{"a":"運\動"}

遗憾的是,这种方法对 Python 的 json 模块不适用。我仍不知道该如何解决这个解码问题。

中文编码——没错误!

对于相同的 case,Python 倒是能够编码成功:

$ cat in.dat
運動
$ python
>>> import json
>>> in_str = open('in.dat', 'r').read()
>>> out_f = open('out.dat', 'w', 0)
>>> dump_str = json.dumps({'a': in_str}, ensure_ascii=False, encoding='gb18030')
>>> out_f.write(dump_str.encode('gb18030'))
$ cat out.dat
{"a": "運動"}

所以这件事情就把我给搞糊涂了,Python 的 json 模块不能解码自己编码的 json 串。所以我觉得这可能是一个 bug,或者至少是 2.7.1 版本的 bug。

PS: 要仔细看文档

20120516:经网友 TreapDB 提醒,加载字符串时自己做 Unicode 转换,貌似能够解决这个问题。

$ cat decode.dat
{"a":"運動"}
$ python
>>> import json
>>> in_str = open('decode.dat', 'r').read().decode('gb18030')
>>> json.loads(in_str)

回头仔细看了一下 json 的文档,其中有这么一段:

Encodings that are not ASCII based (such as UCS-2) are not allowed, and should be wrapped with codecs.getreader(encoding)(fp), or simply decoded to a unicode object and passed to loads().

已经注明了 encoding 不支持非 ASCII-based 编码的参数,所以应该使用 getreader 进行转码,而不是让 json 模块去转码。看来是我没读懂文档,大惊小怪了,回家面壁去!

>>> json.load(codecs.getreader('gb18030')(fp))