Нахождение наименьших значений заданных векторов

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. Мне пришлось предоставить функтор min для gcc 4.3.

Answer 2

Я думаю, что нижняя граница вашей задачи - O(n*m), где n - количество векторов и m элементы каждого вектора.

Тривиальный алгоритм (сравнение элементов водин и тот же индекс разных векторов) настолько эффективен, насколько это возможно, я думаю.

Самый простой способ реализовать это - поместить все ваши векторы в некоторую структуру данных (простой C-подобный массив,или, может быть, вектор векторов).

Answer 3

Лучший способ сделать это - использовать вектор векторов и просто выполнить цикл.

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

Answer 4

Чтобы найти наименьшее число в векторе, вам просто нужно изучить каждый элемент по очереди;нет более быстрого пути, по крайней мере, с алгоритмической точки зрения.

С точки зрения практической производительности проблемы с кэшем могут затронуть вас здесь.Как уже упоминалось в комментарии, вероятно, будет более эффективным использование кеша, если вы сможете хранить свои векторы по столбцам, а не по строкам.В качестве альтернативы вы можете выполнить все минимальные поиски параллельно, чтобы минимизировать потери в кеше.т.е. вместо этого:

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().