C# 比 SortedList<> 更快的排序方法是什么？

Question

我们有一个

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

我们在模拟中使用的资源清单是这样初始化的，因为我们希望随时传递不同的比较器。我们面临的第一个问题是，SortedList<>需要在比较器内部进行额外的比较，以便我们可以添加具有相同属性的不同Resource实例。例如，如果比较器如下所示：

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<> 更快的方式来排序大量对象？

- Dimitris

---

有多少不同的优先级？ - user180326

优先级的数量是由用户定义的。它可以是3个也可以是10个，这取决于所使用的模型。 - Dimitris

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)而不是SortedList<TKey, TValue>的O(n)。
• 如果列表从已排序的数据一次性填充，则SortedList<TKey, TValue>比SortedDictionary<TKey, TValue>更快。

- Jon Skeet

Answer 2

是否需要在任何时候都对列表进行排序？如果不需要，只在需要时进行排序肯定会更快。另一个想法是使用“OrderPriority”进行排序，它是优先级和ID字段的组合，因此只需要进行一次比较：

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

这个假设是基于ID不会太大的前提...

- Alex Lo

---

Resource 实例列表必须一直排序。 Id 字段只是一个示例，它可以是一个字符串，并且还有更多属性可用于排序。 - Dimitris

我觉得你已经把问题限制得无法取得任何进展了。如果你现在必须按照目前的方式来做事，我没有看到太多其他选择。 - Alex Lo

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

- user180326

Answer 4

如果您不关心区分具有相同优先级的对象，为什么不使用一个桶（可能实现为队列）的 SortedList，将所有相同优先级的项目放在同一个桶中呢？

- RyanHennig

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

- Guffa

---

Resource实例列表必须始终保持排序。因此，当您添加一个资源时，为了模拟目的，列表必须进行排序。 - Dimitris

@Dimitris：但是您说过您想随时更改比较器？一旦创建了SortedList，您无法更改它的比较器。 - Guffa

抱歉，我之前没有澄清。这个列表包含在许多其他对象中，每个对象都需要自己的比较器来定义。 - Dimitris