天天看点

#coding4fun#词频统计优化思路

关于这期的coding4fun,我选择的是hashmap方式实现。整体思路和流程大家可能都差不多,c++同学们的总结写的很好,一些逻辑优化都有总结,我这里介绍下java实现的一些优化吧。

开始读出文件转成string对象,然后通过string对象操作,代码写起来都比较方便。

但是有一个问题,文件读取出来的byte[]转成string对象非常耗时,一个1g的string对象分配内存时间就很长了,string对象内部使用char[],通过byte[]构造string对象需要根据编码遍历byte[]。这个过程非常耗时,肯定是可以优化的。

于是我使用bytestring类代替string

hashcode()和equals()方法参考string的实现。

在code4fun的16核机器上测试如下代码:

代码1:

代码2:

hashmap的实现,给单词计数时避免不了如下的代码:

本来这段代码没什么问题,但是当单词个数足够大的时候(最终1.1g的文件,有2亿多单词),这段代码就值得优化了。第一行创建的对象,只有单词第一次出现有用,其他时间都可以不用创建。

于是创建一个pmap类,继承hahsmap,并添加了一个get(bytestring bs, int start, int end)方法。上面的代码改为

concurrenthashmap的实现固然精妙,只是能不用锁尽量不用,实在用的时候,尽量减少范围。cas的方式虽然比锁好,但是还是有消耗。

我们使用多线程的方式统计,所以统计结果对象需要线程安全。开始使用atomicinteger,但是跟count++比起来效率还是差的非常多,单词个数越多越明显。

尝试使用volatile关键字效果也是不理想,然后比不上count++。

最后使用两个字段来解决这个问题:在线程内部统计单词个数时,使用count++方式;到合并环节,单词数已经不多,使用atomicinteger的方式累加,基本不影响效率。

通过减少锁的范围和锁的次数,来达到提升效率的目标。