汕头seo网站排名,手机网页版浏览器,长春一大网站,佛山 做网站公司有哪些第一次个人作业——词频统计 第一次做这种大作业#xff0c;明显感觉陌生#xff0c;各种规范和技能也是第一次使用#xff0c;希望自己好运。 目录#xff1a;一、基本要求 二、需求分析及时间估计 三、实现思路及过程 四、测试用例、时间性能分析及改进方法 五、经验总结…第一次个人作业——词频统计 第一次做这种大作业明显感觉陌生各种规范和技能也是第一次使用希望自己好运。 目录一、基本要求 二、需求分析及时间估计 三、实现思路及过程 四、测试用例、时间性能分析及改进方法 五、经验总结 一、基本要求 1. 统计文件的字符数只需要统计Ascii码汉字不用考虑换行符不用考虑,\0不用考虑ascii码大小在[32,126]之间 2. 统计文件的单词总数 3. 统计文件的总行数任何字符构成的行都需要统计不要只看换行符的数量要小心最后一行没有换行符的情形空行算一行 4. 统计文件中各单词的出现次数输出频率最高的10个。 5. 对给定文件夹及其递归子文件夹下的所有文件进行统计 6. 统计两个单词词组在一起的频率输出频率最高的前10个。 7. 在Linux系统下进行性能分析过程写到blog中附加题 注意 a) 空格水平制表符换行符均算字符 b) 单词的定义至少以4个英文字母开头跟上字母数字符号单词以分隔符分割不区分大小写。 分割符空格非字母数字符号 例如”file123”是一个单词”123file”不是一个单词。fileFile和FILE是同一个单词。 如果两个单词只有最后的数字结尾不同则认为是同一个单词例如windowswindows95和windows7是同一个单词 输出按字典顺序例如windows95windows98和windows2000同时出现时输出windows2000 c)词组的定义windows95 good windows2000 good123可以算是同一种词组。按照词典顺序输出。 两个合法单词之间出现一个非法字符串比如windows2000 abc good123因为abc按照定义不是单词因此这个词组其实是windows2000 good123中间的abc当做分隔符看待。 两个单词分属两行也可以直接组成一个词组。统计词组只看顺序上是否相邻。 d) 输入文件名以命令行参数传入。需要遍历整个文件夹时则要输入文件夹的路径。 e) 输出文件result.txt characters: number words: number lines: number word: number word为文件中真实出现的单词大小写格式例如如果文件中只出现了File和file程序不应当输出FILE且word按字典顺序基于ASCII排列上例中程序应该输出File: 2 f) 根据命令行参数判断是否为目录 g) 将所有文件中的词汇进行统计最终只输出一个整体的词频统计结果。 二、需求分析及时间估计 1.统计字符总数及行数 2.甄别单词并予以统计 3.甄别词组并予以统计 4.根据频率对单词、词组各自排序 5.实现对文件夹及子文件夹的遍历 PSP表格 由表可看出大部分阶段都是超时完成的亟需改进整体来看效率也比较低。 三、实现思路及过程 *结构体定义 1.统计字符总数及行数 这个就是遍历一下文件遇到ascii值在32~126之间的就计数行数统计则是统计换行符的个数针对最后一个字符表示换行符的文件额外再加一即可。 2.甄别单词并予以统计 从文件第一个字符开始或者从某一分隔符开始若检测到字母则开始借助flag标志辨别单词当连续字母达到四个时说明找到单词之后继续扫描并依次写入临时数组直到遇见分隔符如果在连续遇到1~3个字母后被打断则用标志mark判断若被数字打断则当前字符串作废继续扫描直到遇见分隔符然后开始下一次单词甄别如果是被分隔符打断则可以直接开始寻找下一个单词。注意最后退出的时候要判断一下当前字符串是否为单词。 统计部分则是在上述代码中增设一个临时数组b实时存储字符串当字符串无效时清空该数组直到其为一个合法的单词此时将其插入哈希表通过单词首字母确定52个元素按自然顺序1~52构造其哈希地址用常数52定址解决冲突若遇到等价的单词则判断字典顺序决定是否覆盖若没有则新占一个槽。下面是哈希部分的代码 3.甄别数组并予以统计 这部分我没什么好的思路基本就是每次成功甄别到一个单词就用临时数组temp记录它当下一个单词找到时就把temp和b代入哈希函数去寻址以temp首字母为自变量哈希表构造与操作同上。套路与单词统计基本一致代码不再展示。 4.根据频率对单词、词组各自排序 由于只需要输出频率最高的10个单词及10个词组堆排序是最好的方式。 数组a按序包含了所有单词在word结构体数组也就是哈希表中的下标。算法是以单词频率为排序依据对每个单词在word数组中的下标进行排序当已经排好前十个时停止排序并打印结果。对词组的排序与之相同不再赘述。 5.实现对文件夹及子文件夹的遍历 查阅资料之后得知可以用句柄递归遍历文件夹从而获取当前文件夹里所有文件的路径然后处理一下将路径中的‘ \ ’换成 ‘ / ’即可被fopen调用来打开文件了。 getFiles函数用于获取当前文件夹下所有文件的路径。 完整的源代码地址https://github.com/ustcychu/HW1_PB16060445.git 四、测试用例及时间性能分析 1.第一次调试用了个555k的文件夹然后用了7.688秒orz所以就靠优化工作了。 主函数中的热行当然在于调用分析函数statistics。 statistics函数中的热行在于两次构造哈希表查找空槽和判断是否等价的过程而且词组部分的耗时明显高于单词部分。 所以首先该分析的是JudgeWordEqual函数。其大致工作流程是判断俩字符串长度大小关系然后从后往前扫描如果最后一段数字之前如果有的话的部分等价就判定俩单词等价然再从头遍历判断二者字典顺序并予以覆盖方便后续操作。 分析结果显示大部分判断长度大小关系的结果都是二者相等所以应放在第一个判断从句用strlen取字符串长度耗时较多上述两次遍历时间太长。 因此决定先针对性优化效果不好就尝试别的方法。经过改进时间缩至6.56秒。 接着我又重写了一种方法 从两个字符串末尾开始扫描直到非数字的字符将这之前的字符串片段取出进行不区分字母大小写的比较stricmp若匹配则说明俩字符串等价然后用strcmp判断二者字典顺序选择是否进行覆盖方便之后的操作。 似乎有了进步—5.01秒但好像也不是特别好qaq。 再在lb--后面加上判断la与lb是否相等的判断以避免不必要的运算—时间缩至4.833秒。 之后再经过分析认为可能是哈希函数的问题于是作了修改主要就是扩大哈希函数的值域以减少搜索 对应的查找与插入 事实上哈希函数如果给自变量加权的话可能效果更好还有散列函数还可以选择二次探测法和拉链法有时间的话再写一份拉链法的毕竟指针操作快很多 可惜开始没有想到出于时间限制没有继续写下去了。 此次修改之后对应时间缩至1.633秒(还是有了一点点效果)。 2.测试空文件 按要求空文件也记行 虽然不知道为啥要记... 3.测试只有一个单词的文件 4.测试只有一行的文件hhhh a1hhh hhhh lalalala 5.其他测试集 ( 优化前 A.27k0.018s B.32k0.024s C.1M, 5.243秒 6.其他测试集优化后 A.(1.2M, 2.56秒) B.5.2M3.791秒 C.(21M, 11.143秒) 附时间性能分析 可以看出代码的热行没有改变改动的两个地方JudgeWordEqual和哈希函数的时间性能好了很多。 很明显可优化的地方还很多今后继续学习逐渐进步。 ***标准测试集177M21min*** 五、经验总结 通过本次实验回顾了不少编程知识也在看书浏览博客的过程中收获了很多技能与之前的编程经历相比进步在于编程增加模块功能时结构更清晰、语句整理更熟练、细节bug明显减少但在代码运行效率方面还有很大的进步空间首先需要学习更多更高级的语言和工具目前也是在进行中为团队项目做准备其次是在编程算法上有待锻炼目前感觉还是太老套需要更多的阅读积累。希望通过本学期的学习能够很好地提升自己的软件编程能力为今后做好准备。 转载于:https://www.cnblogs.com/notegeek/p/8654847.html
