你的位置:首页 > ASP.net教程

[ASP.net教程]ListT线性查找和二分查找BinarySearch效率分析


今天因为要用到List的查找功能,所以写了一段测试代码,测试线性查找和二分查找的性能差距,以决定选择哪种查找方式。

线性查找:Contains,Find,IndexOf都是线性查找。

二分查找:BinarySearch,因为二分查找必须是对有序数组才有效,所以查找前要调用List的Sort方法。

结论:如果List项的个数比较小,用线性查找要略快于二分查找,项的个数越多二分算法优势越明显。可根据实际情况选用适合的查找方式。

测试结果:

测试代码:

    private void button1_Click(object sender, EventArgs e)    {            TestFind(10);      TestFind(30);      TestFind(70);      TestFind(100);      TestFind(300);      TestFind(1000);    }    private void TestFind(int aItemCount)    {      listBox1.Items.Add("测试:列表项个数:" + aItemCount + ",查询100万次");      int nTimes = 1000000;      int nMaxRange = 10000;   //随机数生成范围            Random ran = new Random();      List<int> test = new List<int>();      for (int i = 0; i < aItemCount; i++)      {        test.Add(ran.Next(nMaxRange));      }      int nHit = 0;      DateTime start = DateTime.Now;      for (int i = 0; i < nTimes; i++)      {        if (test.IndexOf(ran.Next(nMaxRange)) >= 0)        {          nHit++;        }      }      DateTime end = DateTime.Now;      TimeSpan span = end - start;      listBox1.Items.Add("一般查找用时:" + span.Milliseconds + "ms, 命中次数:" + nHit);      nHit = 0;      start = DateTime.Now;      test.Sort();      for (int i = 0; i < nTimes; i++)      {        if (test.BinarySearch(ran.Next(nMaxRange)) >= 0)        {          nHit++;        }      }      end = DateTime.Now;      span = end - start;      listBox1.Items.Add("二分查找用时:" + span.Milliseconds + "ms, 命中次数:" + nHit);      listBox1.Items.Add("");    }