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

本文关键字：CPU 排序 有效地 数组 | 更新日期: 2023-09-27 18:34:26

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

我看了 Parallel.Invoke，但不知道如何实际使用它进行排序，也许它不可能。有什么想法吗？

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

在另一个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 
}
相关文章：