C # более быстрая сортировка, чем SortedList <>

Question

у нас есть

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

, которые мы используем в нашей симуляции. Этот список ресурсов инициализируется таким образом, потому что мы хотим передавать разные компараторы в любой момент времени. Первая проблема, с которой мы столкнулись, заключается в том, что SortedList<> требует дополнительного сравнения в компараторе, чтобы мы могли добавлять разные экземпляры Resource с одинаковыми свойствами. Например, если Comparer выглядит так:

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

тогда мы должны сделать дополнительное сравнение, когда приоритеты одинаковы, иначе мы получим исключение для записи с тем же ключом. Итак, мой вопрос, есть ли другой способ достижения этого? И как вторичный вопрос, есть ли что-нибудь быстрее, чем SortedList<> для заказа большого количества объектов?

Answer 1

Ну, SortedDictionary<,> имеет различные характеристики производительности - это зависит от того, что вы делаете с ним. В MSDN довольно много деталей, сравнивающих два:

Универсальный класс SortedDictionary<TKey, TValue> представляет собой двоичное дерево поиска с поиском O (log n), где n - количество элементов в словаре. В этом отношении он похож на универсальный класс SortedList<TKey, TValue>. Два класса имеют похожие объектные модели, и оба имеют O (log n) извлечения. Различаются два класса в использовании памяти и скорости вставки и удаления:

• SortedList<TKey, TValue> использует меньше памяти, чем SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> имеет более быстрые операции вставки и удаления для несортированных данных: O (log n), а не O (n) для SortedList<TKey, TValue>.
• Если список заполняется сразу из отсортированных данных, SortedList<TKey, TValue> быстрее, чем SortedDictionary<TKey, TValue>.

Answer 2

Если вас не волнует различие между объектами с одинаковым приоритетом, почему бы не использовать SortedList списков (возможно, реализованных в виде очереди) со всеми элементами одинакового приоритета в одном сегменте?

Answer 3

Вы можете немного сократить сравнение:

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

это требование, чтобы список всегда сортировался в любое время?если нет, то, безусловно, будет быстрее сортировать только по требованию.другая идея заключается в том, чтобы сортировка выполнялась с помощью «OrderPriority», который представляет собой комбинацию полей «Приоритет» и «ID», поэтому необходимо сделать только одно сравнение:получить слишком большой ...

Answer 5

Когда вы создаете SortedList из словаря, он копирует ключи и значения в массивы, а затем использует метод Array.Sort для их сортировки, так что это довольно быстро, если вы не получили специальные знания о коллекции, которые могут помочь вам выбрать другой алгоритм, который лучше подходит для этого особого случая.

Однако, похоже, вы создаете словарь с тем же ключом и значением, чтобы иметь возможность использовать SortedList. Если это так, вы должны просто поместить элементы в массив или список и отсортировать их. Методы Array.Sort и List<T>.Sort также могут использовать пользовательский компаратор.

Ваш компаратор со вторичным сравнением можно упростить как:

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