Каков наиболее эффективный и стандартный (С++ 11/14) способ найти элемент max/min вектора векторов?
std::vector<std::vector<double>> some_values{{5,0,8},{3,1,9}};
требуемый максимальный элемент 9
искомый минимальный элемент 0
Любой эффективный способ вычисления максимального элемента в двумерном массиве (или векторе в вашем случае) включает в себя сложность O(n^2), независимо от того, что вы делаете, поскольку расчет включает сравнение между n*n элементами .Best путь с точки зрения простоты использования заключается в использовании std::max_element для вектора векторов. Я не буду углубляться в детали. Вот ссылка .
Здесь многопоточное решение, которое возвращает итератор (или бросает) до максимального для общего типа T (предполагается, что operator< определено для T). Обратите внимание, что наиболее важная оптимизация заключается в выполнении внутренних максимальных операций в "столбцах", чтобы использовать упорядочение столбцов в С++.
#include <vector>
#include <algorithm>
template <typename T>
typename std::vector<T>::const_iterator max_element(const std::vector<std::vector<T>>& values)
{
if (values.empty()) throw std::runtime_error {"values cannot be empty"};
std::vector<std::pair<typename std::vector<T>::const_iterator, bool>> maxes(values.size());
threaded_transform(values.cbegin(), values.cend(), maxes.begin(),
[] (const auto& v) {
return std::make_pair(std::max_element(v.cbegin(), v.cend()), v.empty());
});
auto it = std::remove_if(maxes.begin(), maxes.end(), [] (auto p) { return p.second; });
if (it == maxes.begin()) throw std::runtime_error {"values cannot be empty"};
return std::max_element(maxes.begin(), it,
[] (auto lhs, auto rhs) {
return *lhs.first < *rhs.first;
})->first;
}
threaded_transform не входит в стандартную библиотеку (пока), но здесь вы можете использовать реализацию.
#include <vector>
#include <thread>
#include <algorithm>
#include <cstddef>
template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
OutputIterator threaded_transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op, unsigned num_threads)
{
std::size_t num_values_per_threads = std::distance(first, last) / num_threads;
std::vector<std::thread> threads;
threads.reserve(num_threads);
for (int i = 1; i <= num_threads; ++i) {
if (i == num_threads) {
threads.push_back(std::thread(std::transform<InputIterator,
OutputIterator, UnaryOperation>,
first, last, result, op));
} else {
threads.push_back(std::thread(std::transform<InputIterator,
OutputIterator, UnaryOperation>,
first, first + num_values_per_threads,
result, op));
}
first += num_values_per_threads;
result += num_values_per_threads;
}
for (auto& thread : threads) thread.join();
return result;
}
template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
OutputIterator threaded_transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op)
{
return threaded_transform<InputIterator, OutputIterator, UnaryOperation>(first, last, result, op, std::thread::hardware_concurrency());
}
Если вы использовали boost::multi_array<double, 2> вместо std::vector<std::vector<double>>, это было бы так же просто, как:
auto minmax = std::minmax_element(values.data(), values.data() + values.num_elements());
Вы должны, по крайней мере, посмотреть на каждый элемент, так как, как упоминала Anony-mouse, сложность будет как минимум O (n ^ 2).
#include <vector>
#include <limits>
#include <algorithm>
int main() {
std::vector<std::vector<double>> some_values;
double max = std::numeric_limits<double>::lowest();
for (const auto& v : some_values)
{
double current_max = *std::max_element(v.cbegin(), v.cend());
max = max < current_max ? current_max : max; // max = std::max(current_max, max);
}
}
Если вы создадите пользовательский итератор для повторения всех double вашего vector из vector, простой std::minmax_element выполнит задание
выглядит примерно так:
class MyIterator : public std::iterator<std::random_access_iterator_tag, double>
{
public:
MyIterator() : container(nullptr), i(0), j(0) {}
MyIterator(const std::vector<std::vector<double>>& container,
std::size_t i,
std::size_t j) : container(&container), i(i), j(j)
{
// Skip empty container
if (i < container.size() && container[i].empty())
{
j = 0;
++(*this);
}
}
MyIterator(const MyIterator& rhs) = default;
MyIterator& operator = (const MyIterator& rhs) = default;
MyIterator& operator ++() {
if (++j >= (*container)[i].size()) {
do {++i;} while (i < (*container).size() && (*container)[i].empty());
j = 0;
}
return *this;
}
MyIterator operator ++(int) { auto it = *this; ++(*this); return it; }
MyIterator& operator --() {
if (j-- == 0) {
do { --i; } while (i != 0 && (*container)[i].empty());
j = (*container)[i].size();
}
return *this;
}
MyIterator operator --(int) { auto it = *this; --(*this); return it; }
double operator *() const { return (*container)[i][j]; }
bool operator == (const MyIterator& rhs) const {
return container == rhs.container && i == rhs.i && j == rhs.j;
}
bool operator != (const MyIterator& rhs) const { return !(*this == rhs); }
private:
const std::vector<std::vector<double>>* container;
std::size_t i;
std::size_t j;
};
И использование может быть
// Helper functions for begin/end
MyIterator MyIteratorBegin(const std::vector<std::vector<double>>& container)
{
return MyIterator(container, 0, 0);
}
MyIterator MyIteratorEnd(const std::vector<std::vector<double>>& container)
{
return MyIterator(container, container.size(), 0);
}
int main() {
std::vector<std::vector<double>> values = {{5,0,8}, {}, {3,1,9}};
auto b = MyIteratorBegin(values);
auto e = MyIteratorEnd(values);
auto p = std::minmax_element(b, e);
if (p.first != e) {
std::cout << "min is " << *p.first << " and max is " << *p.second << std::endl;
}
}
Используя функцию accumulate, вы можете написать:
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<std::vector<double>> m{ {5, 0, 8}, {3, 1, 9} };
double x = std::accumulate(m.begin(), m.end(), m[0][0],
[](double max, const std::vector<double> &v)
{
return std::max(max,
*std::max_element(v.begin(),
v.end()));
});
std::cout << x << '\n';
return 0;
}
но я бы предпочел хороший, старый для цикла.
Пример может быть расширен, чтобы найти как минимальные, так и максимальные значения:
std::accumulate(m.begin(), m.end(),
std::make_pair(m[0][0], m[0][0]),
[](std::pair<double, double> minmax, const std::vector<double> &v)
{
auto tmp(std::minmax_element(v.begin(), v.end()));
return std::make_pair(
std::min(minmax.first, *tmp.first),
std::max(minmax.second, *tmp.second));
});
К сожалению, вектор вектора не сохраняется последовательно в памяти, поэтому у вас нет ни одного блока, содержащего все значения (это одна из причин, по которой вектор вектора не является хорошей моделью для матрицы).
Вы можете воспользоваться вектором вектора, если он содержит много элементов.
Поскольку каждый суб-вектор является автономным, вы можете использовать std:: async для асинхронного ввода вектора фьючерсов, содержащих максимальное значение каждого суб-вектор.
Вы можете сделать это довольно легко с помощью Eric Niebler range-v3 библиотека (которая, очевидно, еще не стандартная, но, надеюсь, будет в не слишком отдаленное будущее):
vector<vector<double>> some_values{{5,0,8},{3,1,9}};
auto joined = some_values | ranges::view::join;
auto p = std::minmax_element(joined.begin(), joined.end());
p.first является итератором для элемента min; p.second до макс.
(range-v3 имеет реализацию minmax_element, но, к сожалению, для него требуется ForwardRange, а view:: join дает мне InputRange, поэтому я не могу его использовать.)
Простой способ for loop:
T max_e = std::numeric_limits<T>::min();
for(const auto& v: vv) {
for(const auto& e: v) {
max_e = std::max(max_e, e);
}
}
Простейшим методом было бы сначала иметь функцию для определения элементов max/min одного вектора, например, функцию, называемую:
double getMaxInVector(const vector<double>& someVec){}
Передача по ссылке (только для чтения) в этом случае будет намного больше времени и пространства (вы не хотите, чтобы ваша функция копировала весь вектор). Таким образом, в вашей функции для определения максимального/минимального элемента вектора векторов вы должны иметь вложенный цикл, например:
for(size_t x= 0; x < some_values.size(); x++){
for(size_t y = 0; y < x.size(); y++){
// y represents the vectors inside the vector of course
// current max/min = getMax(y)
// update max/min after inner loop finishes and x increments
// by comparing it with previous max/min
Проблема с приведенным выше решением заключается в его неэффективности. Насколько мне известно, этот алгоритм, как правило, работает на эффективность O (n ^ 2log (n)), что весьма неудивительно. Но, конечно, это решение. Несмотря на то, что могут быть стандартные алгоритмы, которые могут найти максимальный/минимальный вектор для вас, он всегда более эффективен для написания собственного, и использование данных обычно не делает ничего с точки зрения повышения эффективности, поскольку алгоритм будет в общем случае одинаковым ( для малых функций, определяющих max/min). Фактически, теоретически, стандартные функции выполнялись бы незначительно медленнее, поскольку эти функции являются шаблонами, которые должны определять тип, с которым он имеет дело во время выполнения.
Предположим, что у нас есть вектор с именем some_values , как показано ниже
7 4 2 0
4 8 10 8
3 6 7 6
3 9 19* 14
определяют одномерный вектор, как показано ниже
vector<int> oneDimVector;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
oneDimVector.push_back(some_values[i][j]);
}
}
Затем найдите элемент максимума/минимума в этом одномерном векторе, как показано ниже
vector<int>::iterator maxElement = max_element(oneDimVector.begin(),oneDimVector.end());
vector<int>::iterator minElement = min_element(oneDimVector.begin(),oneDimVector.end());
Теперь вы получаете максимальные/минимальные элементы, как показано ниже
cout << "Max element is " << *maxElement << endl;
cout << "Min element is " << *minElement << endl;
vector<vector<int>> vv = { vector<int>{10,12,43,58}, vector<int>{10,14,23,18}, vector<int>{28,47,12,90} };
vector<vector<int>> vv1 = { vector<int>{22,24,43,58}, vector<int>{56,17,23,18}, vector<int>{11,12,12,90} };
int matrix1_elem_sum=0;
int matrix2_elem_sum = 0;
for (size_t i = 0; i < vv.size(); i++)
{
matrix1_elem_sum += std::accumulate(vv[i].begin(), vv[i].end(), 0);
matrix2_elem_sum += std::accumulate(vv1[i].begin(), vv1[i].end(), 0);
}
cout << matrix1_elem_sum <<endl;
cout << matrix2_elem_sum << endl;
int summ = matrix1_elem_sum + matrix2_elem_sum;
cout << summ << endl;
или оптимальный вариант:
vector<vector<int>> vv = { vector<int>{10,12,43,58}, vector<int>{10,14,23,18}, vector<int>{28,47,12,90} };
vector<vector<int>> vv1 = { vector<int>{22,24,43,58}, vector<int>{56,17,23,18}, vector<int>{11,12,12,90} };
int summ=0;
int matrix2_elem_sum = 0;
for (size_t i = 0; i < vv.size(); i++)
{
summ += std::accumulate(vv[i].begin(), vv[i].end(), 0)+ std::accumulate(vv1[i].begin(), vv1[i].end(), 0);
}
cout << summ << endl;
}