Tại sao Danh sách này <>. Mã IndexOf nhanh hơn nhiều so với Danh sách [i] và so sánh thủ công?

Question

Tôi đang chạy AQTime trên đoạn mã này, tôi thấy rằng .IndexOf mất 16% thời gian so với gần 80% cho phần khác ... Chúng dường như sử dụng cùng một IsEqual và các thường trình khác. Được gọi là 116.000 lần chèn 30.000 mặt hàng. Không có đối tượng nào trong Danh sách <> nhận hơn 200 phần tử. (Tôi có thể sử dụng AQTime không chính xác, tôi đang xem xét điều này)

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

tôi đã giả định sau:

• PointD là một struct
• IndexOf thực sự là chậm hơn so với tự lặp lại danh sách

Bạn có thể tăng tốc độ IndexOf bằng cách thực hiện các giao diện 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); 
    } 
} 

Nếu không thực hiện giao diện IEquatable<T>, IndexOf sẽ so sánh hai PointD yếu tố sử dụng ValueType.Equals(object other) trong đó bao gồm các hoạt động đấm bốc đắt tiền.

Các tài liệu của các bang giao diện IEquatable<T>:

Giao diện IEquatable<T> được sử dụng bởi bộ sưu tập chung các đối tượng như Dictionary<TKey, TValue>, List<T>, và LinkedList<T> khi kiểm tra cho sự bình đẳng trong các phương pháp như Contains, IndexOf, LastIndexOf, và Remove. Cần được triển khai cho bất kỳ đối tượng nào có thể được lưu trữ trong bộ sưu tập chung.

Đây là mã chuẩn hoàn chỉnh của tôi:

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

Trên Windows 7, x64, .NET 4.0 x64 build tôi nhận được timings sau (xấp xỉ):

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

Khi quay PointD vào một class thời gian thay đổi thành

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

Khi sử dụng một struct PointD thực hiện IEquatable<PointD> tôi nhận được nhiều hơn "tương tự" kết quả, nhưng IndexOf vẫn là chậm (không có khác biệt đáng kể khi sử dụng một class bây giờ):

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

Answer 2

Loại _pCoord3Points là gì? Nếu loại phần tử là loại giá trị chỉ ghi đè Equals(object) thì có thể là IndexOf là các giá trị quyền anh liên tục để kiểm tra sự bình đẳng. Điều đó có thể giải thích điều đó. Nó thực sự chỉ là phỏng đoán tại thời điểm này mặc dù ... nếu bạn có thể cung cấp một chương trình ngắn nhưng đầy đủ mà chứng minh vấn đề, mà sẽ làm cho nó dễ dàng hơn nhiều để giúp bạn.

Answer 3

Thông thường, trước khi bạn truy cập phần tử mảng, nó kiểm tra để đảm bảo rằng chỉ mục là> = 0 và < độ dài - để bạn không đọc hoặc ghi đè bộ nhớ không thuộc về bạn. Trong số những thứ khác, nó loại bỏ một loạt các lỗ hổng bảo mật nghiêm trọng được gọi là buffer overflows.

Không cần phải nói, điều đó cản trở hiệu suất nếu bạn có rất ít mã trong vòng lặp của mình. Để giảm bớt vấn đề này, trình biên dịch JIT tối ưu hóa các vòng lặp của biểu mẫu for (i = 0; i < array.Length; i++) { array[i]; } - tức là, bất kỳ vòng lặp nào truy cập tất cả các chỉ mục của một mảng từ 0 đến chiều dài - 1. Nó bỏ qua việc kiểm tra giới hạn cho trường hợp này. (Tối ưu hóa không thành công nếu bạn truy cập vào những thứ như mảng [i + 1], vì lý do bạn có thể vượt qua các giới hạn đó.)

Thật không may là nó chỉ hoạt động với các mảng chứ không phải với Danh sách <> s. Vì vậy, mã thứ hai của bạn sẽ không được tối ưu hóa.

Nhưng kể từ danh sách <> nội bộ chứa một mảng và List.IndexOf() sử dụng vòng lặp để truy cập từng giá trị trong mảng trực tiếp, nó có thể được tối ưu hóa.

Bằng cách này, tốt hơn là nói for (int i = 0; i < array.Length; i++) { } hơn là nói int length = array.Length; for(int i = 0; i < length; i++) { } - vì không thể chắc chắn rằng length thực sự là độ dài của mảng.

Chỉnh sửa: nhìn vào mã IndexOf sử dụng Reflector, vòng lặp thực sự sẽ tối ưu hóa, nhưng như những người khác ở đây đã đề cập, nó gọi Equals() - yêu cầu vtable lookup và kiểm tra sanity khác nhau. Vì vậy, trong trường hợp này, IndexOf thực tế có thể chậm hơn khi bạn không chạy nó với một trình lược tả.

Mã tháo rời:

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