查找给定矢量的最小值

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; 
    } 
}