Perché questo elenco <>. IndexOf codice in modo molto più veloce rispetto alla Lista [i] e manuale confrontare?

Question

Io corro AQTime su questo pezzo di codice, ho scoperto che .IndexOf prende il 16% del tempo vs vicino al 80% per l'altro pezzo ... Essi sembrano utilizzare lo stesso IsEqual e altre routine. Chiamato 116.000 volte l'inserimento di 30.000 articoli. Nessuno dei List <> oggetti ottiene più di 200 elementi. (I può essere usando AQTime in modo non corretto, sto cercando in questo)

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

ho fatto le seguenti ipotesi:

• PointD è una struct
• IndexOf è infatti più lento rispetto l'iterazione manualmente l'elenco

È possibile accelerare IndexOf implementando l'interfaccia 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);
    }
}

Senza implementare l'interfaccia IEquatable<T>, IndexOf confronterà i due elementi PointD utilizzando ValueType.Equals(object other) che comporta operazioni boxe costose.

La documentazione degli stati di interfaccia IEquatable<T>:

  

L'interfaccia IEquatable<T> viene utilizzata per collezione generica oggetti come Dictionary<TKey, TValue>, List<T> e LinkedList<T> durante il test per l'uguaglianza in tali metodi come Contains, IndexOf, LastIndexOf e Remove. Si dovrebbe essere attuata per qualsiasi oggetto che potrebbe essere memorizzato in un insieme generico.

Ecco il mio codice di riferimento completo:

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

In Windows 7, x64, x64 NET 4.0 accumulo Ottengo i seguenti orari (circa):

IndexOf:  00:00:04.8096623
For Loop: 00:00:00.0014203

Quando si accende PointD in una class i tempi cambiano per

IndexOf:  00:00:01.0703627
For Loop: 00:00:00.0014190

Quando si utilizza una struct PointD attuazione IEquatable<PointD> ottengo più risultati "simili", ma IndexOf è ancora più lento (non v'è alcuna differenza significativa quando si utilizza un class ora):

IndexOf:  00:00:00.3904615
For Loop: 00:00:00.0015218

Answer 2

In genere, prima di accedere a un elemento dell'array, controlla per assicurarsi che l'indice è> = 0 e buffer di overflow .

Inutile dire, che ostacola le prestazioni se si hanno ben poco codice all'interno del tuo ciclo. Per ridurre questo problema, il compilatore JIT ottimizza per-loop della forma for (i = 0; i < array.Length; i++) { array[i]; } - cioè, ogni ciclo che accede tutti gli indici di una matrice da 0 a lunghezza - 1. omette il controllo dei limiti per questo caso. (L'ottimizzazione non riesce se si accede cose come array [i + 1], per la ragione che si potrebbe scavalcare i limiti.)

Purtroppo questo funziona solo con gli array, non con List <> s. Così il vostro quest'ultimo codice non sarà ottimizzato.

Ma poiché un List <> contiene internamente un array, e List.IndexOf () utilizza un ciclo per ogni accesso valore nella matrice direttamente, può essere ottimizzato.

Tra l'altro, è meglio dire for (int i = 0; i < array.Length; i++) { } di quello che è da dire int length = array.Length; for(int i = 0; i < length; i++) { } -. Perché non può essere sicuro che length è davvero la lunghezza della matrice

Modifica: guardando il codice IndexOf utilizzando Reflector, il ciclo sarà davvero ottimizzare, ma come le altre persone qui hanno già detto, chiama Equals () - che richiede un vtable lookup vari controlli di integrità e . Quindi, in questo caso, IndexOf potrebbe infatti essere più lento quando non sei in esecuzione con un profiler.

Il codice disassemblato:

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

Qual è il tipo di _pCoord3Points? Se il tipo di elemento è un tipo di valore cui solo sostituzioni Equals(object) allora è possibile che IndexOf è ripetutamente valori boxe controllare l'uguaglianza. Quella potrebbe spiegarlo. E 'davvero solo congetture, a questo punto anche se ... se si potesse fornire un programma breve ma completo che illustra il problema, che renderebbe molto più facile per aiutarvi.