c# Dictionary与List速度对比

最近在做的一个项目,数据量有些大,我们计划着将经常要用的一些数据进行缓存,开始计划使用Redis,由于没有Linux测试机,所以就采用MemCache(当然这只是一个不算原因的原因,还有其他很多因素,主要存什么类型数据、重要吗?等..)


然后,一个下午开了一个会。这个项目的负责的**领导,听说以前是技术..
他就提问了:你们说MemCache存储数据的形式是key-value,为什么不用dictionary?它也是key-value


具体后面怎么解释的,这里说不清...
然后,我也好好看了看dictionary泛型类。


概念:
Dictionary 泛型类提供了从一组键到一组值的映射。字典中的每个添加项都由一个值及其相关联的键组成。通过键来检索值的速度是非常快的,接近于 O(1),这是因为 Dictionary 类是作为一个哈希表来实现的。在C#中,Dictionary提供快速的基于键值的元素查找。当你有很多元素的时候可以使用它。他需要引用的命名空间是:System.Collection.Generic


将dictionary与memecache对比,没有实质的意义。

在网上看到一个测试dictionary与list速度的例子,自己运行了一下,结果吻合。


using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
using System.Threading.Tasks;  
using System.Diagnostics;  
namespace dictionaryDemo  
{  
    class Program  
    {  
        static void Main(string[] args)  
        {  
  
  
            Dictionary<int, string> dic = new Dictionary<int, string>();  
            for (int i = 0; i < 10000000; i++)   
            {  
                string a = "v" + i;  
                dic.Add(i, a);  
            }  
  
            Stopwatch stopwatch1 = new Stopwatch();  
            stopwatch1.Start(); //  开始监视代码运行时间  
            foreach (KeyValuePair<int, string> item in dic)  
            {  
                if (item.Key==5000000)  
                {  
                    Console.WriteLine(dic[5000000]);  
                }  
                  
            }  
            stopwatch1.Stop(); //  停止监视  
  
            List<string> studentinfo = new List<string>();  
            //studentModel student=new studentModel();  
            for (int i = 0; i < 10000000; i++)  
            {  
                string b = "b"+i;  
                studentinfo.Add(b);  
            }  
              
            Stopwatch stopwatch2 = new Stopwatch();  
            stopwatch2.Start(); //  开始监视代码运行时间  
            foreach (string item in studentinfo)  
            {  
                if (item=="b5000000")  
                {  
                    Console.WriteLine(studentinfo[5000000]);   
                }  
                  
            }  
            stopwatch2.Stop(); //  停止监视  
  
              
  
            Console.WriteLine("dictionary查找用时{0}:",stopwatch1.Elapsed );  
            Console.WriteLine("      list查找用时{0}:",stopwatch2.Elapsed);  
            Console.ReadLine();  
  
  
  
        }  
  
  
    }  
}  

list与dictionary对比
结论:

不是任何时候dictionary都是最快的,我们知道list是以线性表的形式存储的,通过前驱结点和后续节点,找到这个位置,在内存中是连续的区域,而dictionary在内存中是不连续的,所以在查找的时候会产生大量的内存换页操作,而list需要进行最少的内存换页即可,所以直接查找的时候,list效率明显比dictionary要高


什么是线性表的形式存储?


其实线性表的存储方式又有两种:顺序、链接
1、顺序存储
优点:
在结点等长时可以随机存取
存储密度高节省存储空间
用结点的物理次序反映结点之间的逻辑关系
缺点:
插入和删除结点时要移动大量的结点
必须静态分配连续空间

2、链接存储
优点:
插入和删除比较灵活,不需要大量移动结点
动态分配空间比较灵活,不需要预先申请最大的连续空间
缺点:
增加指针的空间开销
检索必须沿链进行,不能随机存取

标签: ditionary, list

添加新评论