C# nhanh sắp xếp hơn SortedList <>

Question

chúng tôi có một

SortedList<Resource, Resource> resources = 
    new SortedList<Resource, Resource>(new ResourceIdle()); 

mà chúng tôi sử dụng trong mô phỏng của chúng tôi. Danh sách tài nguyên này được khởi tạo theo cách này bởi vì chúng tôi muốn chuyển các trình so sánh khác nhau vào bất kỳ thời điểm nào. Vấn đề đầu tiên chúng tôi có là các SortedList<> đòi hỏi một so sánh thêm trong so sánh để chúng tôi có thể thêm các trường hợp khác nhau của Resource với các thuộc tính tương tự. Ví dụ: nếu Trình so sánh trông giống như:

public int Compare(Resource x, Resource y) 
{ 
    int priority1 = x.Priority;  
    int priority2 = y.Priority;  

    if (priority1 > priority2) { 
     return -1; 
    } else if (priority1 < priority2) { 
     return 1; 
    } else { 
     return (x.Id.CompareTo(y.Id)); 
    } 
} 

thì chúng tôi phải so sánh thêm khi các ưu tiên giống nhau nếu không chúng tôi lấy lại ngoại lệ cho mục nhập có cùng khóa. Vì vậy, câu hỏi của tôi là, có cách nào khác để đạt được điều này? Và như một câu hỏi thứ cấp là có bất cứ điều gì nhanh hơn so với SortedList<> cho đặt hàng số lượng lớn các đối tượng?

Answer 1

Vâng, SortedDictionary<,> có các đặc tính hiệu suất khác nhau - tùy thuộc vào những gì bạn đang làm với nó. MSDN có khá nhiều chi tiết so sánh hai:

Lớp chung là cây tìm kiếm nhị phân với truy xuất O (log n), trong đó n là số phần tử trong từ điển. Về mặt này, nó tương tự như lớp chung chung SortedList<TKey, TValue>. Hai lớp này có các mô hình đối tượng tương tự và cả hai đều có truy xuất O (log n). Trường hợp hai lớp khác nhau là sử dụng bộ nhớ và tốc độ chèn và loại bỏ:

• SortedList<TKey, TValue> sử dụng ít bộ nhớ hơn SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> có thao tác chèn và xóa nhanh hơn cho dữ liệu chưa được phân loại: O (log n) trái ngược với O (n) cho SortedList<TKey, TValue>.
• Nếu danh sách được điền cùng một lúc từ dữ liệu được sắp xếp, SortedList<TKey, TValue> nhanh hơn SortedDictionary<TKey, TValue>.

Answer 2

yêu cầu danh sách luôn được sắp xếp bất cứ lúc nào? nếu không, nó chắc chắn sẽ nhanh hơn để chỉ phân loại theo yêu cầu. ý tưởng khác là để có sự sắp xếp được thực hiện bởi một "OrderPriority" mà là một sự kết hợp của các lĩnh vực ưu tiên và ID, do đó chỉ có một so sánh cần phải được thực hiện:

int OrderPriority { get { return Priority * MAX_ID + ID; } } 

này giả định rằng các ID này không nhận được quá lớn ...

Answer 3

bạn có thể rút ngắn so sánh một chút:

public int Compare(Resource x, Resource y) 
{ 
    int priority1 = x.Priority;  
    int priority2 = y.Priority;  

    if (priority1 != priority2) 
     return priority2 - priority1; 

    return (x.Id.CompareTo(y.Id)); 
} 

Answer 4

Nếu bạn không quan tâm đến việc phân biệt giữa các đối tượng với các ưu tiên như nhau, tại sao không sử dụng một SortedList xô (thực hiện như một có lẽ hàng đợi), với tất cả các mục có mức độ ưu tiên bằng nhau trong cùng một nhóm et?

Answer 5

Khi bạn tạo SortedList từ một từ điển, nó sẽ sao chép khóa và giá trị thành mảng và sau đó sử dụng phương pháp Array.Sort để sắp xếp chúng, vì vậy, bạn sẽ có được một số kiến ​​thức đặc biệt bộ sưu tập có thể giúp bạn chọn một thuật toán khác phù hợp hơn cho trường hợp đặc biệt đó.

Tuy nhiên, có vẻ như bạn đang tạo từ điển có cùng khóa và giá trị chỉ để có thể sử dụng SortedList. Nếu đúng như vậy, bạn nên đặt các mục trong một mảng hoặc một danh sách và sắp xếp chúng. Các phương thức Array.Sort và List<T>.Sort cũng có thể sử dụng trình so sánh tùy chỉnh.

Bạn Comparer với một so sánh thứ cấp có thể được đơn giản hóa như:

public int Compare(Resource x, Resource y) { 
    int result = x.Priority.CompareTo(y.Priority); 
    if (result == 0) { 
    result = x.Id.CompareTo(y.Id); 
    } 
    return result; 
}