1

我有选择排序功能

inline void selection_sort(double* arrayPtr, int length_array)
{
    for (auto i = 0; i < length_array; i++)
    {
        for (auto j = i + 1; j < length_array; j++)
        {
            if (arrayPtr[i] > arrayPtr[j])
            {
                std::swap(arrayPtr[i], arrayPtr[j]);
            }
        }
    }
}

如何使用多线程对其进行优化？

我找到了仅用于快速排序的解决方案，但这些解决方案对我没有帮助。

4

2 回答 2

3

如何使用多线程对其进行优化？我找到了仅用于快速排序的解决方案，但这些解决方案对我没有帮助。

您找不到太多关于它的信息，因为这样做不是一个好主意。效率不高，选择排序的并行化与插入排序的并行化有一些相同的问题。即，此代码：

for (auto i = 0; i < length_array; i++)
{
    for (auto j = i + 1; j < length_array; j++)
    {
        if (arrayPtr[i] > arrayPtr[j])
        {
            std::swap(arrayPtr[i], arrayPtr[j]);
        }
    }
}

由于与内循环的相互依赖性，您无法有效地并行化外循环。因此，您已经受限于并行任务的数量及其粒度。然后你在交换阶段遇到了数据依赖问题，你还需要解决这个问题，这也会影响并行版本的加速。

由于其分而治之的性质，诸如合并排序之类的算法更可并行化（即，它们的并行化产生更好的加速），其中可以并行化递归调用。

尽管如此，您可以在stackoverflow中找到OpenMP/C++ 中选择排序的并行版本。话虽如此，代码运行是并行的，但我怀疑没有太多（如果有的话）加速。

于 2021-02-18T10:11:05.460 回答
1

免责声明：这仅适用于家庭作业要求。出于所有实际目的std::sort，更好。

假设要求是必须执行精确的一组操作，但是可以以任何顺序执行独立的操作。

注意：

  • 有 length_array通过数组的通道（由 索引i）
  • 每次通过都必须按顺序完成。
  • 但是，请注意（非正式地）第二遍的前半部分独立于第一遍的后半部分，只要完成第一遍的前半部分，两者都可以按任何顺序完成。

因此解决问题的一种可能方法是（非常小心偏移错误，你必须弄清楚细节）

  • 让线程 1 处理第一遍的前半部分。
  • 等待两个线程完成当前步骤。
  • 让线程 1 处理第一遍的后半部分，而线程 2 并发处理第二遍的前半部分。
  • 等待两个线程完成当前步骤。
  • 让线程 1 处理第二遍的后半部分，而线程 2 并发处理第三遍的前半部分。
  • 等待两个线程完成当前步骤。
  • 重复。
  • 特殊情况最后一次通过。
  • 以某种方式处理偏移量。
于 2021-02-18T10:08:01.177 回答