确定 uint64 是否已被“看到”的最快方法

Question

我一直对优化“重新编号”算法感兴趣，该算法可以将具有重复项的任意整数数组重新标记为从 1 开始的标签。集合和映射对于我一直在尝试做的事情来说太慢了，排序也是如此。是否有一种数据结构只能记住某个数字是否已被看到或不可靠？我正在考虑尝试使用布隆过滤器，但我有 >12M 整数，并且目标性能比良好的哈希图更快。这可能吗？

这是一个简单的伪 C++ 算法示例，该算法会很慢：

// note: all elements guaranteed > 0
std::vector<uint64_t> arr = { 21942198, 91292, 21942198, ... millions more };

std::unordered_map<uint64_t, uint64_t> renumber;
renumber.reserve(arr.size());

uint64_t next_label = 1;
for (uint64_t i = 0; i < arr.size(); i++) {
    uint64_t elem = arr[i];
    if (renumber[elem]) {
        arr[i] = renumber[elem];
    }
    else {
        renumber[elem] = next_label;
        arr[i] = next_label;
        ++next_label;
    }
}

输入/输出示例：

{ 12, 38, 1201, 120, 12, 39, 320, 1, 1  }
->
{ 1, 2, 3, 4, 1, 5, 6, 7, 7 }

Answer 1

您的算法还不错，但是用于映射的适当数据结构是具有开放寻址的哈希表。

正如这个答案所解释的，std::unordered_map不能以这种方式实现： https: //stackoverflow.com/a/31113618/5483526

因此，如果 STL 容器对您来说确实太慢，那么您可以通过制作自己的容器来做得更好。

但请注意：

1. 90% 的情况下，当有人抱怨 STL 容器太慢时，他们会在关闭优化的情况下运行调试构建。确保您正在运行优化编译后的发布版本。在 12M 整数上运行代码最多需要几毫秒。
2. 当只需要一次时，您会多次访问地图，如下所示：

uint64_t next_label = 1;
for (size_t i = 0; i < arr.size(); i++) {
    uint64_t elem = arr[i];
    uint64_t &label = renumber[elem];
    if (!label) {
       label = next_label++;
    }
    arr[i] = label;
}

请注意，unordered_map operator []返回对关联值的引用（如果不存在则创建它），因此您可以测试和修改该值，而无需再次搜索地图。