Почему этот список <>. Индекс код намного быстрее, чем список [I] и ручной сравнить?

Question

Я бегу в AQTime на этом кусочке кода, я обнаружил, что .indexof занимает 16% времени против 80% для другой части ... они, кажется, используют одни и те же неравные и другие процедуры. Называется 116 000 раз, вставляя 30 000 предметов. Ни один из список объектов <> не получает более 200 элементов. (Я могу использовать aqtime неправильно, я ищу это)

class PointD : IEquatable<PointD>
{
    public double X, Y, Z;

    bool IEquatable<PointD>.Equals(PointD other)
    {
        return ((X == other.X) && (Y == other.Y) && (Z == other.Z));
    }
}

class PerfTest
{
    readonly List<PointD> _pCoord3Points = new List<PointD>();
    public int NewPoints;
    public int TotalPoints;

    public PerfTest()
    {
        NewPoints = 0;
        TotalPoints = 0;
    }
    public int CheckPointIndexOf(PointD pt)
    {
        int retIndex = _pCoord3Points.IndexOf(pt);
        if (retIndex < 0)
        {
            _pCoord3Points.Add(pt);
            NewPoints++;
        }
        TotalPoints++;
        return retIndex;    
    }

    public int CheckPointForBreak(PointD pt)
    {
        int retIndex = -1;
        for (int i = 0; i < _pCoord3Points.Count; i++)
        {
            PointD otherPt = _pCoord3Points[i];
            if ((pt.X == otherPt.X) &&
                (pt.Y == otherPt.Y) &&
                (pt.Z == otherPt.Z))
            {
                retIndex = i;
                break;
            }
        }
        if (retIndex == -1)
        {
            NewPoints++;
            _pCoord3Points.Add(pt);
        }
        TotalPoints++;
        return retIndex;
    }

    static void Main()
    {
        const int xmax = 300;
        const int ymax = 10;
        const int zmax = 10;
        const int imax = 4;

        var test = new PerfTest();
        //test.Init();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < imax; i++)
        {
            for (int x = 0; x < xmax; x++)
            {
                for (int y = 0; y < ymax; y++)
                {
                    for (int z = 0; z < zmax; z++)
                    {
                        var pt = new PointD { X = x, Y = y, Z = z };
                        test.CheckPointIndexOf(pt);
                    }
                }
            }

        } 
        sw.Stop();
        string output = string.Format("Total: {0:0} New: {1:0} IndexOf: ", test.TotalPoints, test.NewPoints);
        Console.Write(output);
        Console.WriteLine(sw.Elapsed);

        test = new PerfTest();
        sw = Stopwatch.StartNew();
        for (int i = 0; i < imax; i++)
        {
            for (int x = 0; x < xmax; x++)
            {
                for (int y = 0; y < ymax; y++)
                {
                    for (int z = 0; z < zmax; z++)
                    {
                        var pt = new PointD { X = x, Y = y, Z = z };
                        test.CheckPointForBreak(pt);
                    }
                }
            }

        } 
        sw.Stop();
        output = string.Format("Total: {0:0} New: {1:0} PointD[] ", test.TotalPoints, test.NewPoints);
        Console.Write(output);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }
}

Answer 1

Я сделал следующие допущения:

• PointD это структура
• IndexOf действительно медленнее, чем вручную итерацию списка

Вы можете ускорить IndexOf Реализация IEquatable<T> интерфейс:

struct PointD : IEquatable<PointD>
{
    public int X;
    public int Y;
    public int Z;

    public bool Equals(PointD other)
    {
        return (this.X == other.X) &&
                (this.Y == other.Y) &&
                (this.Z == other.Z);
    }
}

Без реализации IEquatable<T> интерфейс, IndexOf будет сравнивать два PointD Элементы с использованием ValueType.Equals(object other) который включает в себя дорогие боксерские операции.

Документация IEquatable<T> Штаты интерфейса:

То IEquatable<T> Интерфейс используется универсальными объектами коллекции, такими как Dictionary<TKey, TValue>, List<T>, а также LinkedList<T> При тестировании на равенство в таких методах как Contains, IndexOf, LastIndexOf, а также Remove. Он должен быть реализован для любого объекта, который может храниться в общем коллекции.

Вот мой полный эталон код:

using System;
using System.Collections.Generic;
using System.Diagnostics;

struct PointD 
{
    public int X;
    public int Y;
    public int Z;
}

class PerfTest
{
    List<PointD> _pCoord3Points = new List<PointD>();

    int checkPointIndexOf(PointD pt)
    {
        return _pCoord3Points.IndexOf(pt);  
    }

    int checkPointForBreak(PointD pt)
    {
        int retIndex = -1;
        for (int i = 0; i < _pCoord3Points.Count; i++)
        {
            PointD otherPt = _pCoord3Points[i];
            if ((pt.X == otherPt.X) &&
                (pt.Y == otherPt.Y) &&
                (pt.Z == otherPt.Z))
                retIndex = i;
            break;
        }
        return retIndex;
    }

    void init()
    {
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    _pCoord3Points.Add(pt);
                }
            }
        }
    }

    static void Main(string[] args)
    {
        PerfTest test = new PerfTest();
        test.init();
        Stopwatch sw = Stopwatch.StartNew();
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    test.checkPointIndexOf(pt);
                }
            }
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
        sw = Stopwatch.StartNew();
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    test.checkPointForBreak(pt);
                }
            }
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
    }
}

На Windows 7, x64, .NET 4.0 x64 Создание Я получаю следующие время (ок.):

Indexof: 00: 00: 04.8096623 для цикла: 00:00: 00.0014203

При повороте PointD в а class время меняется на

Индекс: 00: 00: 01.0703627 для цикла: 00:00: 00.0014190

При использовании A. struct PointD реализация IEquatable<PointD> Я получаю больше «похожи» результатов, но IndexOf все еще медленнее (не существует значительного разницы при использовании class сейчас):

Индекс: 00:00: 00.3904615 для цикла: 00: 00: 00.0015218

Answer 2

Обычно, прежде чем получить доступ к элементу массива, он проверяет, чтобы убедиться, что индекс является> = 0 и <длина - так что вы не читаете или перезапишите память, которая не принадлежит вам. Среди прочего, это устраняет вредных недостатков безопасности, называемых Переполнение буфера.

Излишне говорить, что препятствует выступлению, если у вас очень мало код в вашем цикле. Чтобы уменьшить эту проблему, Compiler JIT оптимизирует для петлей формы for (i = 0; i < array.Length; i++) { array[i]; } - То есть любая петля, которая обращается к всем показателям массива от 0 до длины - 1. Он пропускает проверку границ на этот случай. (Оптимизация выходит из строя, если вы получите доступ к тому, как Array [I + 1], по той причине, по которой вы можете наступить на границы.)

К сожалению, это только работает с массивами, а не со списком <> s. Таким образом, ваш последний код не будет оптимизирован.

Но поскольку список <> внутренне содержит массив, и list.indexof () использует цикл для доступа к каждому значению в массиве напрямую, его можно оптимизировать.

Кстати, лучше сказать for (int i = 0; i < array.Length; i++) { } чем сказать int length = array.Length; for(int i = 0; i < length; i++) { } - потому что это не может быть уверена, что length Действительно это длина массива.

Редактировать: Глядя на код indexOf, используя отражатель, цикл действительно оптимизирует, но, поскольку другие люди здесь упомянули, он называет равную () - что требует VTable Lookup и различные здравомыслие проверки. Таким образом, в этом случае индекс может на самом деле быть медленнее, когда вы не используете его с помощью профилировщика.

Разобранный код:

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
        {
            return i;
        }
    }
    return -1;
}

Answer 3

Какой тип _pCoord3Points? Если тип элемента является типом значения, который только переопределяет Equals(object) тогда возможно, что IndexOf неоднократно боксерские значения для проверки равенства. Это мощь объясни это. Это действительно просто догадка на данный момент, хотя ... если бы вы могли предоставить короткую, но полную программу, которая демонстрирует проблему, которая сделает вам намного легче помочь вам.