多列並列排序列表<T>

Question

對於List<T>，我需要實現多列排序，其中列名和排序方向在運行時已知。我使用的是System.Linq.Dynamic OrderBy API，它可以採取列名和排序方向連接字符串，因此下面的代碼工作：

List<T> data = DataCollection; // Stored in Cache 
var sortedData = data.OrderBy("Col1 asc, Col2 desc, Col3 asc,Col4 asc"); 

挑戰時的數據增加1 million+記錄的大小，那麼同樣的排序操作減慢顯着，就像沒有魔杖一樣。

現在我想了解在Parallel模式下是否有相同操作的方法。以下是選項，我正在考慮：

選項1：

• 劃分數據收集在較小的子集，例如100 K均和運行在每個排序，但隨後面臨的挑戰是如何合併個人組，在我的理解有沒有方便的機制整合有序子集

選項2

因爲我是覓食的選項，遇到下列並行模式來抓List<int>，其中遞歸併行排序也要求遞歸序列排序內部：

public class CustomSort 
{ 
    // Fetch Partition 
    public static int Partition(List<int> list, int left, int right) 
    { 
     int start = left; 
     int pivot = list[start]; 
     left++; 
     right--; 

     while (true) 
     { 
      while (left <= right && list[left] <= pivot) 
       left++; 

      while (left <= right && list[right] > pivot) 
       right--; 

      if (left > right) 
      { 
       list[start] = list[left - 1]; 
       list[left - 1] = pivot; 

       return left; 
      } 


      int temp = list[left]; 
      list[left] = list[right]; 
      list[right] = temp; 

     } 
    } 

    // Quick Sort serial 
    public static void QuickSort(List<int> list, int left, int right) 
    { 
     if (list == null || list.Count <= 1) 
      return; 

     if (left < right) 
     { 
      int pivotIdx = Partition(list, left, right); 
      QuickSort(list, left, pivotIdx - 1); 
      QuickSort(list, pivotIdx, right); 
     } 
    } 

    // Quick Sort Parallel 
    public static void QuickSortParallel(List<int> list, int left, int right) 
    { 
     if (list == null || list.Count <= 1) 
      return; 

     if (left < right) 
     { 
      int pivotIdx = Partition(list, left, right);   

      Task leftTask = Task.Run(() => QuickSort(list, left, pivotIdx - 1)); 
      Task rightTask = Task.Run(() => QuickSort(list, pivotIdx, right)); 

      Task.WaitAll(new[] { leftTask, rightTask }); 

     } 
    } 
} 

問題：

• 是否有更好的方法來實現相同？
• 對於整數其操作簡單，如何將我的版本的multi column sort，作爲選擇分區將是一個複雜的事情

任何指針，可以讓我正確的道路上

Answer 1

最合理的選擇是從LINQ切換到Parallel LINQ (PLINQ)。

不幸的是，儘管System.Linq.DynamicOrderBy方法的工作，它實際上擊中Enumerable方法重載，因此對ParallelQuery<T>沒有影響這需要結合相應的ParallelEnumerable重載。另外動態LINQ OrderBy實現使用內部類，所以不可能在外部擴展它（無源代碼）。

還存在一個解決方案。您可以使用以下自定義擴展方法。它所做的使用動態LINQ建立一個假的查詢，然後用相應的ParallelEnumerable方法更換順序相關Queryable調用比較簡單ExpressionVisitor：

public static class DynamicPLINQ 
{ 
    public static OrderedParallelQuery<T> OrderBy<T>(this ParallelQuery<T> source, string ordering, params object[] values) 
    { 
     var query = Enumerable.Empty<T>().AsQueryable(); 
     var orderedQuery = query.OrderBy(ordering, values); 
     var binder = new ParallelQueryBinder(); 
     binder.source = query; 
     binder.target = source; 
     var queryExpr = binder.Visit(orderedQuery.Expression); 
     return (OrderedParallelQuery<T>)query.Provider.Execute(queryExpr); 
    } 

    class ParallelQueryBinder : ExpressionVisitor 
    { 
     public object source; 
     public object target; 
     protected override Expression VisitConstant(ConstantExpression node) 
     { 
      if (node.Value == source) 
       return Expression.Constant(target); 
      return base.VisitConstant(node); 
     } 
     protected override Expression VisitUnary(UnaryExpression node) 
     { 
      if (node.NodeType == ExpressionType.Quote) 
       return Visit(node.Operand); 
      return base.VisitUnary(node); 
     } 
     static readonly string[] Methods = { "OrderBy", "OrderByDescending", "ThenBy", "ThenByDescending" }; 
     protected override Expression VisitMethodCall(MethodCallExpression node) 
     { 
      if (node.Method.IsStatic && node.Method.DeclaringType == typeof(Queryable) && Methods.Contains(node.Method.Name)) 
      { 
       var arguments = node.Arguments.Select(Visit).ToArray(); 
       var result = Expression.Call(typeof(ParallelEnumerable), node.Method.Name, node.Method.GetGenericArguments(), arguments); 
       return result; 
      } 
      return base.VisitMethodCall(node); 
     } 
    } 
} 

現在你可以使用PLINQ服務是這樣的：

var sortedData = data.AsParallel() 
    .OrderBy("Col1 asc, Col2 desc, Col3 asc,Col4 asc") 
    .ToList(); 

並比較其性能。