C++中实现向量特定更改的最快方法

Question

我想要复制一个向量，同时将其中一个元素的属性设置为零。我有一个std::vector<PLY>向量，其中包含特定数量的以下结构体元素：

struct PLY{
    float x;
    float y;
    float z;
}

如何最快地创建此向量的副本，其中每个PLY元素的 z值 为 0 ？是否存在更快速的方法，而不是创建向量的副本，然后迭代每个元素以设置新的z值？

- Kevin Katzke

---

如果您定义一个默认构造函数并将每个元素初始化为0，那么仅定义具有初始大小的向量将使每个结构元素默认为0。 - EdChum

PLY()：x（0），y（0），z（0）将此默认构造函数添加到您的结构体中。 - Samer Tufail

Answer 1

你可以使用 std::transform：

std::vector<PLY> zeroed{};
zeroed.reserve(other_vec.size()); //pre-allocate the storage
std::transform(other_vec.begin(), other_vec.end(), std::back_inserter(zeroed), 
           [](auto e){ e.z = 0.f; return e; });   

- TartanLlama

---

应该是：std::back_inserter(zeroed)，你只调用了 reserve，而没有调用 resize。 - PaulMcKenzie

只是想知道，rvalue引用是必要的吗？lvalue引用不行吗？ - user1810087

@user1810087 这不是一个 rvalue 引用，而是由于类型推导而产生的转发引用。在这种情况下，它并没有什么区别，但它是处理这种类型事情最通用的方式，因为它将处理代理对象。 - TartanLlama

那样做不会改变other_vec中的值吗？类型推断将推断出左值引用，然后您将把z设置为0。看起来OP想保留原始向量中的值不变。 - Revolver_Ocelot

@Revolver_Ocelot 哇，今天我真的很厉害</sarcasm>。问题已解决。 - TartanLlama

在测试中（如上所述），令我非常失望的是，std::transform 是迄今为止最慢的方法。 :( - Richard Hodges

Answer 2

第一个答案

测试它。内存架构有时会产生奇怪的效果。

#include <iostream>
#include <chrono>
#include <vector>
#include <iomanip>
#include <algorithm>

struct PLY
{
    PLY() : x(0), y(0), z(0) {}
    PLY(float x, float y, float z) : x(x), y(y), z(z) {}
    float x, y , z;
};



template<class F>
std::vector<PLY> test(const char* name, std::vector<PLY> samples, F f)
{
    using namespace std::literals;
    std::vector<PLY> result;
    result.reserve(samples.size());

    auto start = std::chrono::high_resolution_clock::now();

    f(result, samples);

    auto end = std::chrono::high_resolution_clock::now();

    using fns = std::chrono::duration<long double, std::chrono::nanoseconds::period>;
    using fms = std::chrono::duration<long double, std::chrono::milliseconds::period>;
    using fs = std::chrono::duration<long double, std::chrono::seconds::period>;

    auto interval = fns(end - start);
    auto time_per_sample = interval / samples.size();
    auto samples_per_second = 1s / time_per_sample;

    std::cout << "testing " << name << '\n';
    std::cout << " sample size        : " << samples.size() << '\n';
    std::cout << " time taken         : " << std::fixed << fms(interval).count() << "ms\n";
    std::cout << " time per sample    : " << std::fixed << (interval / samples.size()).count() << "ns\n";
    std::cout << " samples per second : " << std::fixed << samples_per_second << "\n";

    return result;
}

struct zero_z_iterator : std::vector<PLY>::const_iterator
{
    using base_class = std::vector<PLY>::const_iterator;
    using value_type = PLY;

    using base_class::base_class;

    value_type operator*() const {
        auto const& src = base_class::operator*();
        return PLY{ src.x, src.y, 0.0 };
    }
};

int main()
{

    test("transform", std::vector<PLY>(1000000), [](auto& target, auto& source)
         {
             std::transform(source.begin(), source.end(),
                            std::back_inserter(target),
                            [](auto& ply) {
                                return PLY { ply.x, ply.y, ply.z };
                            });
         });

    test("copy and reset z", std::vector<PLY>(1000000), [](auto& target, auto& source)
         {
             std::copy(source.begin(), source.end(),
                       std::back_inserter(target));
             for (auto& x : target)
             {
                 x.z = 0;
             }
         });

    test("hand_roll", std::vector<PLY>(1000000), [](auto& target, auto& source)
         {
             for(auto& x : source) {
                 target.emplace_back(x.x, x.y, 0.0);
             }
         });

    test("assign through custom iterator", std::vector<PLY>(1000000), [](auto& target, auto& source)
         {
             target.assign(zero_z_iterator(source.begin()),
                                           zero_z_iterator(source.end()));
         });


    test("transform", std::vector<PLY>(100000000), [](auto& target, auto& source)
         {
             std::transform(source.begin(), source.end(),
                            std::back_inserter(target),
                            [](auto& ply) {
                                return PLY { ply.x, ply.y, ply.z };
                            });
         });

    test("copy and reset z", std::vector<PLY>(100000000), [](auto& target, auto& source)
         {
             std::copy(source.begin(), source.end(),
                       std::back_inserter(target));
             for (auto& x : target)
             {
                 x.z = 0;
             }
         });

    test("hand_roll", std::vector<PLY>(100000000), [](auto& target, auto& source)
         {
             for(auto& x : source) {
                 target.emplace_back(x.x, x.y, 0.0);
             }
         });

    test("assign through custom iterator", std::vector<PLY>(100000000), [](auto& target, auto& source)
         {
             target.assign(zero_z_iterator(source.begin()),
                           zero_z_iterator(source.end()));
         });
}

样例结果

testing transform
 sample size        : 1000000
 time taken         : 7.495685ms
 time per sample    : 7.495685ns
 samples per second : 133410088.604310
testing copy and reset z
 sample size        : 1000000
 time taken         : 3.436614ms
 time per sample    : 3.436614ns
 samples per second : 290984090.735823
testing hand_roll
 sample size        : 1000000
 time taken         : 3.289287ms
 time per sample    : 3.289287ns
 samples per second : 304017253.587176
testing assign through custom iterator
 sample size        : 1000000
 time taken         : 2.563334ms
 time per sample    : 2.563334ns
 samples per second : 390116933.649692
testing transform
 sample size        : 100000000
 time taken         : 768.941767ms
 time per sample    : 7.689418ns
 samples per second : 130048859.733744
testing copy and reset z
 sample size        : 100000000
 time taken         : 880.893920ms
 time per sample    : 8.808939ns
 samples per second : 113521046.892911
testing hand_roll
 sample size        : 100000000
 time taken         : 769.276240ms
 time per sample    : 7.692762ns
 samples per second : 129992315.894223
testing assign through custom iterator
 sample size        : 100000000
 time taken         : 689.493098ms
 time per sample    : 6.894931ns
 samples per second : 145034084.155546

最终答案

通过自定义转换迭代器进行赋值。

你工具箱的一份礼物

template<class Container, class Iter, class TransformFunction>
void assign_transform(Container& target, Iter first, Iter last, TransformFunction func)
{
    struct transform_iterator : Iter
    {
        using base_class = Iter;
        using value_type = typename Iter::value_type;

        transform_iterator(Iter base, TransformFunction& f)
        : base_class(base), func(std::addressof(f))
        {}

        value_type operator*() const {
            auto const& src = base_class::operator*();
            return (*func)(src);
        }
        TransformFunction* func;
    };

    target.assign(transform_iterator(first, func),
                  transform_iterator(last, func));
}

使用方法如下：

         assign_transform(target, source.begin(), source.end(),
                          [](auto& from)
         {
             return PLY(from.x, from.y, 0.0);
         });

- Richard Hodges

---

做得很好！你上面的自定义迭代器版本的转换和赋值没有将z设置为0，但似乎并不影响结果。 - TartanLlama

@TartanLlama会修复它。谢谢。还错过了一个#include <algorithm>。clang让你变得如此懒惰... - Richard Hodges

有趣的是，在我的机器上，使用Clang 3.8进行转换的速度比GCC 6.1.1快得多。 - TartanLlama

@TartanLlama，你是用libstdc++还是像我一样使用clang libc++？ - Richard Hodges

Answer 3

如果有问题，你的编译器可能会发现它。尽可能简单明了地编写代码。如果在你的平台上有意义，这将为编译器提供优化复制和循环的最佳机会。

- David Schwartz

---

通常我会说同样的话。但是测试表明，通过转换迭代器进行赋值要快得多。我认为标准容器可以使用 assign_through_transform 方法来使其成为惯用做法。请参见上面的测试。 - Richard Hodges

@RichardHodges 那对我来说似乎是最简单和最清晰的方式，让编译器有最好的机会将复制和循环一起优化。 - David Schwartz

Answer 4

默认分配器的向量有两个问题：

1. 如果向量被调整为更大的大小，则每个元素都会被初始化，这种初始化是有成本的；
2. 当为向量和插入到其中的元素保留内存时，由于向量的大小已更新，因此每次插入都会产生成本。

如此处所讨论的那样，可以使用自定义分配器来消除这些问题，以拒绝执行任何初始化。当创建具有所需大小的向量时，可以使用memcpy或for循环来复制数据。

#include <vector>
#include <cstring>
template <class T>
class no_init_alloc
    : public std::allocator<T>
{
public:
    using std::allocator<T>::allocator;

    template <class U, class... Args> void construct(U*, Args&&...) {}
};
struct PLY
{
    float x, y , z;
};
int main()
{
    std::vector<PLY> source(1000000);
    //create a vector with the custom allocator refusing any initialization
    std::vector<PLY, no_init_alloc<PLY>> target(source.size());
    //then we can use memcpy approach
    {
        memcpy(target.data(), source.data(), source.size() * sizeof(source.front()));
        for(auto& t : target) t.z = 0.0f;
    }
    // or simple for loop approach
    {
         size_t sz = target.size();
         for(size_t i = 0; i < sz; ++i) {
            target[i].x = source[i].x;
            target[i].y = source[i].y;
            target[i].z = 0.0f;
         }
    }

}

使用@Richard Hodges的基准测试，进行-O2优化，结果如下：

CLNAG:

testing transform
 sample size        : 1000000
 time taken         : 8.363995ms
 time per sample    : 8.363995ns
 samples per second : 119560090.602637
testing assign through custom iterator
 sample size        : 1000000
 time taken         : 7.162974ms
 time per sample    : 7.162974ns
 samples per second : 139606816.945029
testing no_init_alloc_memcpy
 sample size        : 1000000
 time taken         : 6.918533ms
 time per sample    : 6.918533ns
 samples per second : 144539312.018892
testing no_init_alloc_for
 sample size        : 1000000
 time taken         : 6.383721ms
 time per sample    : 6.383721ns
 samples per second : 156648450.018414

GCC：

testing transform
 sample size        : 1000000
 time taken         : 12.083038ms
 time per sample    : 12.083038ns
 samples per second : 82760643.473934
testing assign through custom iterator
 sample size        : 1000000
 time taken         : 6.188324ms
 time per sample    : 6.188324ns
 samples per second : 161594641.780230
testing no_init_alloc_memcpy
 sample size        : 1000000
 time taken         : 3.000699ms
 time per sample    : 3.000699ns
 samples per second : 333255684.758785
testing no_init_alloc_for
 sample size        : 1000000
 time taken         : 1.979482ms
 time per sample    : 1.979482ns
 samples per second : 505182669.001284

最终答案：

使用自定义的非初始化分配器，并使用简单的for循环。

- rahnema1

Answer 5

听起来需要使用std::transform，并编写一个小的lambda表达式来对每个元素进行转换。

- Jesper Juhl