最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
C#中Lookup类和有序字典详解
时间:2022-06-25 08:07:08 编辑:袖梨 来源:一聚教程网
Lookup类介绍
Dictionary
Lookup
属性名或者方法名
说明
Count
属性Count返回集合中的元素个数
Item
使用索引器可以根据键访问特定的元素.因为同一个键可以对应多个值,所以这个属性返回所有值的枚举
Contain()
方法Contains()根据使用用Key参数传送元素,返回一个布尔值
ApplyResultSelector()
ApplyResultSelector(0根据传送给它的转换函数,转换每一项,返回一个集合
Loopup
当一个Key要求对应多个value情况ToLookup方法非常有用,ToLookup返回一种特殊的数据结构,类似SQL中的group,可以把集合分组并且可以用索引访问这些元素,案例:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Lookup类 { class Program { static void Main(string[] args) { //创建一个string类型的数组 string[] array = { "cat","dog","horse"}; //生成查找结构 var lookup = array.ToLookup(item => item.Length); //枚举字符长度3的串 foreach (var item in lookup[3]) { Console.WriteLine("3 = "+item); } //枚举字符长度5的串 foreach (var item in lookup[5]) { Console.WriteLine("5 = " + item); } //枚举分组 foreach (var grouping in lookup) { Console.WriteLine("Grouping : "); foreach (var item in grouping) { Console.WriteLine(item); } } Console.ReadKey(); } } }
上面的案例是通过数组元素的字符串长度为Key分组,也就是字符长度相同的元素的Key是一样的,索引下标也是一样.比如以通过lookup[3]访问,而horse要用lookup[5]来访问.
有序字典
SortedDictionary
SortedDictionary
1.SortedList
2.SortedDictionary
3.在用已排好序的数据填充集合时,若不需要修改容量,SortedList
案例:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 有序字典 { class Program { static void Main(string[] args) { //SortedList使用的内存少 //SortedDictionary 元素插入和删除速度快 //键要实现IComparable 接口 SortedDictionary sd = new SortedDictionary (); sd.Add(new EmployeeID(3),new Person("中国", "张飞", 40)); sd.Add(new EmployeeID(20), new Person("中国", "关羽", 43)); sd.Add(new EmployeeID(4), new Person("中国", "刘备", 45)); sd.Add(new EmployeeID(5), new Person("中国", "诸葛亮", 24)); sd.Add(new EmployeeID(1), new Person("美国", "豪威尔", 40)); sd.Add(new EmployeeID(0),new Person("美国", "奥巴马", 40)); sd.Add(new EmployeeID(210), new Person("朝鲜", "金三胖", 40)); sd.Add(new EmployeeID(80), new Person("印度", "印度阿三", 40)); foreach (var item in sd) { Console.WriteLine(item.Key.ID+","+item.Value.Name);//键,正序排序 } Console.ReadKey(); } } public class EmployeeID : IComparable { public int ID { get; private set; } public EmployeeID(int id) { this.ID = id; } public int CompareTo(EmployeeID other) { return ID.CompareTo(other.ID); } } public class Person { public string Country { get; private set; } public string Name { get; private set; } public int Age { get; private set; } public Person(string country, string name, int age) { this.Country = country; this.Name = name; this.Age = age; } } }
注意:SortedList类使用的内存比SortedDictionary类少,但SortedDictionary类在插入和删除未排序的数据时比较快.
详细分析SOrtedList和SortedDictionary类的不同,SortedList内部用数组保存,只能算是有序线性表,而SortedSictionary的内部结构是红黑树(这是一种数据结构,不懂得自己去百度).
SortedDictionary内部结构是红黑树,红黑树的平衡二叉树的一种,SortedList是有序线性表,内部结构是Array,运用了二分查找法提高效率.从两者查找,插入,删除操作的时间复杂度来看,都为O(LogN),分辨不出优劣,但内部结构的不同导致了实际操作的性能差异.
SortedList和SortedDictionary性能比较----插入
由于SortedList用数组保存,每次进行插入操作时,首先用二分查找发找到相应的位置,得到位置以后,SortedList会把该位置以后的值依次往后移动一个位置,空出当前位,再把值插入,这个过程用到了Array.Copy方法,而调用该方法是比较损耗性能的,代码如下:
private void Insert(int index,TKey key,TValue value) { ... if(index
SortedDictionary在添加操作时,只会根据红黑树的特性,旋转节点,保持平衡,并没有对Array.Copy的调用.
测试代码:循环一个int型,容量为100000的随机数组,分别用SortedList和SortedDictionary添加.
结论:在大量添加操作的情况下,SortedDictionary性能优于DortedList.
SortedList和SortedDictionary性能比较----查询
两者的查询操作中,事件复杂度都为O(LogN),且源码中也没有额外的操作造成性能损失.
经过测试得出:两者在循环10W次的情况下,仅仅相差几十毫秒,可以看出两者的查询操作性能相差不大.
SortedList和SortedDictionary性能比较----删除
从添加操作的案例可以看出,由于SortedList内部使用数组进行存储数据,而数组本身的局限性使得SortedList大部分的添加操作都要滴啊用Array.Copy方法,从而导致了性能的损失,这种情况同样存在于删除操作中.所以得出了:在大量删除操作的情况下是,SortedDictionary的性能优于SortedList.
总结:SortedDictionary内部用红黑树存储数据,SortedList用数组存储数据,两者的查询效率差不多,但由于数组本身的限制,在大量添加删除操作的情况下,SortedDictionary的性能优于SortedList.相关文章