java - 在 C/Java/任何东西中加速/优化此代码

Question

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

下面的代码就是这样做的。有一个问题，当矩阵超过一定长度时，它需要永远完成。

有没有可能让那段代码更快一点？我现在真的什么也想不起来了。 max_index 和 min_index 通常也是简单的实现。

最多 N=100 万件相对来说没问题，大约需要 1.0-1.5 分钟，但如果我需要像 N=10mill 或更多它永远不会在我的笔记本电脑上完成。

 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

Answer 1

这只需要 Quick Select algorithm ，稍作修改，因为元素不在单个连续数组中。快速选择是 O(n)(平均)，因为它比排序做的工作少。您只需找到元素 N，这将是第一个数组中的最后一个元素。

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

或者，您可以自己编写算法代码，同时处理两个数组。

您会经常看到“中位数中位数”算法的引用，用于查找与快速选择相关的枢轴，因为中位数中位数可以提供复杂性保证。尽管这个理论上有趣的事实，它的开销是巨大的，实际的实现应该避免它。它不是快速的一部分选择(或快速排序)。