为什么处理排序的数组比未分类的数组慢？

Question

阅读器注：这是类似问题的重复的重复性为什么处理排序的数组比处理未分类的数组更快？这两个问题侧重于不同的前提，因此有不同的解释。 我有一个随机生成的500000个列表，我在上面执行简单的“”搜索： Tuple<long,long,string> 当我生成随机数组并运行100个随机生成的值

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

的搜索时，搜索在大约四秒钟内完成。但是，我知道排序对搜索的奇迹，但是，我决定对数据进行排序 - 首先是

x

，然后是

Item1

，最后是

Item2

- - 在进行100次搜索之前。我希望由于分支机构的预测，分类版本的执行速度会更快：我的想法是，一旦我们到达

Item3

的地步，所有进一步的检查都会正确预测分支，因为“ no take take”，可以加快搜索的尾巴部分。令我惊讶的是，搜索在排序的阵列上花了两倍的时间！

i我尝试在我运行实验的顺序上切换，并为随机数生成器使用了不同的种子，但是效果是相同的：在未排序阵列中搜索的速度几乎是同一数组中的搜索，但分类！

有人对这种奇怪的效果有很好的解释吗？我的测试的源代码如下；我正在使用.NET4.0.

Item1 == x

t.Item1 <= x

当您使用未分类列表时，所有元素均在

Memory-ordord中访问。他们在RAM中连续分配。 CPU喜欢依次访问内存，因为他们可以投机请求下一个缓存行，因此在需要时始终存在。

当您对列表进行排序时，您将其放入

随机订单上，因为您的排序键是随机生成的。这意味着对元组成员的内存访问是不可预测的。 CPU无法预取存储，几乎所有对元组的访问都是缓存小姐。 这是一个很好的示例，它具有GC内存管理的特定优势：已分配在一起并一起使用的数据结构非常出色。他们具有很大的参考第众。

在这种情况下，CACHES的罚款toverweightwighte the保存的分支预测罚款

。 trory切换到

private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
    var data = new byte[8];
    r.NextBytes(data);
    return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
        var res = x.Item1.CompareTo(y.Item1);
        if (res != 0) return res;
        res = x.Item2.CompareTo(y.Item2);
        return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
    }
}
static void Test(bool doSort) {
    var data = new List<Tuple<long,long,string>>(TotalCount);
    var random = new Random(1000000007);
    var sw = new Stopwatch();
    sw.Start();
    for (var i = 0 ; i != TotalCount ; i++) {
        var a = NextLong(random);
        var b = NextLong(random);
        if (a > b) {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var s = string.Format("{0}-{1}", a, b);
        data.Add(Tuple.Create(a, b, s));
    }
    sw.Stop();
    if (doSort) {
        data.Sort(new TupleComparer());
    }
    Console.WriteLine("Populated in {0}", sw.Elapsed);
    sw.Reset();
    var total = 0L;
    sw.Start();
    for (var i = 0 ; i != TotalQueries ; i++) {
        var x = NextLong(random);
        var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
        total += cnt;
    }
    sw.Stop();
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
    Test(false);
    Test(true);
    Test(false);
    Test(true);
}

tuple。这将恢复性能，因为在运行时不需要指针裁定才能访问元组成员。

ChrisSinclair在评论中指出，“对于总计约10,000或更少，排序的版本确实更快地执行了”。这是因为一个小列表完全符合CPU缓存。内存访问可能是不可预测的，但目标始终处于缓存中。我相信仍然有很小的罚款，因为即使是高速缓存的负载也需要一些周期。但这似乎并不是问题，因为

---

CPU可以兼顾多个出色的负载

，从而增加吞吐量。每当CPU达到内存等待时，它仍然会在指令流中加速，以尽可能多的内存操作排队。该技术用于隐藏潜伏期。

这种行为表明预测现代CPU的性能是多么困难。从顺序到随机内存访问到我的封面下发生了多少以隐藏内存延迟的情况，我们只有2x慢了2x。内存访问可以使CPU停滞50-200个周期。鉴于该数字在引入随机存储器访问时可能会期望该程序速度降低> 10倍。

---

linq不知道您是否已排序。

Answer 1

要利用排序阵列的性能优势（例如二进制搜索），您必须进行更多的编码。