Phương pháp này có nhanh hơn trong Danh sách <T> .Xóa (T) hoặc Danh sách <T> .RemoveAt (int)?

Question

Phương thức List<T>.Remove(T) hoặc List<T>.RemoveAt(int) trong bộ sưu tập .NET có nhanh hơn không? Tốc độ khác nhau đối với các loại giá trị hoặc loại tham chiếu?

Answer 1

List.Remove (T) sử dụng IndexOf và RemoveAt (int) trong quá trình triển khai. Vì vậy, List.RemoveAt (int) là nhanh hơn.

public bool Remove(T item) 
{ 
    int index = this.IndexOf(item); 
    if (index >= 0) 
    { 
     this.RemoveAt(index); 
     return true; 
    } 
    return false; 
} 

Answer 2

Remove (T) làm cho nội bộ một cuộc gọi đến RemoveAt (int) như vậy, làm trực tiếp một removeAt là nhanh hơn.

Nhưng bạn muốn đạt được điều gì?

Answer 3

câu trả lời đơn giản:

Nói chung, RemoveAt là nhanh hơn, mặc dù không phải lúc nào cũng vô cùng.

Long trả lời:

Hãy chỉ xem xét việc tìm kiếm mục thích hợp đầu tiên. Phương pháp Remove phải tìm kiếm danh sách cho mục phù hợp với đối tượng đã cho, và do đó là O(n) thời gian nói chung. RemoveAt trên danh sách có thể chỉ cần lập chỉ mục mục đã cho và do đó là O(1).

Bây giờ, việc xóa một mục từ cuối danh sách luôn là O(1) tất nhiên, nhưng nói chung việc xóa một mục mất O(n) thời gian, vì cần phải thực hiện thay đổi (di chuyển các mục sau khi chuyển đi). Do đó, trong trường hợp chung, tổng thời gian phức tạp để xóa là O(n) + O(n) hoặc O(n) + O(1) cho Remove và RemoveAt tương ứng, do đó chỉ đơn giản là O(n) trong cả hai trường hợp. Tuy nhiên, RemoveAt được đảm bảo ít nhất là nhanh chóng, mặc dù tỷ lệ là giống nhau trừ khi bạn biết bạn đang xóa nó tại/gần cuối.

Answer 4

Sử dụng System.Diagnostics.Stopwatch()

Tôi vừa tạo một ứng dụng bảng điều khiển nhỏ để kiểm tra xem ứng dụng nào nhanh hơn.

Answer 5

Giả sử rằng .Net đang lây nhiễm một vectơ (hoặc mảng), không phải là một danh sách được liên kết, RemoveAt() sẽ nhanh hơn.