1

我们有一个给定的 3D 网格，我们正在尝试消除相同的顶点。为此，我们使用了一个包含顶点坐标和相应法线的自定义结构。

    struct vertice
    {
        float p1,p2,p3,n1,n2,n3;

        bool operator == (const vertice& vert) const
        {
            return (p1 == vert.p1 && p2 == vert.p2 && p3 == vert.p3);
        }
    };

用数据填充顶点后，将其添加到 unordered_set 以删除重复项。

    struct hashVertice
    {
        size_t operator () (const vertice& vert) const
        {
            return(7*vert.p1 + 13*vert.p2 + 11*vert.p3);
        }
    };

    std::unordered_set<vertice,hashVertice> verticesSet;

    vertice vert;

    while(i<(scene->mMeshes[0]->mNumVertices)){

            vert.p1 = (float)scene->mMeshes[0]->mVertices[i].x;
            vert.p2 = (float)scene->mMeshes[0]->mVertices[i].y;
            vert.p3 = (float)scene->mMeshes[0]->mVertices[i].z;

            vert.n1 = (float)scene->mMeshes[0]->mNormals[i].x;
            vert.n2 = (float)scene->mMeshes[0]->mNormals[i].y;
            vert.n3 = (float)scene->mMeshes[0]->mNormals[i].z;

            verticesSet.insert(vert);

            i = i+1;
    }

我们发现它对于像 3.000.000 个顶点这样的数据量来说太慢了。即使运行了 15 分钟，程序也没有完成。是否存在我们看不到的瓶颈，或者是否有其他数据结构更适合此类任务？

4

3 回答 3

6

如果你只是verticesSet.insert(vert);从循环中删除会发生什么？

如果它显着加速（正如我所期望的那样），那么您的瓶颈就在std::unordered_set哈希表的内部，哈希表的主要潜在性能问题是当存在过多的哈希冲突时。

在您当前的实现中，如果p1和p2都很p3小，则不同哈希码的数量会很小（因为您将浮点数“折叠”为整数）并且会有很多冲突。

如果上述假设被证明是正确的，我会尝试以不同的方式实现散列函数（例如乘以更大的系数）。

除此之外，正如其他人已经建议的那样，配置您的代码。

于 2013-07-10T09:15:58.363 回答
1

散列浮点可能很棘手。特别是，您的哈希例程将哈希计算为浮点值，然后将其转换为无符号整数类型。如果顶点可以很小，这会带来严重的问题：[0...1.0)例如，如果所有顶点都在 range 中，则哈希函数将永远不会返回大于 13 的任何值。作为无符号整数，这意味着最多会有 13 个不同的哈希码。

散列浮点的常用方法是散列二进制图像，首先检查特殊情况。（0.0并且-0.0 有不同的二进制图像，但必须散列相同。这是一个悬而未决的问题，你用NaNs 做什么。）因为float这特别简单，因为它通常具有相同的大小 int，你可以reinterpret_cast：

size_t
hash( float f )
{
    assert( /* not a NaN */ );
    return f == 0.0 ? 0.0 : reinterpret_cast( unsigned& )( f );
}

我知道，正式地，这是未定义的行为。但是，如果 float 和 int 具有相同的大小，并且 unsigned 没有捕获表示（当今大多数通用机器上的情况），那么出错的编译器就是故意钝化的。

然后，您可以使用任何组合算法来合并三个结果；你使用的那个和其他的一样好（在这种情况下——它不是一个好的通用算法）。

我可能会补充一点，虽然有些评论坚持进行分析（这通常是个好建议），但如果您为 300 万个值花费 15 分钟，那么问题实际上可能只是一个糟糕的哈希函数，这会导致很多冲突. 没有其他东西会导致性能如此糟糕。除非您熟悉 的内部实现，否则std::unordered_set通常的分析器输出可能不会为您提供太多信息。另一方面，std::unordered_set确实具有 和 之类的函数bucket_count，bucket_size可以分析散列函数的质量。在您的情况下，如果您无法创建一个unordered_set包含 300 万个条目的条目，那么您的第一步应该是创建一个更小的条目，并使用这些函数来评估您的哈希码的质量。

于 2013-07-10T09:14:25.183 回答
0

如果存在瓶颈，您肯定看不到它，因为您没有包含任何类型的计时措施。

使用分析器或手动测量算法的时间。这会让你找到瓶颈——如果有的话。

这是进行的正确方法。根据我的经验，期望自己或 StackOverflow 用户通过肉眼检查而不是实际测量程序中的时间来发现瓶颈是优化尝试失败的最常见原因。

于 2013-07-10T08:50:49.780 回答