词频统计 List Array

c# 使用数组进行词频统计

1.先考虑要是使用的数据结构:

Array在在内存中是连续存储的,所以它的索引速度非常快,而且赋值与修改元素也很简单,但是数组存在一些不足的地方。在数组的两个数据间插入数据是很麻烦的,而且在声明数组的时候必须指定数组的长度,数组的长度过长,会造成内存浪费,过段会造成数据溢出的错误。如果在声明数组时我们不清楚数组的长度,就会变得很麻烦。

ArrayList对象的大小是按照其中存储的数据来动态扩充与收缩的。所以,在声明ArrayList对象时并不需要指定它的长度。但是ArrayList会把所有插入其中的数据当作为object类型来处理,在我们使用ArrayList处理数据时,很可能会报类型不匹配的错误,也就是ArrayList不是类型安全的。在存储或检索值类型时通常发生装箱和取消装箱操作,带来很大的性能耗损。

List<T>类是 ArrayList 类的泛型等效类。该类使用大小可按需动态增加的数组实现 IList<T> 泛型接口。不会强行对值类型进行装箱和拆箱,或对引用类型进行向下强制类型转换,是类型安全的。

2.Array 进行词频统计

要使用Array进行词频统计就需要提前规定一个大小够用的数组,确保不会越界。使用二维数组,一维存储单词另一维存放单词出现次数。

每次查询单词是否在数组(单词维度)中存在,若存在则获取到在数组中的位置下标,根据下标更新对应的单词出现次数。若存在将单词写入数组,次数为1。

效能分析结果图:

词频统计 List Array

程序运行总时间16s

词频统计 List Array词频统计 List Array

占用最多的函数项ArrayContains() 该函数用于判定单词是否已存在数组之中,若存在返回1及下标,若不存在返回0及数组为空的位置以便继续写入。

数组的赋值和修改都很简单,查找占用较多。

2.List<> 进行词频统计

使用List<T>来进行词频统计。定义类 Item包含下面两个属性
        private int total;//单词出现次数
        private string word;//单词

List<Item>无需设定长度,每次查询单词是否存在,若存在则获取到在List中位置,删除对应位置的数据Item,若不存在将单词写入,次数记为1.

效能分析结果图:

词频统计 List Array

程序运行总时间130s

词频统计 List Array词频统计 List Array

占用最多的函数项 IsExAndgetIndexAndValue(List<Item> itemList, string word)

该函数用于判定单词是否已存在List之中,若存在返回1、位置(index)及单词出现出次数(value)组成的int数组,若不存在返回0、0 、0组成的数组

根据是否存在确定下一步要进行的操作:①存在:删除对应位置Item,将新Item(word,value+1)写入

②不存在:写入Item(word,1)

3.HashTable 词频统计(博客:http://www.cnblogs.com/WeSure6/p/5257024.html

效能分析结果(博客:http://www.cnblogs.com/WeSure6/p/5275715.html

效能分析(代码部分调整:将一些功能写成独立函数)

词频统计 List Array

程序运行总时间 3s

词频统计 List Array词频统计 List Array

占用百分比较高的部分是对标点符号的替换(TxtToWords()函数部分)

词频统计 List Array

其余为判断单词是否存在于HashTable中

词频统计 List Array

4.总结

就程序运行总时间看,使用HashTable的程序运行时间最短只有3s,使用二维数组稍长16s,而使用List<T>最长130S(严重超出预期,有待思考,还未想明缘由)

CPU使用情况上,使用HashTable的程序优于使用二维数组优于List<>

*以上结论依据个人程序

上一篇:[TJOI2017]可乐


下一篇:【Dart学习】-- Dart之匿名方法 & 回调函数 & 闭包