C# List排序性能测试

对于List<T>元素排序的性能一直想测试一下。例如有一个关于明星的列表list { “黎明”, “张学友” , “周星驰” ….} 我希望第 m 个元素的位置排序到第 n 个位置

例如 list[0] -> 2, { “张学友” , “周星驰” ,”黎明”, ….}

废话不多说,我采用了两种方法:【直接插入法】、【局部遍历法】

在开始之前,先创建一个 list 用来测试,传入一个num变量用来改变元素多寡。可以测试在元素变化时对效率有何影响。

public static void TestListSetRank(int num)
{
    List<string> list = new List<string>();
    for (int i = 0; i < num; i++)
        list.Add("a" + i);
}

第一种 【直接插入法】 ,直接插入法意思是,既然已经知道了 起点 m 和 终点 n。那么我先把m位置的引用给删掉, 再把它插入n的位置。

【 直接插入法 】的代码如下,我把它定义成委托func1:

var func1 = new Action<int, int>((n, m) =>
{
    if (n == m)
        return;
    var str = list[m];
    list.RemoveAt(m);
    list.Insert(n, str);
});

第二种 【局部遍历法】,根据 m、n的位置关系确定局部区域,把每个元素的指向引用更改。

【局部遍历方法】的代码如下 ,我把它定义成委托func2:

var func2 = new Action<int, int>((n, m) =>
{
    if (n == m)
        return;              
    var str = list[m];
    int stepnum = n < m ? -1 : 1;
    for (int i = m; i != n; i = i + stepnum)
        list[i] = list[i + stepnum];
    list[n] = str;
});

测试方法:使用一个rodm随机发生器,随机产生在 0~list.Count范围内的两个位置,即 n和m。然后分别调用两个委托方法进行测试。测试结果如下:

创建 10 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3218094 秒
采用【局部遍历】的方法操作元素:共计耗时 0.9492085 秒
创建 100 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3415924 秒
采用【局部遍历】的方法操作元素:共计耗时 3.8234382 秒
创建 1000 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 3.0650181 秒
采用【局部遍历】的方法操作元素:共计耗时 28.1718113 秒

总结:【局部遍历法】对小节点量的排序还可以接受,一旦容量增大,性能损失严重。【直接插入法】相对比较稳定,通过查看List源码可以知道它在后台调用了两次Array Copy方法(插入时调用一次,删除时调用一次)。 以上,对于元素较少的情况,局部遍历法的效率比 调用Copy的开销小,随着元素量增加,则采用直接插入法最好。

完整测试代码:

static void Main(string[] args)
{
    TestListSetRank(10);
    TestListSetRank(100);
    TestListSetRank(1000);
    Console.ReadKey();
}
public static void TestListSetRank(int num)
{
        List<string> list = new List<string>();
        for (int i = 0; i < num; i++)
            list.Add("a" + i);
           
        var func1 = new Action<int, int>((n, m) =>
        {
            if (n == m)
                return;
            var str = list[m];
            list.RemoveAt(m);
            list.Insert(n, str);
        });
        var func2 = new Action<int, int>((n, m) =>
        {
            if (n == m)
                return;              
            var str = list[m];
            int stepnum = n < m ? -1 : 1;
            for (int i = m; i != n; i = i + stepnum)
                list[i] = list[i + stepnum];
            list[n] = str;
        });

        var rodm = new Random();
        int total = 10000000;

        Console.WriteLine("创建 {0} 个节点:", num);
        Console.Write("使用 Insert 和 RemoveAt 方法操作元素:");
        var sw = Stopwatch.StartNew();
        for (int i = 0; i < total; i++)
        {
            var n = rodm.Next(0, num - 1);
            var m = rodm.Next(0, num - 1);
            func1(n, m);
        }
        sw.Stop();
        Console.WriteLine("共计耗时 {0} 秒", sw.Elapsed.TotalSeconds);

        Console.Write("采用【局部遍历】的方法操作元素:");
        sw.Restart();
        for (int i = 0; i < total; i++)
        {
            var n = rodm.Next(0, num - 1);
            var m = rodm.Next(0, num - 1);
            func2(n, m);
        }
        sw.Stop();
        Console.WriteLine("共计耗时 {0} 秒", sw.Elapsed.TotalSeconds);   
}

编辑:经过分析,上文说的元素小的list不太准确,应该是n与m差值小的情况。现在定义一个委托方法func3,它根据差值决定采用哪种方法,我管这个叫混合模式。

【混合模式】的代码如下 ,我把它定义成委托func3:

var func3 = new Action<int, int>((n, m) =>
{
    if (n == m)
        return;

    if (Math.Abs(n - m) < 10)
        func2(n, m);
    else
        func1(n, m);
});

重新测试,结果如下。使用这种模式,list可以根据移动距离选择最佳的排序模式,以实现性能优化。

创建 3 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 0.8282541 秒
采用【局部遍历】的方法操作元素:共计耗时 0.6876499 秒
采用【混合模式】的方法操作元素:共计耗时 0.7015953 秒
创建 5 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 0.902439 秒
采用【局部遍历】的方法操作元素:共计耗时 0.7280125 秒
采用【混合模式】的方法操作元素:共计耗时 0.8775396 秒
创建 7 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 0.9871264 秒
采用【局部遍历】的方法操作元素:共计耗时 0.7870832 秒
采用【混合模式】的方法操作元素:共计耗时 0.9757926 秒
创建 10 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.0613971 秒
采用【局部遍历】的方法操作元素:共计耗时 0.899727 秒
采用【混合模式】的方法操作元素:共计耗时 1.0612489 秒
创建 30 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.2957685 秒
采用【局部遍历】的方法操作元素:共计耗时 1.7546192 秒
采用【混合模式】的方法操作元素:共计耗时 1.3904508 秒
创建 50 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3147112 秒
采用【局部遍历】的方法操作元素:共计耗时 2.0260564 秒
采用【混合模式】的方法操作元素:共计耗时 1.4525724 秒
创建 70 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3862056 秒
采用【局部遍历】的方法操作元素:共计耗时 2.5569355 秒
采用【混合模式】的方法操作元素:共计耗时 1.5220287 秒
创建 100 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3969189 秒
采用【局部遍历】的方法操作元素:共计耗时 3.4157527 秒
采用【混合模式】的方法操作元素:共计耗时 1.5469496 秒
创建 300 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.8116123 秒
采用【局部遍历】的方法操作元素:共计耗时 8.974341 秒
采用【混合模式】的方法操作元素:共计耗时 2.0337284 秒

发表评论

邮箱地址不会被公开。 必填项已用*标注

11 + 20 =