Multi column Параллельная сортировка для списка <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:

• Divide сбор данных в небольших подмножеств как 100 К каждому и запустить Сортировать по каждому, но задача состоит в том, чтобы объединить индивидуальные наборы, в моем понимании есть не удобный механизм не интегрировать отсортированные подмножества

Вариант 2

Как я нагул для вариантов, наткнулся на следующем параллельном шаблоне для List<int>, где рекурсивный Parallel Сортировка также вызывает рекурсивные последовательные сортировать внутренне:

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 перегрузкам. Также реализация Dynamic LINQ OrderBy использует внутренние классы, поэтому ее внешнее расширение (без исходного кода) невозможно.

Все еще существует решение. Вы можете использовать следующий способ расширения. Что она делает это с помощью Dynamic LINQ, чтобы построить поддельный запрос, а затем заменить ордена, связанные Queryable вызовы с соответствующими ParallelEnumerable методы с использованием относительно простой 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(); 

и сравнить производительность.