由图案分裂矢量

Question

我有一个包含大量数据的向量'a',应该分成两个单独的向量'b'和'c'.

vector<unsigned char> a; //contains a lot of data

vector<unsigned char> b; //data should be split into b and c
vector<unsigned char> c;

向量'a'中的数据布局如下:

bbbbccccbbbbccccbbbbcccc

前4个字节应该进入向量'b',接下来的4个字节进入向量'c'等等.

我可以迭代我的数据并将每个元素push_back(或插入)到相应的向量中(基于它们在向量'a'中的索引).但是,我尝试了这个,结果很慢.

在C++中是否有更高效的方法来实现这一目标？

Answer 1

尝试预先分配您将要使用的内存以避免副本.假设a包含完整序列,您可以:

b.reserve(a.size() / 2);
c.reserve(a.size() / 2);
for (auto it = a.begin(); it < a.end(); it += 8) {
  b.insert(b.end(), it, it + 4);
  c.insert(c.end(), it + 4, it + 8);
}

更新

如果您不介意修改原始向量a,可以使用它来保留其中一个子序列并避免分配更多内存.假设a包含完整序列:

b.reserve(a.size() / 2);
auto writer = a.begin();
for (auto reader = a.cbegin(); reader < a.cend(); reader += 8, writer += 4) {
  b.insert(b.end(), reader, reader + 4);
  std::copy(reader + 4, reader + 8, writer);
}
a.resize(a.size() / 2);

Answer 2

如果您对缓存友好,那么您可以比ChronoTrigger的更新答案快得多.

请记住向量中的一件事,你想在一次性中迭代尽可能多的元素,对它们做一件事.

只要你不介意弄乱原版vector<T> a,这个解决方案就可以了:

假设1

在你的例子中,你的元素在你的数组中均匀分布,步长为K. K = 4: BBBBCCCCBBBBCCCC

假设2

矢量的大小是K的倍数.在您的示例中,N = 24 = 6*4.

假设3

该算法不需要稳定.也就是说,元素的相对排序b不需要与它们所在的相同a.同样的c.

(我确实实现了这个的稳定版本......你不想使用它)

途径

• a使用两个迭代器迭代向量,第一个从0开始,第二个从N开始
• 在迭代器中为K元素交换元素
• 重复直到迭代器相遇
  • BBBBCCCCBBBBCCCC 变 CCCCCCCCBBBBBBBB

通俗地说,做以下事项:

• 保持c一开始的元素
• 创建向量b作为下半部分a
• 'a'现在是'c'

它可能看起来更有效,但因为我们对记忆非常友好,所以它实际上会更快(在我自己的实验中占1/3的时间)

码

 void FastSplit(std::vector<int>& a, int stride)
 {
    auto asize = a.size();
    size_t j = asize-1;
    if ((asize / stride) % 2 == 1)
    {
       j -= stride;
       asize = asize - (asize+stride)/2; // asize now represents number of C elements
    }
    else
    {
        asize /= 2; // asize now represents number of C elements
    }

    for (size_t i=0; i < j; i+=stride, j-=stride)
    {
        for (size_t k = 0; k < stride; ++k, ++i, --j)
        {
            std::swap(a[i], a[j]);
        }
    }

现场演示

在我对400万个整数的测试中,ChronoTrigger的第一个答案需要时间T,他的第二个答案需要时间0.6T,而我的答案需要时间0.2T(时间的十分之二!)

此代码的另一个好处是它处理的情况是没有相同数量的元素要分发:

BBBBCCCCBBBB

而链接的答案只能处理存在相同数量B和C元素的情况.

编辑

我也按照sp2danny的注释实现了上述算法的稳定版本,但它非常慢,你永远不想使用它,因为它必须遍历数组O(n)次以执行就地交换.那时,我更喜欢ChronoTrigger的回答.

代码以防万一有人想坐一会儿(它也在链接的演示代码中):

 // Slow!
 void StableSwappingSplit(std::vector<int>& a, int stride)
 {
    auto asize = a.size();

    auto starti = 0;
    while(starti < asize)
    {
        for (size_t i=starti, j = starti+stride;j < asize-starti; i+=stride, j+=stride)
        {
            for (size_t k = 0; k < stride; ++k, ++i, ++j)
            {
                std::swap(a[i], a[j]);
            }
        }
        starti += stride;
    }

    if ((asize / stride) % 2 == 1)
    {
       asize = asize - (asize+stride)/2; // asize now represents number of C elements
    }
    else
    {
        asize /= 2; // asize now represents number of C elements
    }
    //std::cout << "After swapping: \n";
    //PrintVec(a);

    std::vector<int> b(std::make_move_iterator(a.begin() + asize), std::make_move_iterator(a.end())); // copy second half into b
    a.resize(asize);
    //a is now c
 }