4

将百万或十亿 STL 向量排序和连接成单个 STL 向量的最佳方法是什么？目前，我这样做的方式是迭代向量并执行每个操作。

这是伪代码

typedef unsigned long long int ULLInt;

ULLInt N = 1000000;

vector<vector<ULLInt> > vecVec( N, vector<ULLInt>() );
vector<ULLInt>          concatVec;

// ...
// ... fill vectors inside vecVec here 
// ..  we also get here the total number of values inserted in all vectors (count)
// ...

// reserve the space
concatVec.reserve( count);

// sort each vector and concatenate them in sequence
for( ULLInt i=0; i<N; i++)
  sort( vecVec[i].begin(), vecVec[i].end() );
  concatVec.insert( concatVec.end(), vecVec[i].begin(), vecVec[i].end() );
end for

请注意，不需要对 concatVec 进行排序。感谢您的建议。

4

4 回答 4

3

我要做的一件事是询问您是否真的需要连接一百万个 std::vectors。如果您将每个向量添加到列表中并创建自己的迭代器来遍历每个向量中的每个元素会怎样？对于大多数算法来说，这与一个大向量无法区分。而且，根据负载，在自定义迭代器中完成的额外工作将远远少于实际连接所有向量所需的所有工作。

于 2012-08-14T17:53:40.197 回答
1

每次代码插入其中一个向量的内容时，它必须确保目标向量有足够的内存来保存结果。这意味着它将经常为目标向量重新分配内存。这意味着复制它的内容，而代码最终会这样做很多很多次。将目标向量的内存预分配到最终的完整大小会快得多。阅读有关vector::reserve().

于 2012-08-14T16:35:26.473 回答
1

这个怎么样：

  • 将向量拆分为核心堆。计算每桩所需的尺寸
  • 在向量中为所有数据保留空间
  • 将此向量拆分为核心部分。
  • 将零件和桩送入螺纹以进行合并。

一些快速代码（可能无法编译，但您可能明白了）：

typedef vector<vector<ULLINT>> ManyVectors; 

void merge(ManyVectors vector_of_vectors) {
  const int cores = 16;
  std::array<ManyVectors, cores> piles = split_vector(vector_of_vectors,cores);
  std::array<size_t, cores> sizes = calculate_sizes(piles,cores);
  std::vector<ULLINT> result;
  result.reserve(sum_of_sizes(sizes));
  int used = 0; 
  int core = 0;
  for (ManyVectors& pile: piles) {
    std::thread(merge_vectors, pile, result.begin()+used);
    used += sizes[core];
    core += 1;  
  }
}
于 2012-08-14T16:59:23.373 回答
1

如果 vecVec 中的向量按升序填充（正如我从聊天中了解到的那样 - 那是您的用例），那么您可以尝试使用一个向量而不是许多小向量，在单独的索引数组中维护每个向量的开始索引。通过在适当的位置“构建”子向量，这将避免昂贵的连接。

#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iterator>

int main(int argc,char *argv[])
{
    using namespace std;
    typedef int Payload;
    vector<Payload> vec;
    vector<size_t> indices;
    for(unsigned i=0;i!=100;++i)
    {
        indices.push_back(vec.size()); // begin index of current vector
        // filling current sub-vector
        generate_n(back_inserter(vec),777+i,rand);
    }
    indices.push_back(vec.size()); // end of last vector, or begin of
                                   // one-past last vector

    // sorting each sub vector
    for(size_t i=0;i+1!=indices.size();++i)
    {
        // can be done in parallel. be aware of possible false sharing
        sort(vec.begin()+indices[i],vec.begin()+indices[i+1]);
    }
    return 0;
}
于 2012-08-14T17:46:15.983 回答