在之前的3个版本里，我们已经实现了分词的基本功能，并对其合理性等作了大量的测试评估工作，但是性能的提升还很不如意，所以这里我提出了使用SortedList提高分词效率的方案。
C#中提供了众多集合类的数据结构，如大家常用的List
一、SortedList简介
引自MSDN：
SortedList 元素可通过其键来访问 （如任意 IDictionary 实现中的元素），或通过其索引来访问（如任意 IList 实现中的元素）。 SortedList 在内部维护两个数组以存储列表中的元素；即，一个数组用于键，另一个数组用于相关联的值。每个元素都是一个可作为 DictionaryEntry 对象进行访问的键/值对，
键不能为空引用（在 Visual Basic 中为 Nothing），但值可以。
SortedList 的容量是 SortedList 可以保存的元素数。SortedList 的默认初始容量为 0。随着元素添加到 SortedList 中，在需要时可以通过重新分配自动增加容量。可通过调用
TrimToSize 或通过显式设置 Capacity 属性减少容量。 SortedList 的元素将按照特定的 IComparer 实现（在创建 SortedList 时指定）或按照键本身提供的 IComparable 实现并依据键来进行排序。不论在哪种情况下，
SortedList 都不允许重复键。 索引顺序基于排序顺序。当添加元素时，元素将按正确的排序顺序插入 SortedList，同时索引会相应地进行调整。当移除元素时，索引也会相应地进行调整
。因此，当在SortedList 中添加或移除元素时，特定键/值对的索引可能会更改。
由于要进行排序，所以在 SortedList 上操作比在 Hashtable 上操作要慢。但是，SortedList 允许通过相关联键或通过索引对值进行访问，可提供更大的灵活性。
可使用一个整数索引访问此集合中的元素。此集合中的索引从零开始。 C# 语言中的 foreach 语句（在 Visual Basic 中为 for each）需要集合中每个元素的类型。
由于 SortedList 的每个元素都是一个键/值对，因此元素类型既不是键的类型，也不是值的类型。而是 DictionaryEntry 类型。
二、SortedList介绍——个人整理
我们知道对于List
SortedList保存数据时和哈希表一样用Key-Value的方式进行存储，但不同的是，它把Key和Value分别保存在两个object[]数组中，每次插入删除操作都会保持这两个object[]大小的同步性。
SortedList在初始化时如果不指定大小，则会给一个默认的十六进制值0x10（16），在添加操作中，如果容量不足则会自动扩充为2倍容量，这些与ArrayList和Hashtable相同。
SortedList的独特之处在于它保证数据的有序性，这点是如何保证呢？
原来，在Add（key，value）方法中，SortedList会首先用二分查找插入的key值，如果有重复项，则报错，如果没有重复项，则根据key值大小，比较得出在集合中的位置，然后插入到该位置中，反编译查看源代码如下：
1 public void Add(TKey key, TValue value) 2 { 3 if (key == null) 4 { 5 System.ThrowHelper.ThrowArgumentNullException(System.Exceptio 6 nArgument.key); 7 }//二分查找 8 int num = Array.BinarySearch
由于要进行排序，所以在 SortedList 上操作比在 Hashtable 上操作要慢。
但是，SortedList 允许通过相关联键或通过索引对值进行访问，可提供更大的灵活性，因为SortedList 兼容了 Hashtable 和 Array 的特征，当使用 Item 索引器属性按照元素的键访问元素时，其行为类似于 Hashtable，当使用 GetByIndex 或 SetByIndex 按照元素的索引访问元素时，其行为又类似于 Array。所以对于Hashtable来说，用object型的Key值来匹配，而对于ArrayList来说，则用int型的下标序号来获取，而SortedList由于兼有二者的特征，所以既可以用object型的key获取，也可以用int型的序号来获取，从而提高了数据访问的灵活性。
示例如下：
1 public static void Main() 2 { 3 ArrayList arrList = new ArrayList(); 4 arrList.Add("rocky"); 5 Console.WriteLine(arrList[0]); 6 7 Hashtable ht = new Hashtable(); 8 ht.Add("name", "rocky"); 9 Console.WriteLine(hash["name"]); 10 11 SortedList sortedList = new SortedList(); 12 sortedList.Add("name", "rocky"); 13 sortedList.Add("hobby", "coding"); 14 Console.WriteLine(sortedList["name"]); 15 Console.WriteLine(sortedList.GetByIndex(1)); 16 }
此外，SortedList还有泛型版本：SortedList
总结：
优点： 1、SortedList在添加元素时保证了集合中数据的有序性，并通过二分查找，显著提高了元素的查找效率。
2、SortedList兼容了ArrayList和Hashtable的数据访问方式，提高了数据访问的灵活性。
缺点： SortedList为了保证数据的有序性，所以构建时间较为耗时。
三、SortedList
首先，相对于第三个版本来说，这里将List
SortedList
随后调用_dict的Add方法进行词典构造即可。
四、SortedList
其实，说了上面一大通，就是为了看选择SortedList这样的数据结构后能不能使分词性能得到显著的提升，还记得之前对1000字左右的文本进行分词，时间大概在8、9秒的样子，那下面就看一下SortedList的表现。
下面是之前的测试文本：
下面进行分词：
简直毫无压力。随后来点狠的，直接上之前2.0版中提到的完整的测试文本，看下分词效果：
依然毫无压力，可以看到每1000字的分词效率从之前的8、9秒一下提到了100毫秒左右，可以说是质的飞跃，也可以很好地看到SortedList在数据查找方面的优势。
下篇将使用上面提到的另一种数据结构——Hashtable进行测试。
系列索引：基于.NET的分词软件设计与实现索引
作者：Rocky翔 出处：http://www.cnblogs.com/RockyMyx/ 本文版权归作者和博客园共有，欢迎转载，但请在文章明显位置给出原文连接，否则保留追究法律责任的权利。
最新评论