时光匆匆，转眼间这个学期马上就要结束了，数据结构课程也很快就要结课了。
反观ld这个学期的表现：ld这个学期很懒，没有贡献出任何一份关于数据结构的教程，主要原因是课选多了（给ld的懒找台阶下）。不过ld写下了这篇大作业指引，希望可以帮助大家顺利完成DS大作业，以及完成的同学可以进行相关的优化和提速。
ld所在的北京学院级诞生了很多大作业竞速排名很靠前的同学，作为北京学院的DS助教，ld经常和同学交流大作业的完成思路。其实年的大作业和年的数据结构大作业要求很相似，不过要求确实是简单了一些，所以程序可以跑出很短的时间也是理所当然，去年Chenrt等佬跑进0.1都很费劲，今年几个同学扎在一起冲到了0.05s。
那么下面就来看看今年的DS大作业有哪些可以实现思路和优化方法吧！
一、大作业文字描述在自然语言文本处理中，有一种分析文本、自动抽取文本主题思想的方法（通常用于文本摘要生成），其方法如下：
首先分析文本中非停用词（stop-word）的出现频度；
统计文本中每个句子中非停用词频度之和。若某个非停用词在一个句子中出现多次，则都要计算；
按非停用词频度之和由高至低输出前N个句子。
注：
单词为仅由字母组成的字符序列。包含大写字母的单词应将大写字母转换为小写字母后进行词频统计。
句子是由下面符号分隔的段落：句号(.)、问号(?)和惊叹号(!)。
在自然语言处理中，停用词（stop-word）指的是文本分析时不会提供额外语义信息的词的列表，如英文单词a，an，he，you等就是停用词。
根据当前目录下停用词文件“stopwords.txt”，打开当前目录下文件“article.txt”，并从标准输入读入需要生成至文件的句子数N。按上面要求进行文本分析，抽取相关文本主题思想。
在标准输出上按频度之和由高至低输出前5个句子的频度之和与句子。输出时先输出句子的频度和，然后空一个空格再输出整个句子，每个句子最后有一个回车。同时按频度之和由高至低输出前N个句子的频度之和与句子输出到文件“results.txt”中，输出要求同标准输出。输出时，若两个句子频度和相同，则按原文本中出现次序输出。
说明：输出句子时，从第一个非空字符开始，句子中每个组成部分形态（包括单词中字母大小写、间隔）应与原文本中一致。
二、分析与实现从上面今年的题目可以概括，只给定停用词、一篇文章，要求是根据单词词频输出单句频度最大的前N个句子。
这里面我们可以拆分出来程序的各个步骤（不一定每一步都需要），主要包括：字符读入（文章和停用词），存储单词、句子等信息到定义的结构中，计算词频，计算句子频度，排序，筛选，输出结果。
定义好了各个步骤的处理，我们就可以自行设计每一个步骤了。从根上讲，不同的数据结构的选用和编写方式都有可能影响最后的完成或运行时间，所以选择符合要求操作的最低时间复杂度的结构是最合适的。
上面的话可能感觉没有道出什么，但实际这是数据结构有关的程序设计中最重要的一步，其余的代码编写以及Debug等本篇不再赘述，有问题的同学可以使用对拍、随机测试的方式验证自己的程序（有能力的同学可以在Linux上使用GDB进行调试）。
1.普通实现普通实现的定义为代码编写较为简单，结构设计也比较简单的一类实现方式，这一类的实现可以说是五花八门。如果你想要参加竞速，那么你肯定都有尝试过用不同的结构化方式进行程序的编写。
普通实现的方法大致有这些方式：基于暴力、基于二叉搜索等等。由于这样的完成方法有很多，可以优化的地方也实在是很多，所以我决定在下面的思路中进行说明。
这里给大家一个简单的实现思路：定义一个结构体S指代为每一个句子，每一个S里面包含了N个可能个数的单词，这样我们就定义好了这个Struct。这里面我们可能还需要添加一些属性：每一个S中配套存储一个句子的频度，每一个单词都需要额外的一个词频属性。这样我们的单词就可以存储进来了。
然后基于这种实现方式，后面的过程就会很简单了，只需要一步一步计算出定义好的属性即可，难度并不大（简单的暴力）。
但按照上述实现以后你会发现自己处在大作业排行榜的后面，那如何才能跻身前列呢？这就可能需要换一种思路完成代码了。
2.进阶实现进阶实现，意在突破普通实现的瓶颈，实现更快速的功能。到了这一类可能实现方法并没有那么多了，因为你会发现榜上有名的同学们可能都是差不多那几个思路。
进阶实现的方式大体可以分为两类：Hash、字典树。
如果使用Hash，即将单词进行散列，代码编写并不复杂，而需要研究的是如何设计你的哈希算法，以避免大规模的碰撞，以及可以学习一波经典的哈希函数（BKDR、SDBM、RS、JS、AP、DEK、FNV等等字符串哈希函数）。
如果使用字典树，即建立最多有26叉的多叉树进行存取，代码编写较为复杂些，但思路上较好思考。这种方法的优化可以到时间开销极小，但想要达到这个开销还是需要动动脑筋进行优化的。
三、针对性优化经历了上述这么多的实现方式，我相信你已经设计好了自己的实现方法。这里针对不同的程序步骤提出了一些可以让程序优化明显的方案，大家可以根据自己的程序实现方式进行各种优化（小心反优化）。
1.暴力暴力的方式比较爽，代码在复杂度方面可以优化的地方实在是有很多，比如：进行二叉搜索树的建立；所有的零散空间（堆中malloc申请的空间）实现全部改成数组实现；查找时使用二分查找等等。这些优化会让程序的速度一下子提高很多，可能是秒级。
2.二叉搜索二叉搜索树的构造已经比直接暴力时间开销上好了很多，但其实还可以优化，例如更改成平衡二叉树（AVL），红黑树等的结构，具体算法设计还请翻阅PPT等资料。
结构更改做好了之后，可以针对二叉树进行优化。例如更改掉DFS递归的写法、进行相关变量的维护（缓存），这些都做了之后在时间复杂度上可能不能再有特别明显的优化了。
3.Hash哈希的做法精髓在选取的哈希函数，这里推荐BKDR、SDBM等哈希算法（这个地方还是需要好好设计的，甚至可以通过测试对算法进行人为改进）。其余的由于Hash并不需要复杂的程序结构，所以也没有办法有更大的优化空间了。
4.字典树字典树要完成一个26叉树，这种树可能脑中第一闪现的就是使用指针实现。每当有一个新的单词读入时，相同部分过后就需要一个一个创建结点进行树的建立。由于指针实现，所以可以将后续是否有节点进行数组标记，这样查询时DFS也会少遍历到很多的空节点。
但上述的方法必然会用到malloc申请的堆空间，这会导致时间开销将大大提升，所以有一种数组方式实现26叉树的方式，这里给出一个二十六叉树插入函数的Demo：
思考：代码中的sz是一个全局变量，初始为0。代码段里面的valList是用来做什么的呢？
通过数组实现字典树，存取的时间复杂度被大大减小，你的程序可能就此起飞。
四、通用优化1.排序优化排序时由冒泡、插入、选择、快排等更改成堆排、归并、桶排等。在这里要好好说说桶排序，因为平常的程序用到桶排序的机会并不多，且又是O(n)的时间复杂度，很难不用到它时大说一声香。
通过情景思考以及一些随机书籍的大数据集测试，不难发现，其实单词的频率不太会很大，因此是可以使用桶排序的。桶排序的时候要注意一个问题，只有排序之前已经定义好了字典序之后才可以直接放入桶中，相同的词频下，需要让字典序排序靠前的在前面，所以如果使用散列序作为桶排序的输入，则需要添加特殊处理。
在字符串的词频桶排序中，桶可以被定义为一个二维平面空间，相同词频的单词会占据在同一个头地址的不同偏移位置上，其余的细节性的东西就需要大家自己来探索了，处理也不复杂~
2.IO优化IO即Input/Output，输入输出的优化在本程序中也相当的重要。输入的时候如果你使用fscanf、fgets、fgetc等等函数，你会需要使用一个buffer不断地读入写入，这样非常浪费时间。同学们要有一个常识，当调用函数的时候，函数会有一个状态保存和状态返回，所以一旦你调用了函数的时候，这些函数会存在在函数栈上，并在函数体运行完之后一遍遍恢复之前的状态。但类似于文件读入的操作，这样的来回保存状态的操作是没有必要的，况且调用了很多次与文件指针相关的操作，每一次使用的时候都会访问文件指针，这样时间就很不可控了（所以尽量使用已经存入内存的数据，这样可以更快的被处理器访问并处理）。
说了这么多，其实就是优化的时候可以定义一个总文章长度为L的字符串buffer，后使用fread函数一次性将文件内容全部载入到设置好的buffer。输出的时候也是一样，我们可以用fwrite代替fprintf等等函数，一次性写到文件指针指向的位置。
特殊说明：fread函数有种种限制，还会出现很多奇怪的现象，这里提醒大家载入的时候注意选择模式，可能用到“r”，“rb”等，程序离奇出错，很有可能是这里就开始错了。
3.其余优化下面还有一些有意思的、可能有效果的优化方案，可供大家参考：
①使用有限个registerint替换int。
②大小写转换，可以直接或上32，就可以达到大小写转换的目的。
③可以选择开启编译优化Ofast，可以使用#pragmaGCCoptimize("Ofast")加在程序之前。有兴趣的可以尝试搜索“40行加速代码”。
④更多地使用if-else而不是switch-case（利用分支预测）。
⑤更多的优化掉无关的变量使用，少占用内存（利用评测机访存原理，内存占用小的，更有可能被评测机评测时从内存中访问到，加快速度）。
⑥更多的优化掉实体拷贝、实体交换等等，类似的操作我们完全可以使用所在地址完成。一个大作业运行下来，我们可能算来算去改变的实体都是指针，最后输出的时候也完全可以只需要这些指针，因此我负责任的说，如果你在这个程序里用到了memcpy、strcpy等等函数，那么必然还有优化空间。
⑦（慎重）重复多的代码使用内联汇编。这个ld也没有尝试过，大家有兴趣可以尝试一下。
以上就是关于大作业优化的全部内容了，如果有任何问题，欢迎通过后台直接给ld留言。
谢谢大家支持，也希望能帮助到大家！祝大家暑假愉快~！
我们下一期再见~（会是什么内容呢，我自己也没想好hhh）
lxlrefuserolling