插入向量变换
Inserting a vector transformation
我之前发布了一个 question 关于 连接 两个 std::vector
的最佳方法,其中必须首先转换一个向量。虽然使用 std::transform
的明显解决方案可能不是理论上的最佳解决方案,但多次容量检查的成本不太可能很大。
但是,如果我们考虑 插入 一个必须转换为另一个向量的更普遍的问题,那么现在可能会涉及大量开销。
执行此操作的最佳方法是什么?
我在这里看到了几个选项:
方法一:临时变换
std::vector<T1> temp {};
temp.reserve(vec.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(temp), op);
vec1.insert(vec1.begin() + pos, std::make_move_iterator(temp.begin()),
std::make_move_iterator(temp.end()));
但现在开销不是微不足道的容量检查,而是额外成本是 temp
的 size_of(T1) * vec2.size()
的 allocation/deallocation。如果 vec2
很大,这很容易成为一项重大成本。
方法二:循环插入
vec1.reserve(vec1.size() + vec2.size());
std::size_t i {pos};
for (const auto& p : vec2) {
vec1.insert(vec1.begin() + i, op);
++i;
}
这避免了方法 1 的额外 allocation/deallocation 但此解决方案还有另一个严重的问题:vec1
中的每个 n = vec1.size() - pos
元素都必须移动 n
次,O(n^2)
次操作。
方法三:移位复制
vec1.resize(vec1.size() + pair_vec.size());
std::move(vec1.begin() + pos, vec1.end(), vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
这似乎接近我们想要的,我们只支付 'extra' n
个默认构造函数。
编辑
我的移位复制方法(3)不正确,应该是:
auto v1_size = vec1.size();
vec1.resize(vec1.size() + vec2.size());
std::move(vec1.begin() + pos, vec1.begin() + v1_size, vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
TESTS(使用@VaughnCato 和@ViktorSehr 的方法更新)
我测试了方法 1 和 3(方法 2 显然不会很好地执行 - 易于验证),以及 @VaughnCato and 建议的方法。这是完整的代码:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstdint>
#include <chrono>
#include <numeric>
#include <random>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/adaptor/transformed.hpp>
using std::size_t;
std::vector<int> generate_random_ints(size_t n)
{
std::default_random_engine generator;
auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
generator.seed((unsigned) seed1);
std::uniform_int_distribution<int> uniform {};
std::vector<int> v(n);
std::generate_n(v.begin(), n, [&] () { return uniform(generator); });
return v;
}
std::vector<std::string> generate_random_strings(size_t n)
{
std::default_random_engine generator;
auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
generator.seed((unsigned) seed1);
std::uniform_int_distribution<int> uniform {};
std::vector<std::string> v(n);
std::generate_n(v.begin(), n, [&] () { return std::to_string(uniform(generator)); });
return v;
}
template <typename D=std::chrono::nanoseconds, typename F>
D benchmark(F f, unsigned num_tests)
{
D total {0};
for (unsigned i = 0; i < num_tests; ++i) {
auto start = std::chrono::system_clock::now();
f();
auto end = std::chrono::system_clock::now();
total += std::chrono::duration_cast<D>(end - start);
}
return D {total / num_tests};
}
template <typename T1, typename T2, typename UnaryOperation>
void temp_transform(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
std::vector<T1> temp {};
temp.reserve(vec2.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(temp), op);
vec1.insert(vec1.begin() + pos, std::make_move_iterator(temp.begin()),
std::make_move_iterator(temp.end()));
}
template <typename T1, typename T2, typename UnaryOperation>
void shift_copy(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
auto v1_size = vec1.size();
vec1.resize(vec1.size() + vec2.size());
std::move(vec1.begin() + pos, vec1.begin() + v1_size, vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
}
template <typename T1, typename T2, typename UnaryOperation>
void boost_transform(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
auto v2_begin = boost::make_transform_iterator(vec2.begin(), op);
auto v2_end = boost::make_transform_iterator(vec2.end(), op);
vec1.insert(vec1.begin() + pos, v2_begin, v2_end);
}
template <typename T1, typename T2, typename UnaryOperation>
void boost_adapter(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
auto transformed_range = vec2 | boost::adaptors::transformed(op);
vec1.insert(vec1.begin() + pos, transformed_range.begin(), transformed_range.end());
}
int main(int argc, char **argv)
{
unsigned num_tests {1000};
size_t vec1_size {1000000};
size_t vec2_size {1000000};
size_t insert_pos {vec1_size / 2};
// Switch the variable names to inverse test
auto vec2 = generate_random_ints(vec1_size);
auto vec1 = generate_random_strings(vec2_size);
//auto op = [] (const std::string& str) { return std::stoi(str); };
auto op = [] (int i) { return std::to_string(i); };
auto f_temp_transform_insert = [&vec1, &vec2, &insert_pos, &op] () {
temp_transform(vec1, vec2, insert_pos, op);
};
auto f_shift_copy_insert = [&vec1, &vec2, &insert_pos, &op] () {
shift_copy(vec1, vec2, insert_pos, op);
};
auto f_boost_transform_insert = [&vec1, &vec2, &insert_pos, &op] () {
boost_transform(vec1, vec2, insert_pos, op);
};
auto f_boost_adapter_insert = [&vec1, &vec2, &insert_pos, &op] () {
boost_adapter(vec1, vec2, insert_pos, op);
};
auto temp_transform_insert_time = benchmark<std::chrono::milliseconds>(f_temp_transform_insert, num_tests).count();
auto shift_copy_insert_time = benchmark<std::chrono::milliseconds>(f_shift_copy_insert, num_tests).count();
auto boost_transform_insert_time = benchmark<std::chrono::milliseconds>(f_boost_transform_insert, num_tests).count();
auto boost_adapter_insert_time = benchmark<std::chrono::milliseconds>(f_boost_adapter_insert, num_tests).count();
std::cout << "temp_transform: " << temp_transform_insert_time << "ms" << std::endl;
std::cout << "shift_copy: " << shift_copy_insert_time << "ms" << std::endl;
std::cout << "boost_transform: " << boost_transform_insert_time << "ms" << std::endl;
std::cout << "boost_adapter: " << boost_adapter_insert_time << "ms" << std::endl;
return 0;
}
结果
编译:
g++ vector_insert.cpp -std=c++11 -O3 -o vector_insert_test
平均用户运行时间为:
| Method | std::string -> int (ms) | int -> std::string (ms) |
|:-----------:|:-----------------------:|:-----------------------:|
| 1 | 68 | 220 |
| 3 | 67 | 222 |
| @VaughnCato | 71 | 239 |
| @ViktorSehr | 72 | 236 |
TLDR
boost
方法不如 std::transform
方法快。
std::transform
方法几乎同样好 - 尽管 int
-> std::string
和 std::string
-> [=28= 之间存在难以解释的差异] 表现。
使用 boost::range::adaptors::transformed 怎么样?
std::vector<...> first_vector;
auto transform_functor = [](...){...};
auto transformed_range = first_vector | boost::adaptors::transformed(transform_functor):
some_vector.insert(some_vector.end(), transformed_range.begin(), transformed_range.end());
鉴于 boost::transform 和 vector::insert 函数的实现尽可能巧妙,这应该能够忽略任何不必要的容量检查。
@VaughnCato 的 approach of using boost::transform_iterator
for your other question 应该也适用于这个:
auto vec1begin = boost::make_transform_iterator(vec1.begin(), f);
auto vec1end = boost::make_transform_iterator(vec1.end(), f);
vec2.insert(middle, vec1begin, vec1end);
我之前发布了一个 question 关于 连接 两个 std::vector
的最佳方法,其中必须首先转换一个向量。虽然使用 std::transform
的明显解决方案可能不是理论上的最佳解决方案,但多次容量检查的成本不太可能很大。
但是,如果我们考虑 插入 一个必须转换为另一个向量的更普遍的问题,那么现在可能会涉及大量开销。
执行此操作的最佳方法是什么?
我在这里看到了几个选项:
方法一:临时变换
std::vector<T1> temp {};
temp.reserve(vec.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(temp), op);
vec1.insert(vec1.begin() + pos, std::make_move_iterator(temp.begin()),
std::make_move_iterator(temp.end()));
但现在开销不是微不足道的容量检查,而是额外成本是 temp
的 size_of(T1) * vec2.size()
的 allocation/deallocation。如果 vec2
很大,这很容易成为一项重大成本。
方法二:循环插入
vec1.reserve(vec1.size() + vec2.size());
std::size_t i {pos};
for (const auto& p : vec2) {
vec1.insert(vec1.begin() + i, op);
++i;
}
这避免了方法 1 的额外 allocation/deallocation 但此解决方案还有另一个严重的问题:vec1
中的每个 n = vec1.size() - pos
元素都必须移动 n
次,O(n^2)
次操作。
方法三:移位复制
vec1.resize(vec1.size() + pair_vec.size());
std::move(vec1.begin() + pos, vec1.end(), vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
这似乎接近我们想要的,我们只支付 'extra' n
个默认构造函数。
编辑
我的移位复制方法(3)不正确,应该是:
auto v1_size = vec1.size();
vec1.resize(vec1.size() + vec2.size());
std::move(vec1.begin() + pos, vec1.begin() + v1_size, vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
TESTS(使用@VaughnCato 和@ViktorSehr 的方法更新)
我测试了方法 1 和 3(方法 2 显然不会很好地执行 - 易于验证),以及 @VaughnCato and
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstdint>
#include <chrono>
#include <numeric>
#include <random>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/adaptor/transformed.hpp>
using std::size_t;
std::vector<int> generate_random_ints(size_t n)
{
std::default_random_engine generator;
auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
generator.seed((unsigned) seed1);
std::uniform_int_distribution<int> uniform {};
std::vector<int> v(n);
std::generate_n(v.begin(), n, [&] () { return uniform(generator); });
return v;
}
std::vector<std::string> generate_random_strings(size_t n)
{
std::default_random_engine generator;
auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
generator.seed((unsigned) seed1);
std::uniform_int_distribution<int> uniform {};
std::vector<std::string> v(n);
std::generate_n(v.begin(), n, [&] () { return std::to_string(uniform(generator)); });
return v;
}
template <typename D=std::chrono::nanoseconds, typename F>
D benchmark(F f, unsigned num_tests)
{
D total {0};
for (unsigned i = 0; i < num_tests; ++i) {
auto start = std::chrono::system_clock::now();
f();
auto end = std::chrono::system_clock::now();
total += std::chrono::duration_cast<D>(end - start);
}
return D {total / num_tests};
}
template <typename T1, typename T2, typename UnaryOperation>
void temp_transform(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
std::vector<T1> temp {};
temp.reserve(vec2.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(temp), op);
vec1.insert(vec1.begin() + pos, std::make_move_iterator(temp.begin()),
std::make_move_iterator(temp.end()));
}
template <typename T1, typename T2, typename UnaryOperation>
void shift_copy(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
auto v1_size = vec1.size();
vec1.resize(vec1.size() + vec2.size());
std::move(vec1.begin() + pos, vec1.begin() + v1_size, vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
}
template <typename T1, typename T2, typename UnaryOperation>
void boost_transform(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
auto v2_begin = boost::make_transform_iterator(vec2.begin(), op);
auto v2_end = boost::make_transform_iterator(vec2.end(), op);
vec1.insert(vec1.begin() + pos, v2_begin, v2_end);
}
template <typename T1, typename T2, typename UnaryOperation>
void boost_adapter(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
auto transformed_range = vec2 | boost::adaptors::transformed(op);
vec1.insert(vec1.begin() + pos, transformed_range.begin(), transformed_range.end());
}
int main(int argc, char **argv)
{
unsigned num_tests {1000};
size_t vec1_size {1000000};
size_t vec2_size {1000000};
size_t insert_pos {vec1_size / 2};
// Switch the variable names to inverse test
auto vec2 = generate_random_ints(vec1_size);
auto vec1 = generate_random_strings(vec2_size);
//auto op = [] (const std::string& str) { return std::stoi(str); };
auto op = [] (int i) { return std::to_string(i); };
auto f_temp_transform_insert = [&vec1, &vec2, &insert_pos, &op] () {
temp_transform(vec1, vec2, insert_pos, op);
};
auto f_shift_copy_insert = [&vec1, &vec2, &insert_pos, &op] () {
shift_copy(vec1, vec2, insert_pos, op);
};
auto f_boost_transform_insert = [&vec1, &vec2, &insert_pos, &op] () {
boost_transform(vec1, vec2, insert_pos, op);
};
auto f_boost_adapter_insert = [&vec1, &vec2, &insert_pos, &op] () {
boost_adapter(vec1, vec2, insert_pos, op);
};
auto temp_transform_insert_time = benchmark<std::chrono::milliseconds>(f_temp_transform_insert, num_tests).count();
auto shift_copy_insert_time = benchmark<std::chrono::milliseconds>(f_shift_copy_insert, num_tests).count();
auto boost_transform_insert_time = benchmark<std::chrono::milliseconds>(f_boost_transform_insert, num_tests).count();
auto boost_adapter_insert_time = benchmark<std::chrono::milliseconds>(f_boost_adapter_insert, num_tests).count();
std::cout << "temp_transform: " << temp_transform_insert_time << "ms" << std::endl;
std::cout << "shift_copy: " << shift_copy_insert_time << "ms" << std::endl;
std::cout << "boost_transform: " << boost_transform_insert_time << "ms" << std::endl;
std::cout << "boost_adapter: " << boost_adapter_insert_time << "ms" << std::endl;
return 0;
}
结果
编译:
g++ vector_insert.cpp -std=c++11 -O3 -o vector_insert_test
平均用户运行时间为:
| Method | std::string -> int (ms) | int -> std::string (ms) |
|:-----------:|:-----------------------:|:-----------------------:|
| 1 | 68 | 220 |
| 3 | 67 | 222 |
| @VaughnCato | 71 | 239 |
| @ViktorSehr | 72 | 236 |
TLDR
boost
方法不如std::transform
方法快。std::transform
方法几乎同样好 - 尽管int
->std::string
和std::string
-> [=28= 之间存在难以解释的差异] 表现。
使用 boost::range::adaptors::transformed 怎么样?
std::vector<...> first_vector;
auto transform_functor = [](...){...};
auto transformed_range = first_vector | boost::adaptors::transformed(transform_functor):
some_vector.insert(some_vector.end(), transformed_range.begin(), transformed_range.end());
鉴于 boost::transform 和 vector::insert 函数的实现尽可能巧妙,这应该能够忽略任何不必要的容量检查。
@VaughnCato 的 approach of using boost::transform_iterator
for your other question 应该也适用于这个:
auto vec1begin = boost::make_transform_iterator(vec1.begin(), f);
auto vec1end = boost::make_transform_iterator(vec1.end(), f);
vec2.insert(middle, vec1begin, vec1end);