为什么这是列表与LT;> .IndexOf代码，所以比列表[i]和手动比较快很多？ [英] Why is this List<>.IndexOf code so much faster than the List[i] and manual compare?

问题描述

我对这段代码运行AQTime，我发现.IndexOf花费的时间与接近80％，而另一片的16％......它们似乎使用相同的ISEQUAL和其他程序。所谓的116000次插入30,000个项目。列表<的无;>对象获得超过200个元素。 （我可能会错误地使用AQTime，我期待这个）

 类PointD：IEquatable< PointD> 
 {
公共双X，Y，Z; 
 
布尔IEquatable< PointD> .Equals（PointD等）
 {
回报率（（X == other.X）及和放大器;（Y == other.Y） &放大器;&放大器（Z == other.Z））; 
} 
} 
 
类PerfTest 
 {
只读表< PointD> _pCoord3Points =新的List< PointD>（）; 
公众诠释NewPoints; 
公众诠释TotalPoints; 
 
公共PerfTest（）
 {
 NewPoints = 0; 
 TotalPoints = 0; 
} 
公众诠释CheckPointIndexOf（PointD PT）
 {
 INT retIndex = _pCoord3Points.IndexOf（PT）; 
如果（retIndex℃，）
 {
 _pCoord3Points.Add（PT）; 
 NewPoints ++; 
} 
 TotalPoints ++; 
返回retIndex; 
} 
 
公众诠释CheckPointForBreak（PointD PT）
 {
 INT retIndex = -1; 
的for（int i = 0; I< _pCoord3Points.Count;我++）
 {
 PointD otherPt = _pCoord3Points [I] 
如果（（pt.X == otherPt.X）及&放大器; 
（pt.Y == otherPt.Y）及&放大器; 
（pt.Z == otherPt。 Z））
 {
 retIndex = I; 
中断; 
} 
} 
如果（retIndex == -1）
 {
 NewPoints ++; 
 _pCoord3Points.Add（PT）; 
} 
 TotalPoints ++; 
返回retIndex; 
} 
 
静态无效的主要（）
 {
 const int的XMAX = 300; 
 const int的YMAX = 10; 
 const int的ZMAX = 10; 
 const int的IMAX = 4; 
 
变种测试=新PerfTest（）; 
 //test.Init（）; 
秒表SW = Stopwatch.StartNew（）; 
的for（int i = 0; I< IMAX，我++）
 {
的for（int x = 0; X< XMAX; X ++）
 {
对于（INT Y = 0; Y< YMAX; Y ++）
 {
为（INT Z = 0; z，其中，ZMAX; Z ++）
 {
变种PT =新PointD {X = X，Y = Y，Z = Z}; 
 test.CheckPointIndexOf（PT）; 
} 
} 
} 
 
} 
 sw.Stop（）; 
字符串输出=的String.Format（总计：{0：0}新：{1：0}的IndexOf：test.TotalPoints，test.NewPoints）; 
 Console.Write（输出）; 
 Console.WriteLine（sw.Elapsed）; 
 
测试=新PerfTest（）; 
 SW = Stopwatch.StartNew（）; 
的for（int i = 0; I< IMAX，我++）
 {
的for（int x = 0; X< XMAX; X ++）
 {
对于（INT Y = 0; Y< YMAX; Y ++）
 {
为（INT Z = 0; z，其中，ZMAX; Z ++）
 {
变种PT =新PointD {X = X，Y = Y，Z = Z}; 
 test.CheckPointForBreak（PT）; 
} 
} 
} 
 
} 
 sw.Stop（）; 
班产量的String.Format（总计：{0：0}新：{1：0} PointD []，test.TotalPoints，test.NewPoints）; 
 Console.Write（输出）; 
 Console.WriteLine（sw.Elapsed）; 
到Console.ReadLine（）; 
} 
} 
  

解决方案

我做了如下假设：

• PointD 是一个结构


• 的IndexOf 确实比手动迭代名单慢

您可以加快的IndexOf 通过执行 IEquatable< T> 接口：

 结构PointD：IEquatable< PointD> 
 {
公众诠释X; 
公众诠释Ÿ; 
公众诠释Z者除外; 
 
公共布尔等于（PointD等）
 {
回报率（this.X == other.X）及和放大器; 
（this.Y == other.Y）及&放大器; 
（this.Z == other.Z）; 
} 
} 
  

但没有实施 IEquatable< T> 接口，的IndexOf 将通过比较两个 PointD 元素 ValueType.Equals（对象等）这涉及昂贵的装箱操作

的

IEquatable 1所述的文件; T> 接口状态：

的

IEquatable< T> 接口被泛型集合对象，如词典< TKEY的，TValue> ，列表< T> 和的LinkedList< T>如包含 ，的IndexOf ， LastIndexOf 和删除。 它应该是可能存储在一个泛型集合的任何对象实现的。

下面是我的完整基准代码：

 使用系统; 
使用System.Collections.Generic;使用System.Diagnostics程序
; 
 
结构PointD 
 {
公众诠释X; 
公众诠释Ÿ; 
公众诠释Z者除外; 
} 
 
类PerfTest 
 {
名单，LT; PointD> _pCoord3Points =新的List< PointD>（）; 
 
 INT checkPointIndexOf（PointD PT）
 {
返回_pCoord3Points.IndexOf（PT）; 
} 
 
 INT checkPointForBreak（PointD PT）
 {
 INT retIndex = -1; 
的for（int i = 0; I< _pCoord3Points.Count;我++）
 {
 PointD otherPt = _pCoord3Points [I] 
如果（（pt.X == otherPt.X）及&放大器; 
（pt.Y == otherPt.Y）及&放大器; 
（pt.Z == otherPt。 Z））
 retIndex = I; 
中断; 
} 
返回retIndex; 
} 
 
无效的init（）
 {
的for（int x = 0; X< 100; X ++）
 {
为（INT Y = 0; Y小于10; Y ++）
 {
为（INT Z = 0; z，其中10; Z ++）
 {
 PointD PT =新PointD （）{X = X，Y = Y，Z = Z}; 
 _pCoord3Points.Add（PT）; 
} 
} 
} 
} 
 
静态无效的主要（字串[] args）
 {
 PerfTest测试=新PerfTest（）; 
 test.init（）; 
秒表SW = Stopwatch.StartNew（）; 
表示（中间体X = 0; X&小于100; X ++）
 {
表示（中间体Y = 0; Y小于10; Y ++）
 {
对（INT z = 0的; z，其中; 10; Z ++）
 {
 PointD PT =新PointD（）{X = X，Y = Y，Z = Z}; 
 test.checkPointIndexOf（PT）; 
} 
} 
} 
 sw.Stop（）; 
 Console.WriteLine（sw.Elapsed）; 
 SW = Stopwatch.StartNew（）; 
表示（中间体X = 0; X&小于100; X ++）
 {
表示（中间体Y = 0; Y小于10; Y ++）
 {
对（INT z = 0的; z，其中; 10; Z ++）
 {
 PointD PT =新PointD（）{X = X，Y = Y，Z = Z}; 
 test.checkPointForBreak（PT）; 
} 
} 
} 
 sw.Stop（）; 
 Console.WriteLine（sw.Elapsed）; 
} 
} 
  

在Windows 7中，64位，.NET 4.0 x64的版本我得到以下计时（约）：

 
的IndexOf：00：00：04.8096623 
 For循环：00：00：00.0014203 
 

当转动时 PointD 到类的时序变化

 
的IndexOf：00：00：01.0703627 
 For循环：00：00：00.0014190 
 

在使用结构PointD 实施 IEquatable< PointD> 我得到更多的类似的结果，但的IndexOf 还是慢（有没有显著差异使用时，类现在）：

 
的IndexOf：00：00：00.3904615 
 For循环：00：00：00.0015218 
 

I'm running AQTime on this piece of code, I found that .IndexOf takes 16% of the time vs close to 80% for the other piece... They appear to use the same IsEqual and other routines. Called 116,000 times inserting 30,000 items. None of the List<> objects gets over 200 elements. (I may be using AQTime incorrectly, I'm looking into this)

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

解决方案

I made the following assumptions:

• PointD is a struct
• IndexOf is indeed slower than manually iterating the list

You can speed up IndexOf by implementing the IEquatable<T> interface:

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

Without implementing the IEquatable<T> interface, IndexOf will compare the two PointD elements using ValueType.Equals(object other) which involves expensive boxing operations.

The documentation of the IEquatable<T> interface states:

The IEquatable<T> interface is used by generic collection objects such as Dictionary<TKey, TValue>, List<T>, and LinkedList<T> when testing for equality in such methods as Contains, IndexOf, LastIndexOf, and Remove. It should be implemented for any object that might be stored in a generic collection.

Here is my complete benchmark code:

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

On Windows 7, x64, .NET 4.0 x64 build I get the following timings (approx):

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

When turning PointD into a class the timings change to

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

When using a struct PointD implementing IEquatable<PointD> I get more "similar" results, but IndexOf is still slower (there is no significant difference when using a class now):

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

这篇关于为什么这是列表与LT;&GT; .IndexOf代码，所以比列表[i]和手动比较快很多？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！