Category Archives: 编程
在 MapReduce 分布式计算时有这样一种场景：mapper 输入来自多个不同的数据源，共同点是每行记录第一列是作为 key 的 id 列，reducer 需要根据数据源的不同，进行相应的处理。由于数据到 reducer 阶段已经无法区分来自什么文件，所以一般采取的方法是 mapper 为数据记录打一个 TAG。为了便于使用，我习惯于把这个 TAG 打到数据的第二列（第一列为 id 列，作为 reduce/join 的 key），所以有这样的 mapper 函数：
def mapper1(line):
l = line.split('\t', 1)
return "%s\t%s\t%s" % (l[0], 'TAG', l[1])
这样给定输入：
s = "3001 VALUE"
mapper1(s) 的结果就是：
s = "3001 TAG VALUE"
这是一个潜意识就想到的很直白的函数，但是我今天忽然脑子转筋，陷入了“这是最快的吗”思维怪圈里。于是我就想，还有什么其它方法呢？哦，格式化的表达式可以用 string 的 + 运算来表示：
def mapper2(line):
l = line.split('\t', 1)
return l[0] + '\t' + 'TAG' + '\t' + l[1]
上面是故意将 '\t' 分开写，因为一般 TAG 是以变量方式传入的。还有，都说 join 比 + 快，那么也可以这样：
def mapper3(line):
l = line.split('\t', 1)
l.insert(1, 'TAG')
return '\t'.join(l)
split 可能要消耗额外的空间，那就换 find：
def mapper4(line):
pos = line.find('\t')
return "%s\t%s\t%s" % (line[0:pos], 'TAG', line[pos+1:])
变态一点儿，第一个数是整数嘛，换成整型输出：
def mapper5(line):
pos = line.find('\t')
pid = long(line[0:pos])
return "%d\t%s\t%s" % (pid, 'TAG', line[pos+1:])
再换个思路，split 可以换成 partition：
def mapper6(line):
(h,s,t) = line.partition('\t')
return "%s\t%s\t%s" % (h, 'TAG', t)
或者干脆 ticky 一点儿，用 replace 替换第一个找到的制表符：
def mapper7(line):
return line.replace('\t', '\t'+'TAG'+'\t', 1)
哇，看一下，原来可选的方法还真不少，而且我相信这肯定没有列举到所有的方法。看到这里，就这几个有限的算法，你猜一下哪个最快？最快的比最慢的快多少？
先把计时方法贴一下：
for i in range(1,8):
f = 'mapper%d(s)' % i
su = "from __main__ import mapper%d,s" % i
print f, ':', timeit.Timer(f, setup=su).timeit()
下面是答案：
mapper1(s) : 1.32489800453 mapper2(s) : 1.2933549881 mapper3(s) : 1.65229916573 mapper4(s) : 1.22059297562 mapper5(s) : 2.60358095169 mapper6(s) : 0.956777095795 mapper7(s) : 0.726199865341
最后胜出的是 mapper7 （tricky 的 replace 方法），最慢的是 mapper5 （蛋疼的 id 转数字方法），最慢的耗时是最慢的约 3.6 倍。最早想到的 mapper1 方法在 7 种方法中排名——第 5！耗时是最快方法的 1.8 倍。考虑到 mapper 足够简单，这个将近一倍的开销还是有一点点意义的。
最后，欢迎回复给出更快的方法！
同其它领域一样，计算机科学和工程领域也是群星璀璨，有些耀眼的星光甚至刺得我们无法直视，只能匍匐在地上聆听神谕。也正如其它领域一样，虽然大家听到的是同样的话，却有各式各样不同的理解。我这里想讲的，就是我观察到的不同理解引发的现象。
“过早优化是万恶之源。” 这是 Donald Knuth 的一句名言。虽然大部分人都不知道，或者会忘掉前面半句：“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” Knuth 说出这句话时，可能想不到这句话会多么地流行，多么根植在很多人心中，以至于成为程序员偷懒的借口，阻碍进步的动力。因为有了这句话，在你指出别人代码中可以优化的问题时，还必须浪费口舌来解释这样的优化是必要的，不是过早优化或者过度优化。
就我的观察而言，对很多程序员来说，其能力还远远达不到过早优化的地步。但他感觉自己受到了 Knuth 的神启，仿佛具有了某种魔力，不优化代码反而成了一种优越感！关于大多数人是否具备过早优化代码的能力，我可以举几个至今我还觉得神奇的例子。
我供职的公司内部有这样一个模块，隔一两个星期总会挂掉几台服务器，现象是内存占满导致服务器假死或者宕机，但事实上根据请求推算根本不会同时使用那么多内存。最后的排查结果发现，每个线程都有这样一个数据结构，它的内存是只增不减的。当你调用它的 clear 接口，它只会把所有的内存还回自己的内存池里，而不是还给系统。这就导致可供分配的内存越来越少、越来越少...
还是这个模块里，仅仅加载一个几 K 的配置文件，就能够占用超过 1G 的内存。为什么呢？因为它用 char str[MAX_CONF_LEN] 保存配置字符串，用 struct xx_t xx[MAX_XX_NUM] 读取配置，而且这个 struct 中还有嵌套的 struct yy_t y[MAX_YY_NUM] 数组。
该模块是个个例吗？还是这家公司，一个全公司使用的公共日志库，LOGGING 宏定义中直接传一个需要系统调用的函数作为参数，导致无论关不关该级别日志都要进行一次系统调用。
这家公司好歹也位列国内顶尖的互联网公司之一，工程师的招聘要求也是极其高的，还会普遍出现这种肆意浪费资源的情况。那么我想对于大部分工程师来说，谈避免“过早优化”、“过度优化”，还为时尚早。
还有一句名言“好代码本身就是最好的文档。当你需要添加一个注释时，你应该考虑如何修改代码才能不需要注释。” 这是 Steve McConnell 说的。同样，大部分人都不知道，或者忘掉后面半句：Good code is its own best documentation. As you're about to add a comment, ask yourself, "How can I improve the code so that this comment isn't needed?" Improve the code and then document it to make it even clearer. 如果你是程序员，回想一下多少次跟别人讨论代码是不是必须要注释时，这句话被引用到；有很多次在写代码时喜爱这句话，又多少次改别人的代码时痛恨这句话。
还是从我个人的观察来看，对很多程序员来说，其编码能力还不足以达到“代码本身就是最好的文档”的地步，包括我自己。敝司招聘过很多顶尖的工程师，有传说中的各种杰出前辈，可能在各种学校、公司内部事迹广为流传。但若是你哪天继承了他的代码遗产，就会发现很多传说中的明星跌落凡尘。成百上千行没有注释，使用一个公共库函数时要么接口就根本没注释只能基本靠猜，要么即使注释也语焉不详让你踩到未注明的大坑。每到这个时候你心里总会暗暗骂娘，后面别人再谈到他的光辉事迹时，你跟随讪笑时心中暗自腹诽：“牛逼个锤子！”
但我想很多人争论的焦点是：“注释是不是不可省略的、要强制执行的？”即使个别人能力真能达到“代码本身就是最好的文档”的地步（我还没见过），我也不建议在团队中传播“注释可以省略”这一想法。因为如果你说“注释可以省略”，可能你会发现大家都理解和实践成“终于可以不写注释了”。如果一个刚刚大学毕业、脑袋里从来没有过 documentation 概念、从来没写过注释的新人进入公司，就“终于可以不写注释了”，那么我想他的代码会很难达到“代码本身就是最好的文档”这个级别。因为他根本没有机会懂得什么叫做 documentation。
在公司里，代码注释深远地影响着团队合作的每个人，以及软件生存期里所有的维护者，甚至会影响自己的职业声誉。所以无论别人怎么想，我对注释这个问题的答案始终是：“注释是不可省略的，越完善越好的，甚至强制执行矫枉过正也没关系的！”
从上一篇《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 = Falset0 = 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_rowMsgBox "在机器表上生成一级分中心。共处理 " & dispatch_nrows & " 条记录，总耗时" & Timer - t0 & "秒。"
' 销毁建立的词典
Set map_dict = Nothing' 打开自动计算和屏幕刷新
Application.Calculation = xlCalculationAutomatic
Application.ScreenUpdating = True
'
End Sub
最后补充一点：我先实现的词典查找，后发现性能问题根源，所以未能去比较 VLOOKUP 与词典查找两种方式的具体性能差异。我想如果差异可以忍受，那么直接在 VBA 中调用 VLOOKUP 公式或许是一种更为简单的实现。