关于List和LinkedList的小测试

最近接触到了一个关于大集合定期轮询扫描的功能,因为大集合的遍历和判断可能会消耗比较多的时间和CPU资源,于是我准备根据.Net平台GC设计的代龄理念搞一个GenerationScaner.当然,不论它是否真的有效,这只是个计划.计划大概是这样的.

类中根据每个item的紧急情况(如某Item快要过期,我要发一条短信通知用户)分成3个集合,这3个集合会以不同的频率定期扫描集合内所有的item并且重新排列.第三代龄里总有些item因为时间的流逝(或其他原因)而进入第二代龄,再进入第一代龄.就像盛满水的三个不同高度的碗,最上面那个装满了就会将水流到下面一个,再到最后一个碗.

而在思考关于3个代龄的集合的实现类型的时候,我在List<T>和LinkedList<T>上思考了一会,主要是因为我觉得在3个集合中items并不是因各种特定的条件排序过的,所以我们在筛选第三代龄的item并且把筛选后的item放到第二代龄中去的时候就会面临着集合的乱序删除.

在数组的这种状态下,如果有10个项目,删除第1个,则后面9个项目都要向前移动1位,可能造成性能损失.而List<T>就是基于数组而实现的.对于链表来说,乱序删除就显得不是那么恐怖,如果有10个项目在一个链表内,删除第3个项目,则链表会讲第2个项目的Next引用指向第4个项目,而不用再移动任何项目.

我也在博客园中找了不少关于这两个集合的测试,但是关于链表的乱序删除这个强项却没有有力的测试.于是我决定自己试一试.

首先我写一个类Test包含一个List<int>和LinkedList<int>;

其次我在AppendTest方法中以一个向两者分别插入一千万条数据,这些数据是Random函数随机生成的数字.

然后我想测试一下二者纯遍历所需要的时间.

最后测试二者的乱序删除.

代码如下.

class Program
{
    public class Test
    {
        public Test(int count, int condition)
        {
            this.count = count;
            this.condition = condition;
            this.list = new List<int>();
            this.ll = new LinkedList<int>();
        }

        int condition = 0;
        int count = 0;
        List<int> list;
        LinkedList<int> ll;
        Random r = new Random(DateTime.Now.Millisecond);
        Stopwatch sw = new Stopwatch();

        private int GetRandom()
        {
            return r.Next(0, count);
        }

        public void AppendTest()
        {
            Print("+--- " + count + " AppendTest: ---+");

            long listTakes = 0;
            long llTakes = 0;
            sw.Reset();
            sw.Start();
            for (int i = 0 ; i < count ; i++)
            {
                list.Add(GetRandom());
            }
            sw.Stop();
            listTakes = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int i = 0 ; i < count ; i++)
            {
                ll.AddLast(GetRandom());
            }
            sw.Stop();
            llTakes = sw.ElapsedMilliseconds;

            Print("\tList takes  " + listTakes + "  milliseconds to append.");
            Print("\tLinkedList takes  " + llTakes + "  milliseconds to append.");
            Print("+--- Test Finished ---+");
        }

        public void ForEachTest()
        {
            Print("+--- " + count + " ForEachTest: ---+");

            long listTakes = 0;
            long llTakes = 0;
            sw.Reset();
            sw.Start();
            foreach (var item in list)
            {
            }
            sw.Stop();
            listTakes = sw.ElapsedMilliseconds;
            sw.Reset();
            sw.Start();
            foreach (var item in ll)
            {
            }
            sw.Stop();
            llTakes = sw.ElapsedMilliseconds;

            Print("\tList takes  " + listTakes + "  milliseconds to iterating.");
            Print("\tLinkedList takes  " + llTakes + "  milliseconds to iterating.");
            Print("+--- Test Finished ---+");
        }

        public void RemoveTest()
        {
            Print("+--- " + count + " RemoveTest: ---+");
            Print("Both of the collection will remove the item less than " + condition + ".");

            long listTakes = 0;
            long llTakes = 0;
            int listRemoved = 0;
            int llRemoved = 0;
            sw.Reset();
            listRemoved = list.Count;
            sw.Start();
            list.RemoveAll(delegate(int i) { return i < condition; });
            sw.Stop();
            listRemoved -= list.Count;
            listTakes = sw.ElapsedMilliseconds;
            sw.Reset();
            sw.Start();
            var next = ll.First;
            while (next != null)
            {
                if (next.Value < condition)
                {
                    var item = next;
                    next = next.Next;
                    ll.Remove(item);
                    llRemoved++;
                }
                else
                    next = next.Next;
            }
            sw.Stop();
            llTakes = sw.ElapsedMilliseconds;

            Print("\tList takes  " + listTakes + "  milliseconds to removing,and removed " + listRemoved + " items.");
            Print("\tLinkedList takes  " + llTakes + "  milliseconds to removing,and removed " + llRemoved + " items.");
            Print("+--- Test Finished ---+");
        }
    }

    public static void Print(string s)
    {
        Console.WriteLine(s);
    }
    public static void Main(string[] args)
    {
        Test t = new Test(10000000, 10000);

        t.AppendTest();
        Console.Write("\nPress any key to continue . . . \n");
        Console.ReadKey(true);

        t.ForEachTest();
        Console.Write("\nPress any key to continue . . . \n");
        Console.ReadKey(true);

        t.RemoveTest();
        Console.Write("\nPress any key to continue . . . \n");
        Console.ReadKey(true);
    }
}

这些代码应该很好看懂我就不写注释了,主要是最后的RemoveTest中我所使用的两种方法来删除项目,因为foreach循环中不可改变集合的内容.

开始测试.

首先保证代码是Release形式的.

其次测试的机子配置如下:

• CPU: AMD 5000+ BE
• RAM: Kingston 800M 2G *2
• MotherBoard: Colorful AMD 780G

最后上运行结果:

第一次测试:

+--- 10,000,000 AppendTest: ---+
List takes 551 milliseconds to append.
LinkedList takes 4,852 milliseconds to append.
+--- Test Finished ---+

+--- 10,000,000 ForEachTest: ---+
List takes 40 milliseconds to iterating.
LinkedList takes 102 milliseconds to iterating.
+--- Test Finished ---+

+--- 10,000,000 RemoveTest: ---+
Both of the collection will remove the item less than 100,000.
List takes 89 milliseconds to removing,and removed 99,808 items.
LinkedList takes 102 milliseconds to removing,and removed 10,0519 items.
+--- Test Finished ---+

第二次测试:

+--- 10,000,000 AppendTest: ---+
List takes 560 milliseconds to append.
LinkedList takes 5,030 milliseconds to append.
+--- Test Finished ---+

+--- 10,000,000 ForEachTest: ---+
List takes 42 milliseconds to iterating.
LinkedList takes 119 milliseconds to iterating.
+--- Test Finished ---+

+--- 10,000,000 RemoveTest: ---+
Both of the collection will remove the item less than 100,000.
List takes 99 milliseconds to removing,and removed 99,779 items.
LinkedList takes 108 milliseconds to removing,and removed 99,567 items.
+--- Test Finished ---+

第三次测试:

+--- 10,000,000 AppendTest: ---+
List takes 561 milliseconds to append.
LinkedList takes 4,971 milliseconds to append.
+--- Test Finished ---+

+--- 10,000,000 ForEachTest: ---+
List takes 39 milliseconds to iterating.
LinkedList takes 104 milliseconds to iterating.
+--- Test Finished ---+

+--- 10,000,000 RemoveTest: ---+
Both of the collection will remove the item less than 100000.
List takes 90 milliseconds to removing,and removed 99,862 items.
LinkedList takes 101 milliseconds to removing,and removed 100,418 items.
+--- Test Finished ---+

结果:

对于LinkedList<T>的乱序删除我感觉很意外,它的最强项之一竟然也会输给List<T>(不排除我写的LinkedList<T>乱序删除的算法太烂的原因),而添加项目的耗时竟然比List<T>多出8倍多.而且单纯遍历,List<T>表现的也比LinkedList<T>好很多.

所以基于目前简单的测试来看,我的代龄集合应该全部由List<T>这个具有优良的性能又提供了一大堆方便的处理函数的集合来打造!

最后,对于LinkedList<T>的乱序添加我没有测试,因为自己用不到.所以如果需要这方面测试的朋友不妨自己试一下 : )