在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慢。