Tuple<long,long,string>간단한 “사이”검색을 수행하는 무작위로 생성 된 500000 개의 개체 목록이 있습니다 .

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

무작위 배열을 생성하고 100 개의 무작위로 생성 된 값에 대한 검색을 실행 x하면 약 4 초 안에 검색이 완료됩니다. 그러나 정렬이 검색 하는 데있어 놀라운 점을 알고 있었지만, 100 개의 검색을 실행하기 전에 먼저 데이터를 정렬 Item1한 다음 Item2마지막으로 정렬하기로 결정했습니다 Item3. 분기 예측으로 인해 정렬 된 버전이 약간 더 빨리 수행 될 것으로 예상했습니다. 내 생각은 일단 우리가 Item1 == x더 이상 모든 검사가 t.Item1 <= x지점을 “취득 없음”으로 정확하게 예측하여 검색. 놀랍게도 정렬 된 배열에서 검색하는 데 두 배가 걸렸습니다 !

실험을 실행 한 순서를 바꾸고 난수 생성기에 다른 시드를 사용했지만 그 효과는 동일합니다. 정렬되지 않은 배열의 검색은 같은 배열의 검색보다 거의 두 배 빠르지 만 분류!

누구든지이 이상한 효과에 대해 잘 설명하고 있습니까? 내 테스트의 소스 코드는 다음과 같습니다. .NET 4.0을 사용하고 있습니다.

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);
}

Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)

답변