Project: Individual Project - Word frequency program----11061192zmx

时间:2023-03-08 19:35:13
Project:  Individual Project - Word frequency program----11061192zmx

Description & Requirements

http://www.cnblogs.com/jiel/p/3311400.html

项目时间估计

  理解项目要求:      1小时

  构建项目逻辑:      1小时

  查阅相关资料:      1小时

  编写&调试程序:      2小时

  样例测试&功能完善:    1小时

  项目效率分析:      1小时

  项目优化:        2小时

  总结&提交:        1小时

项目实际完成时间

  实际完成时间很是蛋疼,题目意思不难理解,实现起来也不难,本着先实现功能不考虑时间的原则写了用c++里的map实现了一下,但发现debug模式下那个速度简直不能看,但这时已经离截止日期很近了,又有些错误,这两天花在改代码测数据上的时间很多。。。主要是数据如果不大没有代表性,如果大了的话又不好调试,很是蛋疼。。。

  写代码:n小时

  调试:   n小时

  测试数据按照我对题目的理解应该是能输出正确结果的,在release模式下100+M的小说大约用了30s左右,相对于薛大神的12s还是8s简直就是奇慢无比,详细的性能分析写在后面。

开发过程

  开发过程其实不能算充满艰辛,但做无用功的时间太多了。一开始先花了好多时间翻了翻C++Primer看了看容器什么,然后没看清楚题意没有递归遍历文件,最后功能实现后再把递归遍历部分加进去导致代码很乱,接着就是一些不知道从哪里冒出来的问题(运行时间过慢等,估计是我不小心点到了debug模式然后没有发现),因为这已经花了很多时间了,实在是不耐烦了,就直接重写了一遍代码,算是一个阶段完成了。但后来和小伙伴们对数据的时候竟然发现对题意理解错了,最后改了一下觉得应该没问题了。。。总之整个过程充满了艰辛,实在是无力了。。

  关于算法实现,我是用一个word_list来存储单词,用word_com来存储单词统一的形式(如file和File我在word_com里都存成FILE)。最后根据word_com里的频率将word_list里的单词排个序,将每个单词的最小字典序的形式提出来,这时单词的顺序不是按照题目要求的字典序的,而是按照真正字典里的顺序,这里再对其进行一次字典序的排序,输出结果。

性能分析

由于是直接用map做的,觉得map的insert操作应该比下标创建要快一点,于是在加单词的时候还加了hash。。其实应该是没什么区别的(只是优化了复杂度的常数,最后性能分析结果也显示没优化多少。。。)

可以看到,100+M的数据跑了30s,而且中间cpu使用率的曲线也很诡异。。

Project:  Individual Project - Word frequency program----11061192zmx

占有样本数比较多的函数是pass,这是用来遍历文件夹的,里面调用了addword是向map里面加单词记录频率的。

Project:  Individual Project - Word frequency program----11061192zmx

Project:  Individual Project - Word frequency program----11061192zmx

总结

  真的是学到了很多,主要是调试方面提高了许多心理承受能力。

  由于看了几遍c++primer里容器的介绍,对c++里各种容器也算有了个详细的了解,方便以后使用。

  学会了如何遍历文件夹,以及对一些函数的运行速度有了更深的了解。

  总的来说是一次很不错的实践。完