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

Question

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

以下代码确实如此。有一个问题，当矩阵超过一定长度时，需要永远完成。

是否有可能让这段代码更快一点？我现在真的想不出什么。 max_index和min_index也通常是天真的实施。

高达N = 1百万项目它相对好，大约需要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），在实践中非常快。但是在使用前需要将两个数组复制到一个临时数组，或者写一个自定义迭代器，使其看起来像两个数组。

或者，您可以自己编写算法，同时在两个阵列上工作。

由于中位数可以提供复杂性保证，因此您会经常看到引用“median-of-medians”算法以查找与快速选择相关的数据透视表。尽管这个理论上有趣的事实，它的开销是巨大的，实际应用应该避免它。它不是快速 select（或quicksort）的一部分。

Answer 2

由于没有关于您实现足够的信息来准确地了解你正在实施的算法（会需要查看max_index（）和min_index（）方法以更具体地进行评论），这变成了讨论为什么这么长时间或完全失败。

小抄：http://bigocheatsheet.com/（参见数组排序算法）

首先，有时间复杂度。时间复杂性将决定运行此操作所需的计算能力的数量。如果你已经实现了一种O（n^2）的排序，那么对于一百万条记录来说，最糟糕的情况就是1,000,000,000,000倍或几万亿次操作。如果您已经实现了O（kn）或O（n）时间复杂度算法 - 您的操作次数达到了一百万倍。

二，有空间复杂性。也就是说，将多少个方法调用添加到您的堆栈以在内存中完成。相同的基本前提在这里适用，但相反，永远不会，你可能只是用完内存或开始使用非常优化的内存缓存 - 这也会显着增加您的运行时间。

Answer 3

如果您确实需要保存顺序，也许您可​​以将两个数组中的所有值相加并取中位数。然后循环遍历每个数组，并通过与您的中位数进行比较，根据需要附加到Media或aboveMedian下的临时数组。然后，将您的临时阵列交换为原始阵列。

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复杂环是O（n 2 ）。

这个问题的天真方法是对两个集合进行排序，然后根据需要通过遍历集合（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有一个这样做的函数（不幸的是，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慢。