查找給定矢量的最小值

Question

如何有效地找到給定矢量集合中每列的最小值？

例如，請考慮下面的程序：

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <cstdlib> 
using namespace std; 

typedef vector<double> v_t; 

int main(){ 

v_t v1,v2,v3; 

for (int i = 1; i<10; i++){ 
v1.push_back(rand()%10); 
v2.push_back(rand()%10); 
v3.push_back(rand()%10); 
} 

copy(v1.begin(), v1.end(), ostream_iterator<double>(cout, " ")); 
    cout << endl; 
copy(v2.begin(), v2.end(), ostream_iterator<double>(cout, " ")); 
    cout << endl; 
copy(v3.begin(), v3.end(), ostream_iterator<double>(cout, " ")); 
    cout << endl; 
} 

讓輸出是

3 5 6 1 0 6 2 8 2 
6 3 2 2 9 0 6 7 0 
7 5 9 7 3 6 1 9 2 

在這個節目，我想找到的每一列的最小值（3個給出向量）並將其放入矢量中。在這個節目，我想定義一個矢量v_t vfinal，將有值：

3 3 2 1 0 0 1 7 0 

是否有一個有效的方式來做到這一點？我提到效率很高，因爲我的程序可能必須在非常多的向量中找到最小的值。謝謝。

更新：

我試圖用這樣的事情，我在我以前的節目之一用於

int count = std::inner_product(A, A+5, B, 0, std::plus<int>(), std::less<int>()); 

此計算兩個數組A和B之間的最小元素的數量。如果我可以循環使用類似的函數來找到最小值，它會不會足夠有效？我並不是說它可以做或不做。這只是一個可以改進的想法，但我不知道如何。

Answer 1

您可以使用std::transform。循環仍然存在，它們只隱藏在算法內部。要處理的每個額外矢量都是對std::transform的調用。

這是兩個線性過程中的示例問題。

typedef std::vector<double> v_t; 

int main() 
{ 
    v_t v1,v2,v3,vfinal(9); // note: vfinal sized to accept results 

    for (int i = 1; i < 10; ++i) { 
     v1.push_back(rand() % 10); 
     v2.push_back(rand() % 10); 
     v3.push_back(rand() % 10); 
    } 

    std::transform(v1.begin(), v1.end(), v2.begin(), vfinal.begin(), std::min<double>); 
    std::transform(v3.begin(), v3.end(), vfinal.begin(), vfinal.begin(), std::min<double>); 
} 

注：本作品在MSVC++ 2010年，我不得不爲GCC 4.3提供了一個min仿函數。

Answer 2

要找到矢量中的最小數字，只需依次檢查每個元素;至少從算法的角度來看，沒有更快的方法。

在實際性能方面，緩存問題可能影響你在這裏。正如評論中提到的那樣，如果你可以將列向量按列方式存儲而不是按行方式存儲，它可能會更加緩存效率。或者，您可能希望並行執行所有分鐘搜索，以便將緩存未命中最小化。即而不是這樣的：

foreach (col) 
{ 
    foreach (row) 
    { 
     x_min[col] = std::min(x_min[col], x[col][row]); 
    } 
} 

你或許應該這樣做：

foreach (row) 
{ 
    foreach (col) 
    { 
     x_min[col] = std::min(x_min[col], x[col][row]); 
    } 
} 

注意，STL已經提供了一個很好的功能來做到這一點：min_element()。

Answer 3

我認爲你的問題的下界是O(n*m)，其中n是向量的個數和m的每個向量的元素。

我認爲，平凡的算法（比較不同向量的相同索引處的元素）效率是一樣的。

實現它的最簡單方法是將所有的矢量放在一些數據結構中（一個簡單的類C數組，或者一個矢量矢量）。

Answer 4

這樣做的第二種方法是使用矢量矢量，只是簡單的循環。

void find_mins(const std::vector<std::vector<int> >& inputs, std::vector<int>& outputs) 
{ 
    // Assuming that each vector is the same size, resize the output vector to 
    // change the size of the output vector to hold enough. 
    output.resize(inputs[0].size()); 

    for (std::size_t i = 0; i < inputs.size(); ++i) 
    { 
     int min = inputs[i][0]; 
     for (std::size_t j = 1; j < inputs[i].size(); ++j) 
      if (inputs[i][j] < min) min = inputs[i][j]; 
     outputs[i] = min; 
    } 
}