0

我正在交叉一些数字集，并通过存储每次在地图中看到数字时的计数来做到这一点。

我发现性能非常缓慢。

详细信息：-其中一组包含 150,000 个数字-该组和另一组的交集第一次大约需要 300 毫秒，第二次大约需要 5000 毫秒-我还没有进行任何分析，但每次我打破在 malloc.c 中进行交集时的调试器！

那么，我该如何提高这种性能呢？切换到不同的数据结构？一些如何提高map的内存分配性能？

更新：

  1. 有没有办法让 std::map 或 boost::unordered_map 预先分配一些空间？
  2. 或者，是否有任何有效使用这些的技巧？

更新2：

请参阅像 C# HashSet<T> 和 Dictionary<K,V> 这样的快速 C++ 容器？

更新3：

我对 set_intersection 进行了基准测试并得到了可怕的结果：

(set_intersection) Found 313 values in the intersection, in 11345ms
(set_intersection) Found 309 values in the intersection, in 12332ms

代码：

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}
4

9 回答 9

3

您绝对应该使用更快的预分配向量。与 stl 集合进行集合交集的问题在于，每次移动到下一个元素时，您都在追逐一个动态分配的指针，而该指针很容易不在您的 CPU 缓存中。使用向量，下一个元素通常会在您的缓存中，因为它在物理上靠近前一个元素。

向量的诀窍在于，如果您不为这样的任务预先分配内存，它会执行更糟糕的操作，因为它会在初始化步骤期间调整自身大小时继续重新分配内存。

尝试这样的事情 - 它会更快。

int runIntersectionTestAlgo() { 

vector<char> vector1; vector1.reserve(100000);
vector<char> vector2; vector2.reserve(1000);

// Create 100,000 values for set1
for ( int i = 0; i < 100000; i++ )    {
    int value = 1000000000 + i;
    set1.push_back(value);
}

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

// Create 1,000 values for set2
for ( int i = 0; i < 1000; i++ )    {
    int random = rand() % 200000 + 1;
    random *= 10;
    int value = 1000000000 + random;
    set2.push_back(value);
}

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

// Reserve at most 1,000 spots for the intersection
vector<char> intersection; intersection.reserve(min(vector1.size(),vector2.size()));
set_intersection(vector1.begin(), vector1.end(),vector2.begin(), vector2.end(),back_inserter(intersection));

return intersection.size(); 
}
于 2009-06-30T14:28:48.763 回答
1

我会支持对它们进行排序的建议。已经有 STL 集合算法对排序范围进行操作（如 set_intersection、set_union 等）：

set_intersection

于 2009-06-29T02:28:00.630 回答
1

在不了解您的问题的情况下，“用一个好的分析器检查”是我能给出的最好的一般建议。除此之外...

如果内存分配是您的问题，请切换到某种池分配器，以减少对malloc. Boost 有许多应该与std::allocator<T>. 事实上，如果您已经注意到调试中断示例总是以malloc.

如果已知您的数字空间是密集的，您可以切换到使用基于vector- 或 -bitset的实现，使用您的数字作为向量中的索引。

如果您的数字空间大多是稀疏的，但有一些自然聚类（这是一个很大的if），您可以切换到向量图。使用高阶位进行地图索引，使用低阶位进行向量索引。这在功能上与简单地使用池分配器非常相似，但它可能会为您提供更好的缓存行为。这是有道理的，因为您正在向机器提供更多信息（集群是显式且缓存友好的，而不是您期望从池分配中获得的随机分布）。

于 2009-06-29T01:58:10.770 回答
1

我不明白为什么你必须使用地图来做交叉点。正如人们所说，您可以将集合放入std::set's 中，然后使用std::set_intersection().

或者您可以将它们放入hash_set's. 但是你必须手动实现交集：从技术上讲，你只需要将其中一个集合放入 a hash_set，然后循环另一个集合，并测试每个元素是否包含在hash_set.

于 2009-06-29T03:33:16.817 回答
0

我想出了一些办法：如果我将调试器附加到 RELEASE 或 DEBUG 构建（例如在 IDE 中按 F5），那么我会遇到可怕的情况。

于 2009-06-29T20:25:38.837 回答
0

查看您的算法，然后选择正确的数据类型。如果您要进行类似集合的行为，并且想要进行交叉路口等，std::set则可以使用容器。

由于它的元素以排序方式存储，插入可能会花费您 O(log N)，但与另一个（排序！）的交集std::set可以在线性时间内完成。

于 2009-06-29T07:51:52.383 回答
0

你的交集算法是什么？也许有一些改进？

这是另一种方法

我不知道它是更快还是更慢，但它可能是值得尝试的。在这样做之前，我还建议使用分析器来确保您确实在热点上工作。更改要使用的相交数字集std::set<int>。然后遍历最小的一个，查看您找到的每个值。对于最小集合中的每个值，使用该find方法查看该数字是否存在于其他每个集合中（为了性能，从最小到最大搜索）。

这是在没有在所有集合中找到数字的情况下进行优化的，因此如果交集比较小，可能会很快。

然后，std::vector<int>改为存储交叉点 - 插入使用push_back也非常快。

这是另一种替代方法

将数字集更改为std::vector<int>并用于std::sort从最小到最大排序。然后使用std::binary_search与上述大致相同的方法来查找值。这可能比搜索 a 更快，std::set因为数组在内存中更紧密地打包。实际上，没关系，您可以在锁步中迭代值，查看具有相同值的值。仅增加小于您在上一步中看到的最小值的迭代器（如果值不同）。

于 2009-06-29T01:58:10.003 回答
0

可能是你的算法。据我了解，您正在旋转每组（我希望这是一个标准组），然后将它们扔到另一张地图中。这做了很多你不需要做的工作，因为标准集的键已经按排序顺序排列。相反，采取类似“合并排序”的方法。旋转每个迭代，取消引用以找到最小值。计算具有该最小值的数字，并增加这些数字。如果计数为 N，则将其添加到交集。重复直到第一张地图结束（如果你在开始之前比较大小，你就不必每次都检查每张地图的结束）。

响应更新：确实存在通过预先保留空间来加速内存分配的功能，例如boost::pool_alloc。就像是：

std::map<int, int, std::less<int>, boost::pool_allocator< std::pair<int const, int> > > m;

但老实说，malloc 非常擅长它的功能。在做任何过于极端的事情之前，我会先分析一下。

于 2009-06-29T02:13:21.783 回答
0

与地图的交叉点很慢，请尝试hash_map. （然而，这并不是在所有 STL 实现中都提供的。

或者，对两个地图进行排序并以类似合并排序的方式进行。

于 2009-06-29T02:26:38.900 回答