Toute implémentation de tri multicœur dans .NET?

Question

Toute implémentation de tri multicœur dans .NET?

Answer 1

Voici un QuickSort multithread que j'ai assemblé il y a quelques temps en utilisant async/await. Sous une certaine taille de tri, il «revient» à une sorte élémentaire connue sous le nom de sélection à deux extrémités. Sort:

public static class SortExtensions 
{ 
    /// <summary> 
    /// Sorts the list. 
    /// </summary> 
    /// <typeparam name="T"> 
    /// The IComparable element type of the list. 
    /// </typeparam> 
    /// <param name="list">The list to sort.</param> 
    public static async Task SortIt<T>(this IList<T> list) where T : IComparable<T> => 
     await SortIt(list, 0, list.Count - 1); 

    /// <summary> 
    /// Sorts the list. 
    /// </summary> 
    /// <typeparam name="T">The element type of the list.</typeparam> 
    /// <param name="list">The list to sort.</param> 
    /// <param name="lowerbound">The lower bound.</param> 
    /// <param name="upperbound">The upper bound.</param> 
    private static async Task SortIt<T>(
     this IList<T> list, 
     int lowerbound, 
     int upperbound) where T : IComparable<T> 
    { 
     // If list is non-existent or has zero or one element, no need to sort, so exit. 
     if ((list == null) || (upperbound - lowerbound < 1)) 
     { 
      return; 
     } 

     const int MinListLength = 6; 

     if (upperbound - lowerbound > MinListLength) 
     { 
      await list.QuickSort(lowerbound, upperbound); 
      return; 
     } 

     await list.DoubleEndedSelectionSort(lowerbound, upperbound); 
    } 

    /// <summary> 
    /// QuickSorts the list. 
    /// </summary> 
    /// <typeparam name="T">The element type of the list.</typeparam> 
    /// <param name="list">The list to sort.</param> 
    /// <param name="lowerbound">The lower bound.</param> 
    /// <param name="upperbound">The upper bound.</param> 
    private static async Task QuickSort<T>(
     this IList<T> list, 
     int lowerbound, 
     int upperbound) where T : IComparable<T> 
    { 
     int left = lowerbound; 
     int right = upperbound; 
     int middle = (lowerbound + upperbound) >> 1; 
     int pivotindex = (list[lowerbound].CompareTo(list[middle]) <= 0) 
      && (list[middle].CompareTo(list[upperbound]) <= 0) 
      ? middle 
      : ((list[middle].CompareTo(list[lowerbound]) <= 0) 
       && (list[lowerbound].CompareTo(list[upperbound]) <= 0) 
       ? lowerbound 
       : upperbound); 
     T pivotvalue = list[pivotindex]; 

     do 
     { 
      while ((left < upperbound) && (list[left].CompareTo(pivotvalue) < 0)) 
      { 
       left++; 
      } 

      while ((right > lowerbound) && (list[right].CompareTo(pivotvalue) > 0)) 
      { 
       right--; 
      } 

      if (left > right) 
      { 
       continue; 
      } 

      (list[left], list[right]) = (list[right], list[left]); 
      left++; 
      right--; 
     } 
     while (right > left); 

     if (lowerbound < right) 
     { 
      await list.SortIt(lowerbound, right); 
     } 

     if (left < upperbound) 
     { 
      await list.SortIt(left, upperbound); 
     } 
    } 

    /// <summary> 
    /// Double-ended selection sorts the list. 
    /// </summary> 
    /// <typeparam name="T">The element type of the list.</typeparam> 
    /// <param name="list">The list to sort.</param> 
    /// <param name="lowerbound">The lower bound.</param> 
    /// <param name="upperbound">The upper bound.</param> 
    private static async Task DoubleEndedSelectionSort<T>(
     this IList<T> list, 
     int lowerbound, 
     int upperbound) where T : IComparable<T> 
    { 
     // Initialize some working variables that will hold the sortable sublist indices. 
     int left = lowerbound; 
     int right = upperbound; 

     // Keep sorting the list while the upper bound of the sublist is greater than the lower bound. 
     while (right > left) 
     { 
      // Find get the indices of the smallest and largest elements of the sublist. 
      (int smallest, int largest) = await list.FindSmallestAndLargest(left, right); 

      if (smallest != largest) 
      { 
       // If they're different elements, swap the smallest with left element of the sublist. 
       (list[left], list[smallest]) = (list[smallest], list[left]); 
       if (largest == left) 
       { 
        // If the largest element of the sublist was the left element, then now, it has to be the 
        // smallest due to the swap. 
        largest = smallest; 
       } 
      } 

      if (largest != right) 
      { 
       // If the largest element of the sublist is the rightmost element, then they need to be swapped. 
       (list[right], list[largest]) = (list[largest], list[right]); 
      } 

      // Move the sublist search indices one in from the left and the right. 
      left++; 
      right--; 
     } 
    } 

    /// <summary> 
    /// Finds the smallest and largest list element indices. 
    /// </summary> 
    /// <typeparam name="T">The element type of the list.</typeparam> 
    /// <param name="list">The list to search.</param> 
    /// <param name="lowerbound">The lower bound.</param> 
    /// <param name="upperbound">The upper bound.</param> 
    private static async Task<(int, int)> FindSmallestAndLargest<T>(
     this IList<T> list, 
     int lowerbound, 
     int upperbound) where T : IComparable<T> 
    { 
     int smallest = (list[lowerbound].CompareTo(list[upperbound]) < 0) ? lowerbound : upperbound; 
     int largest = (list[lowerbound].CompareTo(list[upperbound]) < 0) ? upperbound : lowerbound; 

     lowerbound++; 

     int loop = upperbound; 

     while (loop > lowerbound) 
     { 
      loop--; 
      if (list[loop].CompareTo(list[smallest]) < 0) 
      { 
       smallest = loop; 
      } 

      if (list[loop].CompareTo(list[largest]) > 0) 
      { 
       largest = loop; 
      } 
     } 

     return (smallest, largest); 
    } 
} 

Answer 2

Cochez cette case parallel extensions version of quicksort à partir d'une réponse précédente.

Answer 3

Il y a un article intéressant sur CodeProject qui décrit un algorithme utilisant le cadre TPL:

http://www.codeproject.com/KB/recipes/parallelSort.aspx.