重复 std::vector 的内容

问题描述 投票：0回答：4

假设我有一个简单类型的向量（可能很大），例如

std::vector<int> v{1,2,3};

重复n次最好的方法是什么？

例如3次就可以得到结果

{1,2,3,1,2,3,1,2,3}

当然，这是一个经常出现的问题（数值库通常内置有这样的功能）。我天真的解决方案：

template<typename T>
std::vector<T> repeat(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result;
    auto input_size = input.size();
    result.reserve(input_size * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        for (std::size_t i = 0; i < input_size; ++i) {
            result.push_back(input[i % input_size]);
        }
    }
    return result;
}

这当然可以做得更快吗？也许与 std::copy 一起？然而，在这种情况下，我不确定如何告诉向量其新大小，同时避免零初始化。显然这不容易做到（参见，例如，1）。我也尝试用迭代器来做，但似乎并没有更快。

c++ performance stdvector
4个回答
4
投票

使用 range-v3 你可以写：

#include <range/v3/all.hpp>
namespace rv = ranges::views;

template<typename T>
auto repeat(const std::vector<T> &input, unsigned int times) 
{
    return rv::repeat_n(input, times) 
           | rv::join 
           | ranges::to<std::vector<T>>;
}

这是一个演示。

我怀疑这将具有足够好的性能来满足您的需求。

3
投票

我会立即调整向量的大小以避免任何中间重新分配。然后，您可以使用 

std::copy
和一些算术，使用预先分配的向量中的特定偏移量将 
input
向量复制到 
result
中。

template<typename T>
std::vector<T> repeat(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result(input.size() * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        std::copy(input.begin(), input.end(), std::next(result.begin(), rep * input.size()));
    }
    return result;
}
1
投票

这最初是对问题的编辑。用户 cigien 建议将其发布为答案。这包含一些不完整的（即尚未探索实现解决方案的所有可能性）分析结果。

我制作了一些分析代码（我绝不是分析专家），将我的版本与 Cory Kramer 答案中的版本进行比较。答案中的代码似乎比我的代码快 4.5 倍（在 quick-bench.com 上使用 GCCv10.1、C++17、O3 优化进行测试）。 Remy Lebeau 关于保存临时迭代器的建议似乎没有任何区别。

在问自己之前，我错过了一些重复的问题：1和2。其中的一些答案提出了一些稍微不同的解决方案，我还没有介绍过。

range-v3 库（由 cigien 回答）虽然看起来很方便，但不是我可以使用的选项，而且我也没有对其进行配置。

分析代码：

// This code is intended to be used at quick-bench.com.
// Needs profiling library AND ADDITIONAL INCLUDES to compile, 
// see https://github.com/google/benchmark
    
#include<vector>
    
template<typename T>
std::vector<T> repeat_1(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result;
    auto input_size = input.size();
    result.reserve(input_size * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        for (std::size_t i = 0; i < input_size; ++i) {
            result.push_back(input[i % input_size]);
        }
    }
    return result;
}
    
template<typename T>
std::vector<T> repeat_2(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result(input.size() * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        std::copy(input.begin(), input.end(),
                  std::next(result.begin(), rep * input.size()));
    }
    return result;
}
    
template<typename T>
std::vector<T> repeat_3(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result(input.size() * times);
    auto iter = result.begin();
    for (std::size_t rep = 0; rep < times; ++rep, iter += input.size()) {
        std::copy(input.begin(), input.end(), iter);
    }
    return result;
}


static void version_1(benchmark::State &state) {
    std::vector<int> vec = {12, 4, 4, 5, 16, 6, 6, 17, 77, 8, 54};
    for (int i = 0; i < 100'000; ++i) {
        vec.push_back(i % 10'000);
    }

    for (auto _ : state) {
        auto repeated = repeat_1(vec, 1000);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(repeated);
    }
}
BENCHMARK(version_1);
    
static void version_2(benchmark::State &state) {
    std::vector<int> vec = {12, 4, 4, 5, 16, 6, 6, 17, 77, 8, 54};
    for (int i = 0; i < 100'000; ++i) {
        vec.push_back(i % 10'000);
    }

    for (auto _ : state) {
        auto repeated = repeat_2(vec, 1000);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(repeated);
    }
}
BENCHMARK(version_2);
    
static void version_3(benchmark::State &state) {
    std::vector<int> vec = {12, 4, 4, 5, 16, 6, 6, 17, 77, 8, 54};
    for (int i = 0; i < 100'000; ++i) {
        vec.push_back(i % 10'000);
    }

    for (auto _ : state) {
        auto repeated = repeat_3(vec, 1000);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(repeated);
    }
}
BENCHMARK(version_3);
0
投票

Galik 的 answer 对于一般情况来说已经足够了。

如果您尝试多次复制一个相当小的向量，我认为减少迭代次数会更好。可能的改进是将 

times
重写为 
2^k+r
，连续将输入向量 
k
加倍，并将 
r
输入向量附加到结果中。

template <typename T>
auto repeatByDoubling(const std::vector<T>& input, size_t scale) {
  std::vector<T> result(input);

  // Reserve spaces to keep iterators valid
  result.reserve(input.size() * scale);

  // Rewrite scale to 2^k + r, where k = log2(scale) and r = scale ^ (1 << k)
  size_t k = std::round(std::log2(scale));
  size_t r = scale ^ (1 << k);

  // Double the vector k times
  for (size_t i = 0; i < k; ++i) {
    result.insert(result.end(), result.begin(), result.end());
  };

  // Append the remaining numbers of blocks
  for (size_t i = 0; i < r; ++i) {
    result.insert(result.end(), input.begin(), input.end());
  };

  return result;
}

我用快速工作台这里描述了这个实现。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.