9.9 erlang并发编程杂项-效率

最后我们来讨论一下效率。这并不是说我们认为这个主题不重要,而是因为我们相信过早关注效率问题会导致不良的程序设计。关注重点应该一直放在程序的正确性上,为了达到这个目的,我们提倡开发简练漂亮且“明显”正确的算法。

作为示例,我们将展示如何将低效的程序改造为高效的程序。

作为练习,我们从一个包含某假象公司员工信息元组的文件开始,该文件的内容为:

{202191,’Micky’,’Finn’,’MNO’,’OM’,2431}.
{102347,’Harvey’,’Wallbanger’,’HAR’,’GHE’,2420}.
... 2860 lines omitted ...
{165435,’John’,’Doe’,’NKO’,’GYI’, 2564}.
{457634,’John’, ’Bull’,’HMR’,’KIO’, 5436}.

我们要写一个程序来输入这些数据、将每个条目都放入字典、访问所有条目一遍,再将数据写回文件。这个程序将频繁执行,因此我们得让它尽可能地快。

文件访问

从上述的元组文件中读入数据的最简单的方法就是使用file:consult(File)读取文件(参见附录C)——这个方法很耗时,因为每一行都会被读取和解析。一个好一点的做法是将输入文件从文本格式改为二进制格式。通过以下函数可以实现:

reformat(FileOfTerms, BinaryFile) ->
    {ok, Terms} = file:consult(FileOfTerms),
    file:write_file(BinaryFile, term_to_binary(Terms)).

要读入二进制文件并恢复原始数据,执行:

read_terms(BinaryFile) ->
    {ok, Binary} = file:read(BinaryFile),
    binary_to_term(Binary).

读取二进制文件并将结果转换为项式要比读取并解析一组项式要快得多,从下表便中可见一斑:

文本大小(bytes) 二进制大小(bytes) file:consult (ms) read_terms (ms) 耗时比例
128041 118123 42733 783 54.6
4541 4190 1433 16 89.6

对于4.5K的文件,二进制文件读取要快90倍;对于128K的文件要快55倍。注意二进制文件要被文本文件小一些。

字典访问

我们使用了不同的方法来构建和更新雇员字典。这些方法包括:

lists

所有雇员记录都保存在一个列表中。在表头进行首次插入,其余更新对列表进行线性扫描。

avl

采用第??节描述的AVL树插入算法。

hash

采用程序9.4的散列算法。

为了检验不同方法的效率,我们对我们的每一条雇员数据都进行一次插入和查找,得到以下的计时结果:

条目数 AVL插入 AVL查找 列表插入 列表查找 散列插入 散列查找
25 5.32 0.00 0.00 0.64 1.32 0.00
50 1.32 0.32 0.00 1.00 0.32 0.00
100 2.00 0.50 0.00 1.50 0.33 0.16
200 9.91 0.50 0.00 3.00 2.08 0.17
400 28.29 0.46 0.04 5.96 4.25 0.09
800 301.38 0.54 0.02 11.98 1.77 0.15
1600 1060.44 0.61 0.02 24.20 4.05 0.14

上表中每次插入或查询的时间单位都是毫秒。我们看到对于大小超过800的数据表,散列表的查询效率是最高的。

上面我们看到使用二进制文件和散列查询算法要比使用file:consult和简单列表查询方法快六千倍。和传统命令式语言一样,决定程序效率的最重要因素还是良好的算法设计。

转载请注明:《9.9 erlang并发编程杂项-效率