c# - 如何有效地对数组进行排序以利用多个 CPU？

Question

我有一个包含 1 亿个条目的未排序列表。RAM 不是问题。我对 List.Sort 的速度并不满意，我想知道是否有一种可靠的技术可以对我的列表进行排序以利用多个处理器。

我查看了 Parallel.Invoke 但无法弄清楚如何实际使用它进行排序，也许它不可能。有任何想法吗？

Answer 1

在另一个 StackOverflow 问题中，我发现了这个：

private void QuicksortSequential<T>(T[] arr, int left, int right)  
where T : IComparable<T> 
{ 
    if (right > left) 
    { 
        int pivot = Partition(arr, left, right); 
        QuicksortSequential(arr, left, pivot - 1); 
        QuicksortSequential(arr, pivot + 1, right); 
    } 
} 

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right)  
where T : IComparable<T> 
{ 
    const int SEQUENTIAL_THRESHOLD = 2048; 
    if (right > left) 
    { 
        if (right - left < SEQUENTIAL_THRESHOLD) 
        { 

            QuicksortSequential(arr, left, right); 
        } 
        else 
        { 
            int pivot = Partition(arr, left, right); 
            Parallel.Do( 
                () => QuicksortParallelOptimised(arr, left, pivot - 1), 
                () => QuicksortParallelOptimised(arr, pivot + 1, right)); 
        } 
    } 
} 

来自同一问题的答案的不同（并且更完整，但不确定“更好”）实现：

/// <summary> 
/// Parallel quicksort algorithm. 
/// </summary> 
public class ParallelSort 
{ 
    #region Public Static Methods 

    /// <summary> 
    /// Sequential quicksort. 
    /// </summary> 
    /// <typeparam name="T"></typeparam> 
    /// <param name="arr"></param> 
    public static void QuicksortSequential<T>(T [] arr) where T : IComparable<T> 
    { 
        QuicksortSequential(arr, 0, arr.Length - 1); 
    } 

    /// <summary> 
    /// Parallel quicksort 
    /// </summary> 
    /// <typeparam name="T"></typeparam> 
    /// <param name="arr"></param> 
    public static void QuicksortParallel<T>(T[] arr) where T : IComparable<T> 
    { 
        QuicksortParallel(arr, 0, arr.Length - 1); 
    } 

    #endregion 

    #region Private Static Methods 

    private static void QuicksortSequential<T>(T[] arr, int left, int right)  
        where T : IComparable<T> 
    { 
        if (right > left) 
        { 
            int pivot = Partition(arr, left, right); 
            QuicksortSequential(arr, left, pivot - 1); 
            QuicksortSequential(arr, pivot + 1, right); 
        } 
    } 

    private static void QuicksortParallel<T>(T[] arr, int left, int right)  
        where T : IComparable<T> 
    { 
        const int SEQUENTIAL_THRESHOLD = 2048; 
        if (right > left) 
        { 
            if (right - left < SEQUENTIAL_THRESHOLD) 
            { 
                QuicksortSequential(arr, left, right); 
            } 
            else 
            { 
                int pivot = Partition(arr, left, right); 
                Parallel.Invoke(new Action[] { delegate {QuicksortParallel(arr, left, pivot - 1);}, 
                                               delegate {QuicksortParallel(arr, pivot + 1, right);} 
                }); 
            } 
        } 
    } 

    private static void Swap<T>(T[] arr, int i, int j) 
    { 
        T tmp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = tmp; 
    } 

    private static int Partition<T>(T[] arr, int low, int high)  
        where T : IComparable<T> 
    { 
        // Simple partitioning implementation 
        int pivotPos = (high + low) / 2; 
        T pivot = arr[pivotPos]; 
        Swap(arr, low, pivotPos); 

        int left = low; 
        for (int i = low + 1; i <= high; i++) 
        { 
            if (arr[i].CompareTo(pivot) < 0) 
            { 
                left++; 
                Swap(arr, i, left); 
            } 
        } 

        Swap(arr, low, left); 
        return left; 
    } 

    #endregion 
}