Các lựa chọn thay thế nhanh hơn .Distinct()

Question

Tôi đang tạo một trò chơi điện tử, nơi hiệu suất rất quan trọng.

Tôi đang sử dụng phương thức tiện ích mở rộng .Distinct() để nhận giá trị duy nhất từ ​​Danh sách. Có cách nào nhanh hơn để làm như vậy không? (ngay cả khi nó có nghĩa là có nhiều dòng mã hơn)

Answer 1

.Distinct là cuộc gọi O(n).
Bạn không thể nhận được bất kỳ nhanh hơn thế.

Tuy nhiên, bạn nên đảm bảo rằng GetHashCode (và, ở mức độ thấp hơn, Equals) càng nhanh càng tốt.

Tùy thuộc vào kịch bản của bạn, bạn có thể thay thế List<T> bằng HashSet<T>, điều này sẽ ngăn không cho các bản sao được chèn vào vị trí đầu tiên. (chưa có O(1) cách chèn)

Tuy nhiên, Luôn cấu hình mã của bạn trước khi đi đến kết luận về những gì cần nhanh hơn.

Answer 2

Có phải là Danh sách không?

Bạn có thể chuyển từ Danh sách sang HashSet không? HashSet ngăn không cho các đối tượng được chèn vào danh sách nhiều hơn một lần ngay từ đầu, do đó, Distinct đã được thực hiện.

Answer 3

Nếu bạn có thể làm khác biệt tại chỗ, bạn có thể làm điều đó rất nhanh chóng và với số không phân bổ bằng cách đầu tiên sử dụng Array.Sort và sau đó:

TSource oldV = source[0]; 
int pos = 1; 
for (int i = 1; i < source.Count; i++) 
{ 
    var newV = source[i]; 
    source[pos] = newV; 
    if (!eqComparer.Equals(newV, oldV)) 
    { 
     pos++; 
    }     
    oldV = newV; 
} 
//pos now == the new size of the array 

Sau đó bạn sẽ phải tiếp tục theo dõi những kích thước hiện nay nhỏ hơn mảng, hoặc sử dụng Array.resize (Nhưng điều đó sẽ phân bổ một mảng mới)

Hoặc nếu bạn thực hiện cách tiếp cận tương tự này với List<T>, bạn có thể gọi RemoveRange ở cuối để thay đổi kích thước mà không phân bổ. Điều này kết thúc nhanh hơn đáng kể.

Các áp phích khác có thể là chính xác mặc dù bạn có thể đạt được mục tiêu này một cách khác, chẳng hạn như sử dụng một bộ băm ở vị trí đầu tiên hoặc giữ các bộ sưu tập song song trong đó chỉ chứa các phần tử riêng biệt. Bù đắp chi phí nhỏ trên chèn/loại bỏ vì vậy mà không có thời gian ở tất cả là cần thiết để có được bộ khác biệt.