给定一个包含要切片的索引的向量，是否有一种有效的方法来切片 C++ 向量

Question

我正在努力将用 MATLAB 编写的代码实现为 C++。

在 MATLAB 中，您可以用另一个数组对数组进行切片，例如 A(B)，这会在 B 中的元素值指定的索引处生成一个新的 A 元素数组。

我想在 C++ 中使用向量做类似的事情。这些向量的大小为 10000-40000 个双精度类型的元素。

我希望能够使用另一个包含要切片的索引的 int 类型的向量来切片这些向量。

例如，我有一个向量 v = <1.0, 3.0, 5.0, 2.0, 8.0> 和一个向量 w = <0, 3, 2>。我想使用 w 对 v 进行切片，这样切片的结果是一个新向量（因为旧向量必须保持不变） x = <1.0, 2.0, 5.0>.

我想出了一个函数来做到这一点：

template<typename T>
std::vector<T> slice(std::vector<T>& v, std::vector<int>& id) {

    std::vector<T> tmp;
    tmp.reserve(id.size());

    for (auto& i : id) {
        tmp.emplace_back(v[i]);
    }

    return tmp;
}

我想知道是否有更有效的方法来完成这样的任务。速度是这里的关键，因为这个切片函数将处于一个大约有 300000 次迭代的 for 循环中。我听说 boost 库可能包含一些有效的解决方案，但我还没有使用它的经验。

我使用 chrono 库来测量调用此切片函数所需的时间，其中要切片的向量长度为 37520，包含索引的向量大小为 1550。对于此函数的单次调用，经过的时间 = 0.0004284s。然而，超过 300000 次 for 循环迭代，总耗时为 134s。

非常感谢任何建议！

Answer 1

emplace_back 有一些开销，因为它涉及 std::vector 中的一些内部会计。试试这个：

template<typename T>
std::vector<T> slice(const std::vector<T>& v, const std::vector<int>& id) {

    std::vector<T> tmp;
    tmp.resize (id.size ());

    size_t n = 0;
    for (auto i : id) {
        tmp [n++] = v [i];
    }

    return tmp;
}

另外，我在你的内部循环中删除了一个不必要的取消引用。

编辑： 我进一步考虑了这一点，并受到@jack 的回答的启发，我认为可以进一步优化内部循环（这是重要的循环）。这个想法是将循环使用的所有内容都放在局部变量中，这为编译器提供了优化代码的最佳机会。所以试试这个，看看你得到什么时间。确保测试发布/优化版本：

template<typename T>
std::vector<T> slice(const std::vector<T>& v, const std::vector<int>& id) {

    size_t id_size = id.size ();
    std::vector<T> tmp (id_size);
    T *tmp_data = tmp.data ();

    const int *id_data = id.data ();
    const T* v_data = v.data ();

    for (size_t i = 0; i < id_size; ++i) {
        tmp_data [i] = v_data [id_data [i]];
    }

    return tmp;
}

Answer 2

性能似乎有点慢；您是否使用编译器优化进行构建（例如 g++ main.cpp -O3 或者如果使用 IDE，切换到发布模式）。仅此一项就加快了大约 10 倍的计算时间。

如果您已经在使用优化，通过使用基本的 for 循环迭代 (for int i = 0; i < id.size(); i++) 在我的机器上计算时间加快了大约 2-3 倍，这个想法是，编译器不必解析什么类型auto 指的是，由于基本的 for 循环一直在 C++ 中，编译器可能有很多技巧来加速它。

template<typename T>
std::vector<T> slice(const std::vector<T>& v, const std::vector<int>& id){

    // @Jan Schultke's suggestion
    std::vector<T> tmp(id.size ());

    size_t n = 0;
    for (int i = 0; i < id.size(); i++) {
        tmp [n++] = v [i];
    }

    return tmp;
}

给定一个包含要切片的索引的向量，是否有一种有效的方法来切片 C++ 向量

Is there an efficient way to slice a C++ vector given a vector containing the indexes to be sliced

c++

boost

vector

slice