优化C/Java/任何语言中的代码以提高速度

Question

所以我有两个矩阵，共2N个元素。因此，每个矩阵的长度为1xN。我想要做的是交换它们的元素，使得一个矩阵具有最小的元素，而另一个矩阵具有最大的元素。

以下代码正是如此。但有一个问题，当矩阵的长度超过一定值时，它需要很长时间才能完成。

有没有可能让这段代码运行得更快一些？我真的无法想到任何方法了。max_index和min_index通常也是天真地实现。

对于N = 100万个项目，相对来说还可以，大约需要1.0-1.5分钟，但如果我需要像N = 1000万或更多的项目，则在我的笔记本电脑上永远无法完成。

 while (1) {
        int mini = max_index(other);
        int maxi = min_index(data);
        if (other[mini] > data[maxi]) {
          int temp = other[mini];
          other[mini] = data[maxi];
          data[maxi] = temp;
        } else {
          break;
        }
      }

举个例子以澄清：

other =

    0.5308    0.5458    0.8090    0.8063    0.8874

data =

    0.2901    0.5497    0.9168    0.0882    0.7856

操作后：

other =

    0.5308    0.5458    0.2901    0.5497    0.0882

data =

    0.8090    0.8063    0.9168    0.8874    0.7856

- Mpr. Moe

---

你所说的“一个矩阵具有最小元素，而另一个矩阵具有最大元素”，具体是什么意思？将两个数组合并，对结果进行排序，然后分割成第一和第二部分是否可行？ - Codor

@Codor 我更新了我的原始帖子。 - Mpr. Moe

基数排序是一种在最坏情况下可用的最快速的数字排序算法之一。它的时间复杂度为O(n)。以下是一个实现示例。http://stackoverflow.com/questions/24965564/radix-sort-java-implementation 你需要将两个数组合并，并在最后进行拆分。 - user681574

这是一个冒泡排序吗？你可能想尝试其他排序函数，比如std::sort。 - Thomas Matthews

正如@Codor所说，您需要保持元素的顺序吗？ - hasan

Answer 1

由于没有足够的信息来了解您正在实现哪个算法（需要查看max_index()和min_index()方法才能更具体地评论），因此这变成了一次讨论为什么这需要如此长时间或完全失败。

备忘单：http://bigocheatsheet.com/（请参见数组排序算法）

首先，有时间复杂度。时间复杂度将确定运行此操作所需的计算能力。如果您实现了一个O(n^2)的排序-对于一百万条记录的最坏情况扫描是某个因子乘以1,000,000,000,000或多个万亿次操作。如果您实现了一个O(kn)或O(n)时间复杂度算法-您的操作次数是某个因子乘以一百万。

其次，有空间复杂度。也就是说，在内存中添加了多少方法调用来完成。同样的基本原理也适用于这里，但是不是永远执行，您可能会简单地耗尽内存或开始使用非常糟糕的优化内存缓存-这也会显着增加运行时间。

- user681574

Answer 2

如果您需要保留顺序，或许您可以将两个数组中的所有值求和并取中位数。然后循环遍历每个数组，并通过与中位数比较来将值附加到相应的 belowMedian 或 aboveMedian 的临时数组中。最后只需将您的临时数组交换到原始数组中即可。

- Devin D

---

你不能仅从总和计算中得出中位数，只能得到平均值，而这是不够的。 - chi

啊，那就用快速排序并从中获取中位数吧，这个可能已经被建议过了。 - Devin D

Answer 3

这只需要使用快速选择算法，但需要进行一些小的修改，因为元素不在单个连续数组中。快速选择算法的时间复杂度为O(n)（平均情况下），因为它比排序要少做一些工作。你只需找到第N个元素，它将是第一个数组中的最后一个元素。

标准的C++库提供了nth_element，平均时间复杂度为O(n)，在实践中非常快。但你需要在使用它之前将两个数组都复制到临时数组中，或者编写一个自定义迭代器，使其看起来像两个数组是一个数组。

另外，你可以自己编写算法，同时处理两个数组。

你经常会看到关于快速选择的“中位数中位数”算法用于查找枢轴的参考资料，因为中位数中位数可以提供复杂度保证。尽管如此，在实际应用中，它的开销很大，应该避免使用。它不是快速选择（或快速排序）的一部分。

- rici

---

很好，这正是我想要的。 - Mpr. Moe

Answer 4

首先，我们可以看到您的问题的最大复杂度。将两个集合的元素移动，使较小的元素在一个集合中，而较大的在另一个集合中是一种排序方式。比较排序的最佳复杂度为O(nlogn)。然而，您的答案是O(n²)。

 while (1) {                           // while(true) hides that the loop runs worst-case n times
        int mini = max_index(other);   // finding the max or min-element takes O(n)
        int maxi = min_index(data);
        ... //the rest of the loop is constant-time
      }

执行n复杂度任务的n复杂度循环是O(n²)。

这个问题的朴素方法是对两个集合进行排序，然后通过迭代集合来根据需要交换元素（O(nlogn) + O(n) = O(nlogn)），这是其他答案提出的方法。

sort(begin(data), end(data));
sort(begin(other), end(other));
for(auto i = 0; i < data.size(); ++i)
{
    auto& supposed_to_be_smaller = *(begin(data) + i);
    auto& supposed_to_be_bigger = *(begin(other) + i);
    if (supposed_to_be_smaller <= supposed_to_be_bigger)
         break;
    swap(supposed_to_be_smaller, supposed_to_be_bigger);
}

或者，由于我们实际上并不关心每个集合中的元素是否已排序，因此我们只需要部分排序。我们只关心第一个集合中的元素是否小于第二个集合中的所有元素。幸运的是，C++ STL有一个函数nth_element可以做到这一点（Java不幸的是没有，但实现起来也不应该太难）。nth_element确保集合部分排序，使得第n个元素在排序后的位置上，左边的元素比它小，右边的元素比它大。它的平均时间复杂度为O(n)。两个集合可以在概念上被视为大小加倍的单个集合。你可以简单地将两个集合连接起来，然后进行nth_element操作，最后再将集合拆分。

//combine collections
nth_element(begin(combined), begin(combined) + n, end(combined));
//split collections

更加优雅的做法是，我们可以使用自定义迭代器来同时操作两个集合，让nth_element为我们写入这两个集合。

custom_iter begin_iter{data, other};
nth_element(begin_iter, begin_iter + n, begin_iter + n * 2);

有趣的是，这实际上比更朴素的nth_element要慢。

- apophis42