List<T>线性查找和二分查找BinarySearch效率分析

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

线性查找：Contains，Find，IndexOf都是线性查找。

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

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

测试结果：

测试代码：

        private void button1_Click(object sender, EventArgs e)

        {

            TestFind();

            TestFind();

            TestFind();

            TestFind();

            TestFind();

            TestFind();

        }

        private void TestFind(int aItemCount)

        {

            listBox1.Items.Add("测试：列表项个数:" + aItemCount + ",查询100万次");

            int nTimes = ;

            int nMaxRange = ;      //随机数生成范围

            Random ran = new Random();

            List<int> test = new List<int>();

            for (int i = ; i < aItemCount; i++)

            {

                test.Add(ran.Next(nMaxRange));

            }

            int nHit = ;

            DateTime start = DateTime.Now;

            for (int i = ; i < nTimes; i++)

            {

                if (test.IndexOf(ran.Next(nMaxRange)) >= )

                {

                    nHit++;

                }

            }

            DateTime end = DateTime.Now;

            TimeSpan span = end - start;

            listBox1.Items.Add("一般查找用时：" + span.Milliseconds + "ms， 命中次数：" + nHit);

            nHit = ;

            start = DateTime.Now;

            test.Sort();

            for (int i = ; i < nTimes; i++)

            {

                if (test.BinarySearch(ran.Next(nMaxRange)) >= )

                {

                    nHit++;

                }

            }

            end = DateTime.Now;

            span = end - start;

            listBox1.Items.Add("二分查找用时：" + span.Milliseconds + "ms， 命中次数：" + nHit);

            listBox1.Items.Add("");

        }

巴特西

List<T>线性查找和二分查找BinarySearch效率分析

最新文章

热门文章