时间戳

首页 > 解决方案 > 快速填充 boost::unordered_set

c++ - 快速填充 boost::unordered_set

问题描述

我正在尝试根据图像分类的结果尽可能快地构建一组元素。

在细节上，我想在这个集合中存储属于某个类的所有 (r, g, b) 像素。该问题有 2 个类别，我想保留第 1 类的像素并丢弃第 0 类的像素。分类是使用经过训练的mlpack分类器在双精度 (r, g, b) 向量上完成的。

我必须使用 aboost::unordered_set<uint32_t>来完成此任务或类似任务。到目前为止的代码看起来像这样

boost::unordered_set<uint32_t> bset;

for (int r = 0; r < 256; r++)
{
    for (int g = 0; g < 256; g++)
    {
        for (int b = 0; b < 256; b++)
        {
            arma::rowvec xp = { (double)b, (double)g, (double)r };
            if ((bool)(clf.Classify(xp))) {
                uint32_t cachePos = r + (g << 8) + (b << 16);
                bset.insert(cachePos);
            }

        }
    }
}

我做了一些基准测试，最慢的部分是插入insert(). 扫描所有可能的 (r, g, b) 大约需要 5 秒。由于代码是从 GUI 调用的，因此我希望它能够更快地减少用户等待结果的时间。

首先我试图改变.insert()，.emplace()但正如我所料，几乎没有改善。

我还尝试填充另一个容器，实际上std::vector速度非常快，并且使用迭代器将其内容复制到集合中：

std::vector<int> predictions;
for (int r = 0; r < 256; r++)
{
    for (int g = 0; g < 256; g++)
    {
        for (int b = 0; b < 256; b++)
        {
            arma::rowvec xp = { (double)b, (double)g, (double)r };
            if ((bool)(clf.Classify(xp))) {
                uint32_t cachePos = r + (g << 8) + (b << 16);
                predictions.push_back(cachePos);
            }

        }
    }
}

bset = boost::unordered_set<uint32_t>(predictions.begin(), predictions.end());

但是，最后一行仍然需要很多时间，大约 2-3 秒。你对我有什么暗示吗？我可以做些什么来提高我的代码速度？是否有更快的容器可以用来替换boost::unordered_set？容器应仅包含来自第 1 类的元素。

标签： c++boostcontainersmlpackboost-unordered

解决方案

由于 unordered_set 无法预测要插入的元素数量，它会为每个特定元素执行分配和插入。在您的情况下，它恰好是 256 x 256 x 256 = 16,777,216 次。这种情况下的瓶颈是内存分配。由于向量按块消耗内存 - 它插入速度更快。解决方案是使用“保留”方法：

boost::unordered_set<uint32_t> bset;
bset.reserve(256*256*256);

for (int r = 0; r < 256; r++)
{
    for (int g = 0; g < 256; g++)
    {
        for (int b = 0; b < 256; b++)
        {
            arma::rowvec xp = { (double)b, (double)g, (double)r };
            if ((bool)(clf.Classify(xp))) {
                uint32_t cachePos = r + (g << 8) + (b << 16);
                bset.insert(cachePos);
            }

        }
    }
}

推荐阅读