贝网博客

我的分类
流水记事
源码下载
Asp.net
其它
数据库
Javascript
.Net技术
我的相册
友情链接
博客园
CSDN博客
Start0
最新回复
嗷嗷的cCC
fasdfasdf
[:..
lz这个东西好厉害,我..
哈哈,好照片
不错,以前一直用黄色..
终于找到支持ff的修正..
终于找到支持ff的修正..
新鲜性
看看,试试,好不好使。
分类 =》.Net技术
C#中,List与SortedList的Contains方法,效率比较
发表于:2010-11-23 16:55:24
更新于:2012-06-07 11:30:45

重新书写一下结论,代码中,如果经常使用List的Contains方法,建议修改为使用Dictionary的ContainsKey来代替,也可以使用下文中的SortedList,但是如果有比较多的插入操作,则不建议使用SortedList,而还是使用Dictionary,因为SortedList是线性存储,在修改数据时效率很低;
如果需要数组进行排序,可以改用SortedDictionary,这个的效率,我的测试结果比Dictionary差一点点,可以忽略,但是它是链表存储,占用内存会比SortedList大

本文介绍了C#中的List与SortedList的Contains方法源码,并进行了效率比较,得出结果是SortedList的Contains效率较高,但是插入数据时效率较低

做了个项目,是抽取不重复的随机数,一开始的代码(删减版)是:
static List<int> ok = new List<int>();
public static int GetRandom(){
    int ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, 10000);
    while (ok.Contains(ret))
    {
        ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, 1000);
    }
    ok.Add(ret);
    return ret;
}

后来觉得数组大了后,效率较低,研究了一下List<T>.Contains方法,定义如下:
for(int i=0; i<_size; i++) {
    if (c.Equals(_items[i], item)) return true;
}
return false;
就是循环整个数组去查找,后来想了一下,如果用排序好的数组,会不会效率更高呢?
又研究了一下SortedList<T>.ContainsKey方法,它调用了Array.BinarySearch方法,BinarySearch方法MSDN说明:
    使用指定的 IComparer<(Of <(T>)>) 泛型接口,在一维排序 Array 的某个元素范围中搜索值。定义大致如下:
private static int BinarySearch(T[] array, int index, int length, T value)
{
  int num = index;
  int num2 = (index + length) - 1;
  while (num <= num2)
  {
    int num4;
    int num3 = num + ((num2 - num) >> 1);
    num4 = array[num3].CompareTo(value);
    if (num4 == 0)
    {
      return num3;
    }
    if (num4 < 0)
    {
      num = num3 + 1;
    }
    else
    {
      num2 = num3 - 1;
    }
  }
  return ~num;
}
可以看出来是使用二分法查找,只是在Add的时候也要找到相应元素位置去Insert

通过几次大数据量的测试,在List.Add List.Contains 和 SortedList.Add SortedList.ContainsKey方法对比中,后者胜出,于是我的代码就改成了:
static SortedList<int, int> ok = new SortedList<int, int>();
public static int GetRandom(){
    int ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, 1000);
    while (ok.ContainsKey(ret))
    {
        ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, 1000);
    }
    ok.Add(ret, 1);
    return ret;
}

今天发现还有个SortedDictionary,汗,这个玩意的效率更高,测试代码如下,在下面的代码中SortedDictionary的时间都没超过100ms:
static void Main(string[] args)
{
    int time = 10000;
    Stopwatch w = new Stopwatch();
    for (var j = 0; j < 20; j++)
    {
        w.Reset();
        w.Start();
        for (int i = 0; i < time; i++)
            GetRandom2();
        w.Stop();
        Console.WriteLine("SortedDictionary耗时" + w.ElapsedMilliseconds);
        w.Reset();
        w.Start();
        for (int i = 0; i < time; i++)
            GetRandom();
        w.Stop();
        Console.WriteLine("SortedList耗时" + w.ElapsedMilliseconds);
        w.Reset();
        w.Start();
        for (int i = 0; i < time; i++)
            GetRandom3();
        w.Stop();
        Console.WriteLine("List耗时" + w.ElapsedMilliseconds);
    }
    Console.ReadLine();
}

private static int rndMax = int.MaxValue;
static SortedList<int, int> ok = new SortedList<int, int>();
public static void GetRandom()
{
    int ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, rndMax);
    while (ok.ContainsKey(ret))
        ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, rndMax);
    ok.Add(ret, 1);
}

static SortedDictionary<int, int> ok2 = new SortedDictionary<int, int>();
public static void GetRandom2()
{
    int ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, rndMax);
    while (ok2.ContainsKey(ret))
        ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, rndMax);
    ok2.Add(ret, 1);
}
static List<int> ok3 = new List<int>();
public static void GetRandom3()
{
    int ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, rndMax);
    while (ok3.Contains(ret))
        ret = new Random(Guid.NewGuid().GetHashCode()).Next(1, rndMax);
    ok3.Add(ret);
}

评论列表(7条)
by: 阿斯顿飞
2011-06-21 12:28:41
by: 阿斯顿飞
2011-06-21 12:30:13
by: 阿斯顿飞
2011-06-21 12:30:29
by: 阿斯顿飞
2011-06-21 12:30:45
by: 阿斯顿飞
2011-06-21 12:31:11
by: 阿森
2011-07-06 09:37:23
受教了!
by: 444
2011-07-09 22:40:48
<script>alert('test')</script> <h1>test 习惯</h1>
发表评论
名称(*):
邮箱:
正文:

©2008 Beinet.cn 版权所有