Finding smallest values of given vectors

How can I find the smallest value of each column in the given set of vectors efficiently ?

For example, consider the following program:

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

Let the output be

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 

In this program I want to find the smallest value of every column (of the 3 given vectors) and put it into a vector. In this program I want to define a vector v_t vfinal that will have the values :

3 3 2 1 0 0 1 7 0

Is there an efficient way to do this ? I mention efficient because my program may have to find the smallest values among very large number of vectors. Thank you.

Update:

I'm trying to use something like this which I used in one of my previous programs

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

This counts the number of minimum elements between two arrays A and B. Wouldn't it be efficient enough if I could loop through and use similar kind of function to find the minimal values ? I'm not claiming it can be done or not. It's just an 开发者_如何学编程idea that may be improved upon but I don't know how.

---

You can use std::transform for this. The loops are still there, they're just hidden inside the algorithm. Each additional vector to process is a call to std::transform.

This does your example problem in two linear passes.

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

Note: this works in MSVC++ 2010. I had to provide a min functor for gcc 4.3.

---

I think that the lower bound of your problem is O(n*m), where n is the number of vectors and m the elements of each vector.

The trivial algorithm (comparing the elements at the same index of the different vectors) is as efficient as it can be, I think.

The easiest way to implement it would be to put all your vectors in some data structure (a simple C-like array, or maybe a vector of vectors).

---

The bst way to do this would be to use a vector of vectors, and just simple looping.

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

---

To find the smallest number in a vector, you simply have to examine each element in turn; there's no quicker way, at least from an algorithmic point-of-view.

In terms of practical performance, cache issues may affect you here. As has been mentioned in a comment, it will probably be more cache-efficient if you could store your vectors column-wise rather than row-wise. Alternatively, you may want to do all min searches in parallel, so as to minimise cache misses. i.e. rather than this:

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

you should probably do this:

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

Note that STL already provides a nice function to do this: min_element().