Individual Project - Word frequency program - Multi Thread And Optimization

作业说明详见:http://www.cnblogs.com/jiel/p/3978727.html

一、开始写代码前的规划:

1、尝试用C#来写,之前没有学过C#,所以打算先花1天的时间学习C#

2、整个程序基本分为文件遍历、单词提取、单词匹配、排序、输出几个模块,各个模块大致时间如下:

  1. 文件遍历,5分钟
  2. 单词提取,手写或者正则表达式,5分钟
  3. 单词匹配,3个小时
  4. 排序,需要建立word类以及使用一些类似map神马的东西,3小时
  5. 输出,一个循环输出就全部结束了,5分钟

3、调试以及优化,一天半。

总共预计:两天

二、实际用时:

  1. 学习C#:大概用了半天,中途在周一上大数据的时候老师讲到了Map-Reduce模型http://blog.jobbole.com/1321/,想到了可以用一下上学期学的多线程来搞一搞,计划有变..学习c#下的多线程约一天,顺道推荐下这个讲多线程的博客http://www.cnblogs.com/leslies2/archive/2012/02/07/2310495.html
  2. 程序逻辑结构设计40分钟左右。
  3. 文件遍历,5分钟。
  4. 单词提取:Extended Mode比较难手写,用了正则,10分钟。
  5. 单词匹配:用C#中的Dictionary,轻松了不少,Dictionary是变种的HashTable,查询和插入操作都只需O(1)复杂度,没有用SortedDictionary,不清楚是不是用RB-Tree实现的...
  6. 排序:快排,10分钟。
  7. 调试以及优化,代码优化花了比较多的时间,而且有时候用自己想的方法优化发现比不优化前还差,总共用大概一天吧。

  总共用时:两天。

三、性能优化

  先强行目测优化一些细节:

  1. Dictionary.Trygetvalue代替Dictionary.containsKey();

  2. 使用type[]数组来辅助判断合法单词,比正则快很多;

  一轮优化

  先进行simple mode的测试,性能测试文件夹包含各种英文小说(并且存在文件套文件套到死的情况)共计大小170M,200来个文件(存在单个文件大小超过9M的情况)

        Individual Project - Word frequency program - Multi Thread And Optimization

  优化前性能分析:用时8.5s

Individual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And Optimization

跟踪函数发现主要耗时间的是手写的ToHigher函数以及ToString()转换,由于不能直接修改string,手写函数会多出ToString()转换时间,于是考虑采用String自带的ToUpper()函数,同时简化一些判断的书写

  优化结果:时间减少到7s左右,比初始时优化了20%时间

Individual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And Optimization

主要耗时函数变为string自带的ToUpper()函数,暂时想不到优化的方法

  二轮优化

  1、想到自己两个线程(Reader与Computer)都各自有一个BlockingCollection,浪费了内存;

  2、同时很容易想到作为一个词频统计的软件,主要耗时间的部分并非在读入,于是想到了增加线程来辅助处理Computer线程,先增加一个线程看看

  3、这时候就需要共享一个static dictionary<string,int>以及一个static BlockingCollection<string>,预测可以比双线程减少10%左右用时

  4、代码备份..大改

  5、调试时遇到问题:发生已添加了具有相同键的项的错误。由于共享同一个dictionary,插入时候需要互斥访问

  6、加了lock后发现耗时间多于原本双线程...考虑更换线程安全的ConcurrentDictionary。

  优化结果:4.4s比上轮结果优化了40%的时间,意料之中

  Individual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And Optimization

  可以看到最耗时间的依然是字符串处理部分,但是在多个Computer线程的帮助下,大大减少了时间

  三轮优化

  1、开时着手把Extended Mode的正则表达式优化为手写,用时40分钟

  2、发现修改后Extended Mode耗时增加..舍弃该方案

  3、继续增加线程数以及相应测试

  经过测验,对于约170M的文本,在一个线程负责读取文件内容,一个线程负责处理字符串和输出结果,两个线程负责处理协助字符串时可以达到相对优良的速度,就不丧心病狂的再加线程了…我觉得性能光看时间的话可是太片面了..

  优化结果:

  对于总量170M的各种文本文件

  Simple mode: 3.5s比双线程时候的8.5s优化了约60%

  Individual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And Optimization

  主要瓶颈是字符串处理部分(判断以及加入Dictionary的部分),但是由于啥自己写的,没有使用正则表达式,和Extended mode比起来简直快的一比…

  Extended mode "-e2":15.25s比双线程时候的21s优化了约30%

  Individual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And Optimization

  瓶颈时使用正则表达式实!在!是!太!慢!了!

Individual Project - Word frequency program - Multi Thread And Optimization

Extended mode "-e3":18s比双线程时候的24s优化了约25%

Individual Project - Word frequency program - Multi Thread And OptimizationIndividual Project - Word frequency program - Multi Thread And Optimization

瓶颈还是正则,不多说了…

  四轮优化(误)

  1、考虑优化dictionary,对于大文本的话,dictionary的索引过长可能会降低效率,考虑每个线程各自配备一个dictionary,最后统一merge并输出

  2、有这个想法的时候已经到了deadline,同时也无法保证正确性,同时也不想再把时间耗在这上边了,于是作罢权当攒人品...三轮优化结果就是我目前极限了

四、样例分享

  1. 文件套文件套到死最后是个空文件;程序正常运行

  2. 成片的空文本;程序正常运行
  3. 检验单词识别是否正确:文本内容"file123 123file er r u4y5 asd"输出结果:

    asd:1
    file123:1

  4. 检验单词排序以及插入时是否进行了字典序靠前替换操作:文本内容"File FILE file asd Asd ASD AsD"输出结果:

    ASD:4
    FILE:3

  5. 连续两个单词识别是否正确:文本内容"sjdiof ajasdk asdka sjdiof ajasdk asdka"

    输出结果:

    ajasdk asdka:2
    sjdiof ajasdk:2
    asdka sjdiof: 1

  6. 连续两个单词排序:文本内容

    "hello World
    hello world

    how are you
    how Are you
    How are you"

    输出结果:

    Are you:3
    How are:3
    hello World:2

  7. 连续三个单词:文本内容

    "

    how are you

    how Are you

    how OLD are you
    fine thank you and YOU
    fine Thank you And you
    fine thank YOU and yOu"

    输出结果:

    Thank you And: 3
    YOU and yOu: 3
    fine Thank you: 3
    how Are you: 2
    OLD are you: 1
    how OLD are: 1

  8. 分隔符的判断:文本内容"sgq&qwge#wet@wqe t$111sdfao sifj032ri23<>:<PL:LFTFTFkokpasfk.s;x:}{+hi}{;"

    输出结果:

    LFTFTFkokpasfk: 1
    qwge: 1
    sgq: 1
    sifj032ri23: 1
    wet: 1
    wqe: 1

  9. 对于".h", ".cs", ".cpp", ".txt"文件后缀的判断:文件加下包括各自不同后缀的文件包括.h,.H,.CS,.cs,.CPP,.TXT,.rmvb,.MKV,.c等等

    输出结果中只包含.h,.cs,.cpp,.txt之类的文件(case insensitive)

  10. 用大文本测试并进行优化

五、学习与收获

  1、程序不是很难,主要还是自己对C#不熟悉,还是太渣,总的来说对C#有了一个基本的了解,包括基本语法、文件处理、字符串处理、哈希表、多线程、以及正则表达式。

  2、多线程是坑,大坑

  3、性能测试时候别开迅雷,会占用cpu

  4、改程序前记得备份代码

  5、第一个C#程序居然不是"Hello World!"

  6、据说结对编程又是电梯调度,不知该说什么...

  7、vs卸不干净

  8、套话:综观这次作业,开始做之前,我以为它很简单,可实际上去实现时,发现并不是所想的那么容易,因为有很多的细节需要处理,处理不好就会一直卡在那,或者性能非常弱。通过这次作业,我学会了很多很多有用的知识。更重要的是,结识了vs2012的性能分析工具,发现它对我们来说是个非常有用的工具,如果能好好利用,相信将对我们的编程优化有很大的帮助!

上一篇:Individual Project - Word frequency program-11061171-MaoYu


下一篇:FragmentTransactionExtended