部分排序算法，为什么性能会有这样的差异？

Question

我有一个随机生成的数字列表，其中包含190个数字，我想获得前190个数字的排序列表。我编写了两个版本的部分排序算法，第一个版本是CPU版本，第二个版本是编写的，这样它就可以在Cudafy.net上运行。但是它们之间的执行时间有很大的不同，当在CPU上运行时，我想知道是否有人能解释一下为什么，+可以进一步加快第二个版本的速度吗？

注释：，第二个算法将在GPU上运行，所以我不能使用linq或任何不能在C上运行的东西，因为我将使用cudafy.net来运行代码。不幸的是，cudafy.net也不支持交错数组。

版本1:

/// <summary>
/// Sequentially runs through all the values in the array and identifies if 
/// the current number is less than the highest number in the sorted list.
/// </summary>
/// <param name="numbers"> Unsorted array of numbers.</param>
/// <param name="sortedNumbers"> Array used to hold the partial list of sorted numbers.</param>
public static void NewSorter(int[] numbers, int[] sortedNumbers)
{
    for (int i = 0; i < numbers.Length; i++)
    {
        if (sortedNumbers[sortedNumbers.Length - 1] > numbers[i])
        {
            //Update numbers
            IdentifyPosition(sortedNumbers, numbers[i]);
        }
    }
}

/// <summary>
/// Identifies the position the number should be placed in the partial list of sorted numbers.
/// </summary>
/// <param name="sortedNumbers"> Array used to hold the partial list of sorted numbers.</param>
/// <param name="NewNumber"> Number to be inserted.</param>
static void IdentifyPosition(int[] sortedNumbers, int NewNumber)
{
    for (int i = 0; i < sortedNumbers.Length; i++)
    {
        if (NewNumber < sortedNumbers[i])
        {
            //Offset and add.
            ArrayShifter(sortedNumbers, i, NewNumber);
            break;
        }
    }
}

/// <summary>
/// Moves all the elements to the right of a point up one and 
/// then places the new number in the specified point.
/// </summary>
/// <param name="SortedNumbers"> Array used to hold the partial list of sorted numbers.</param>
/// <param name="position"> Position in the array where the new number should be place.</param>
/// <param name="NewNumber"> Number to include in the array.</param>
static void ArrayShifter(int[] SortedNumbers, int position, int NewNumber)
{
    for (int i = SortedNumbers.Length - 1; i > position; i--)
    {
        SortedNumbers[i] = SortedNumbers[i - 1];
    }

    SortedNumbers[position] = NewNumber;
}

以上版本在~ 0.65毫秒内执行。

版本2:

/// <summary>
/// Sequentially runs through all the values in the array and identifies if 
/// the current number is less than the highest number in the sorted list.
/// </summary>
/// <param name="unsortedNumbers"> Unsorted numbers.</param>
/// <param name="lookbackCount"> Length of the array.</param>
/// <param name="sortedNumbers"> Array which will contain the partial list of sorted numbers.</param>
[Cudafy]
public static void CudaSorter(GThread thread, long[,] unsortedNumbers, int[] lookbackCount, long[,] sortedNumbers)
{
    int threadIndex = thread.threadIdx.x;
    int blockIndex = thread.blockIdx.x;
    int threadsPerBlock = thread.blockDim.x;
    int gpuThread = (threadIndex + (blockIndex * threadsPerBlock));

    if (gpuThread < 32)
    {
        int maxIndex = (lookbackCount[gpuThread] * 10) / 100;
        int maxLookback = lookbackCount[gpuThread];

        for (int i = 0; i < maxLookback; i++)
        {
            if (sortedNumbers[gpuThread, maxIndex] > unsortedNumbers[gpuThread, i])
            {
                //Update numbers
                IdentifyPosition2(sortedNumbers, unsortedNumbers[gpuThread, i], maxIndex, gpuThread);
            }
        }
    }
}


/// <summary>
/// Identifies the position in the sortedNumbers array where the new number should be placed.
/// </summary>
/// <param name="sortedNumbers"> Sorted numbers.</param>
/// <param name="newNumber"> Number to be included in the sorted array.</param>
/// <param name="maxIndex"> length of sortedNumbers array. </param>
/// <param name="gpuThread"> GPU thread index.</param>
[Cudafy(eCudafyType.Device)]
public static void CudaIdentifyPosition(long[,] sortedNumbers, long newNumber, int maxIndex, int gpuThread)
{
    for (int i = 0; i < maxIndex; i++)
    {
        if (newNumber < sortedNumbers[gpuThread, i])
        {
            //Offset and add.
            ArrayShifter2(sortedNumbers, i, newNumber, maxIndex, gpuThread);
            break;
        }
    }
}


/// <summary>
/// Shifts all the elements to the right of the specified position, 1 position
/// to the right, and insert the new number in the specified position.
/// </summary>
/// <param name="sortedNumbers"> Sorted Numbers.</param>
/// <param name="position"> Where the new number needs to be inserted.</param>
/// <param name="newNumber"> New number to insert.</param>
/// <param name="maxIndex"> Length of sortedNumbers array.</param>
/// <param name="gpuThread"> GPU thread index.</param>
[Cudafy(eCudafyType.Device)]
public static void CudaArrayShifter(long[,] sortedNumbers, int position, long newNumber, int maxIndex, int gpuThread)
{
    for (int i = maxIndex - 1; i > position; i--)
    {
        sortedNumbers[gpuThread, i] = sortedNumbers[gpuThread, i - 1];
    }

    sortedNumbers[gpuThread, position] = newNumber;
}

上面的代码在2.8毫秒内执行，即慢了4倍。

我已经尝试过以下几种方法：

1. 为maxLookBack计数声明局部变量，并在for循环=>中使用它，没有改进。
2. 将数据类型从long[,]更改为int[,] => 2.6毫秒(这不可行，因为我需要使用很长的时间)。
3. 将int[,]更改为int[] => 1.3毫秒(这也不可行，因为我需要将多个数组传递给GPU以保持占用)。我很惊讶这对时间有多大的影响。

编辑:由于Henk的评论，i修改了代码。现在我在GPU上使用unsortedNumbers[32,1900]运行GPU版本，而在CPU排序1数组上只运行一个线程。即使我把CPU时间乘以32，它仍然比GPU的时间低得多。

​

​

Answer 1

在这里丢脸之后，我决定读一些关于这项任务的文章，以了解它的意义。

因此，您需要从一个大数组中选择一个最小数目的子数组，然后对其进行排序。最好不要为CPU提供一个选项:在数组中运行，选择低点，然后通过移动元素立即将它们插入最终的数组中。显然，排序将在选择过程中进行。

但是，我无法想象你如何能够并行地采样！此外，您还需要使用良好的并行排序算法.否则，如果按顺序解决任务，则图形核心必然会失去CPU内核的速度，CPU内核的频率更高，数据访问速度更快！

我认为合并排序可以帮你解决这个问题。只是不要取低点，然后排序，尝试排序所有的东西，立即！然后选择N个第一个或最后一个元素。

不幸的是，我现在还没有准备好编辑您的代码。但我希望这至少有一点帮助。