C# szybciej niż SortedList sortowanie <>

Question

mamy

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

że używamy w naszej symulacji. Ta lista zasobów jest inicjowana w ten sposób, ponieważ chcemy w dowolnym momencie przekazać różne porównywarki. Pierwszy problem polega na tym, że SortedList<> wymaga dodatkowego porównania w porównywarce, dzięki czemu możemy dodać różne instancje Resource o tych samych właściwościach. Na przykład, jeśli porównywarka wygląda następująco:

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

wtedy musimy dokonać dodatkowego porównania gdy priorytety są takie same, w przeciwnym razie możemy wrócić wyjątek dla wpisu z tym samym kluczem. Moje pytanie brzmi, czy istnieje inny sposób osiągnięcia tego? A jako drugorzędne pytanie, czy istnieje coś szybszego niż SortedList<> do zamawiania dużej liczby obiektów?

Answer 1

Cóż, SortedDictionary<,> ma różne cechy charakterystyczne - to zależy od tego, co robisz z tym. MSDN ma sporo szczegółowo porównujący dwa:

SortedDictionary<TKey, TValue> klasa rodzajowy jest wyszukiwanie binarne drzewo z O (log n) pobierania, gdzie n jest liczbą elementów w słowniku. Pod tym względem jest podobny do klasy ogólnej SortedList<TKey, TValue>. Te dwie klasy mają podobne modele obiektów i oba mają O (log n) pobieranie. W przypadku, gdy dwie grupy różnią się w użyciu pamięci oraz szybkość wprowadzania i usuwania:

• SortedList<TKey, TValue> wymaga mniej pamięci niż SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> ma szybsze operacje wstawiania i usuwania nieposortowanych danych: O (log n) w przeciwieństwie do O (n) dla SortedList<TKey, TValue>.
• Jeśli lista zostanie wypełniona od razu za posortowane dane, SortedList<TKey, TValue> jest szybsza niż SortedDictionary<TKey, TValue>.

Answer 2

Czy jest wymagane, aby lista była zawsze sortowana w dowolnym momencie? jeśli nie, zdecydowanie szybciej byłoby sortować tylko na żądanie. Innym pomysłem jest mieć sortowania być wykonane przez „OrderPriority”, która jest połączeniem priorytetowych dziedzinach oraz identyfikacyjnych, dlatego potrzebuje tylko jeden dokonanie porównania:

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

ten zakłada, że ​​identyfikatory nie zbyt duży ...

Answer 3

można skrócić porównać trochę:

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

Jeśli nie dbają o rozróżniania obiektów o tym samym priorytecie, to dlaczego nie użyć SortedList wiader (zaimplementowany jako w kolejce), z wszystkimi pozycjami o równym priorytecie w tym samym złotówki et?

Answer 5

Po utworzeniu SortedList ze słownika, skopiuje on klucze i wartości do tablic, a następnie sortuje je za pomocą metody Array.Sort, więc jest to prawie tak szybkie, jak to tylko możliwe, chyba że masz jakąś szczególną wiedzę na temat kolekcja, która może pomóc w wyborze innego algorytmu, który lepiej pasuje do tego szczególnego przypadku.

Wygląda jednak na to, że tworzysz słownik z tym samym kluczem i wartością, aby móc korzystać z SortedList. Jeśli tak jest, powinieneś raczej po prostu umieścić elementy w tablicy lub liście i posortować je. W metodach Array.Sort i List<T>.Sort można również użyć niestandardowego porównywalnika.

Ty comparer z wtórnym porównania można uprościć:

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