10

このコードでAQTimeを実行していると、.IndexOfに16％の時間がかかるのに対し、他のコードでは80％近くかかることがわかりました...同じIsEqualおよび他のルーチンを使用しているようです。30,000アイテムを挿入して116,000回呼び出されました。List<>オブジェクトはいずれも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();
    }
}
4

3 に答える 3

10

私は次の仮定をしました：

  • 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>インターフェイスを実装せずに、高価なボクシング操作を含む2つの要素をIndexOf比較します。PointDValueType.Equals(object other)

IEquatable<T>インターフェイスのドキュメントには次のように記載されています。

このIEquatable<T>インターフェイスは、、などの汎用コレクションオブジェクトによって使用され、、、、、などDictionary<TKey, TValue>のメソッドで同等性List<T>をLinkedList<T>テストするときに使用されます。ジェネリックコレクションに格納される可能性のあるすべてのオブジェクトに実装する必要があります。ContainsIndexOfLastIndexOfRemove

これが私の完全なベンチマークコードです：

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
Forループ：00：00：00.0014203

タイミングをPointD変えるとclass

IndexOf：00：00：01.0703627
Forループ：00：00：00.0014190

struct PointD実装 を使用するIEquatable<PointD>と、より「類似した」結果が得られますが、それでも遅くなります（ nowIndexOfを使用しても大きな違いはありません）。class

IndexOf：00：00：00.3904615
Forループ：00：00：00.0015218
于 2010-09-07T22:37:53.423 に答える
4

通常、配列要素にアクセスする前に、インデックスが> = 0かつ<長さであることを確認します。これにより、自分に属していないメモリを読み取ったり上書きしたりすることはありません。特に、バッファオーバーフローと呼ばれる多数の重大なセキュリティ上の欠陥を排除します。

言うまでもなく、ループ内にコードがほとんどない場合、パフォーマンスが低下します。この問題を軽減するために、JITコンパイラは次の形式のforループを最適化しfor (i = 0; i < array.Length; i++) { array[i]; }ます。つまり、0から長さ-1までの配列のすべてのインデックスにアクセスするループです。この場合の境界チェックは省略されます。（array [i + 1]のようなものにアクセスすると、境界を越える可能性があるため、最適化は失敗します。）

残念ながら、これは配列でのみ機能し、List<>では機能しません。したがって、後者のコードは最適化されません。

ただし、List <>には内部的に配列が含まれており、List.IndexOf（）はループを使用して配列内の各値に直接アクセスするため、最適化できます。

ちなみに、実際に配列の長さであるかどうかは定かではないため、言うfor (int i = 0; i < array.Length; i++) { }よりも言うほうがよいでしょう。int length = array.Length; for(int i = 0; i < length; i++) { }length

編集：Reflectorを使用してIndexOfコードを見ると、ループは確かに最適化されますが、ここで他の人が述べているように、Equals（）を呼び出します。これにはvtableルックアップとさまざまな健全性チェックが必要です。したがって、この場合、プロファイラーを使用して実行していない場合、IndexOfは実際には遅くなる可能性があります。

分解されたコード：

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;
}
于 2010-09-07T22:25:52.273 に答える
0

の種類は_pCoord3Points何ですか？要素タイプがオーバーライドするだけの値タイプである場合、値が等しいかどうかをチェックするために値を繰り返しボックスEquals(object)化する可能性があります。IndexOfそれはそれを説明するかもしれません。ただし、現時点では実際には推測にすぎません...問題を示す短いが完全なプログラムを提供できれば、支援がはるかに簡単になります。

于 2010-09-07T21:50:54.323 に答える