c4f 玄胤总结

c4f 玄胤总结

近日团队举办了编程比赛，题目是：解析一个大文件，用最快的速度统计出出前频率最高的前十个单词。终最得了第四。这里我说说我的做法：

• 首先，大致看了一下大家的代码，发现大家都是自己去实现多线程的，其实没必要，可以利用openMP只需要几行注解就可以实现并行计算，例如：

• 编译器就会自动编译启动cpu_count个线程来计算，很爽，有木有！编译时只需要加上两个参数就可以了，只是要gcc4.1以后的都支持

• 另外就是无锁hash_table，这个可以参看我的博客：.html

• 最后我使用了一种并行合并排序来统计前十的单词，使用openMP也就几行代码，很简单的，如下：

除些之外我还使用文件内存映射，单词hash在扫描时就进行计算（就是扫一个byte算一个，直到非ASCII码，就可以得到本些单词的hash），这样基本上就可以到3s左右，但lf_hash的问题是使用了__sync_add_and_fetch来统计出现频率，虽然可以无锁，但总的来说还是串行的，因此我就把原来的int改成int[]，每个线程一个，这样每个线程都只写自己的，不存在竞争区，最后在取出所有entries的时候再进行合并，如下：

从而统计出总的值

转载于: