从给定向量的块中生成新向量

Question

我有一个 std::vector，其中存储了大约 100 万个值。现在我想将向量分成 N 个给定大小的块，并通过从原始向量中随机拉出 N 个块来创建一个新的 std::vector。这是我目前所拥有的，这只是为了获得一个想法。

int main {  
    int breakPoint = 2;
    std::vector<int> test = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::vector<int> newTest;
    int length = test.size();
    for (size_t i = 0; i < length; i++) {
        int foo = random(breakPoint,length);
        //std::cout << foo << std::endl;
        std::vector<int> subvector(test.begin() + foo, test.begin() + foo + breakPoint);

        for (size_t i = 0; i < subvector.size(); i++){
            newTest.push_back(subvector[i]);
        }
    }
    return 0;
}

int random(int N, int interval){
    int rnd;

    int foo = 1;
    while (foo !=0) {
        rnd = int(randomNumber(0, (interval+1-N)));
        foo = (rnd%N);
    }
    return rnd;
}

randomNumber(a,b)给出区间[a,b)中的一个随机数。这段代码运行并且对于不太大的向量我会这样使用它。但是因为我有一个很大的原始向量，我将不得不多次重复这个新的向量操作，以获得统计数据，我宁愿不使用它。所以我的问题是，如何使这样的操作非常快？第一个问题显然是我如何 select 在 random() 中设置断点。谢谢你帮助我，干杯！

Answer 1

如何使用 std::vector::insert 将随机块附加到输出向量：

std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::vector<int> output;

for (size_t i = 0; i != num_blocks; i++) {
    int block_position = getRandomBlock(num_blocks, block_length);
    auto block_begin = input.cbegin() + block_position;
    auto block_end = block_begin + block_length;
    output.insert(output.end(), block_begin, block_end);
}

Answer 2

正如评论所建议的那样，对于非常大的test，这段代码在复制过程中会陷入困境，解决方案是不复制。（假设测试包含一百万个元素，这意味着您将进行 400 万次随机访问 只是为了复制 。）

只要 test 保持不变，将迭代器保留在 test 中是一种简单的索引方式。

const auto breakPoint = 2;
const std::vector<int> test = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector<vector<int>::const_iterator> newTest(test.size());

for(auto& i : newTest){
    i = test.begin() + random(breakPoint, test.size());
}

将迭代器保存在向量中允许我们对它们进行排序，在访问内存之前。所以我们可以利用缓存的空间局部性。

sort(newTest.begin(), newTest.end());

现在要使用 newTest，您只需执行以下操作即可：

for(auto& i : newTest){
    for_each(i, i + breakPoint, [](int foo){cout << foo << ' ';});
    cout << endl;
}

编辑：

random 在宏伟的计划中似乎并没有浪费太多时间，因为它不进行内存访问，但您可以通过搜索合适的 breakPoint 乘数来改进它，而不是试图随机找到一个 breakPoint 增量：

// This change assumes that you've already done srand(time(nullptr));
int random(int N, int interval){
    return (rand() % (interval / N)) * N;
}

您可以看到如何内联这么简单的东西，这将提供允许 interval / N 只计算一次的进一步好处。所以我们的初始化部分现在可以变成：

const auto breakPoint = 2;
const std::vector<int> test = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const auto partitions = test.size() / breakPoint;
vector<vector<int>::const_iterator> newTest(test.size());

srand(time(nullptr));

for(auto& i : newTest){
    i = test.begin() + breakPoint * (rand() % partitions);
}

从给定向量的块中生成新向量

Generate a new vector out of blocks of a given vector

c++

random

vector