我一直对优化"重新编号"感兴趣。可以将具有重复项的任意整数数组重新标记为从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 }
你的算法不错，但是对于映射来说，合适的数据结构是一个开放寻址的哈希表。
正如在这个答案中解释的那样，std::unordered_map不能这样实现:https://stackoverflow.com/a/31113618/5483526
所以如果STL容器对你来说太慢了，那么你可以自己做一个更好的。
但是，请注意:
- 90%的情况下，当有人抱怨STL容器太慢时，他们正在运行一个调试版本，并关闭了优化。确保您运行的是在优化状态下编译的发布版本。在12M整数上运行代码最多只需要几毫秒。
- 当只需要一次时，你多次访问地图，像这样:
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_mapoperator []返回对关联值的引用(如果不存在则创建它)，因此您可以测试和修改该值，而无需再次搜索映射。
已更新修复了
首先，当你经历"缓慢"时;对于像vector或map这样的std:: collection类，只需通过优化重新编译即可(发布版本)。通常有10倍的加速。
现在谈谈你的问题。我将展示一个在O(N)时间内运行的两步解决方案。我将把它作为练习留给您，让您转换为一次通过的解决方案。但是我断言，即使对于包含数百万个元素的向量，这也足够快了。首先，声明不是一个而是两个无序映射:
std::unordered_map<uint64_t, uint64_t> element_to_label;
std::unordered_map<uint64_t, std::pair<uint64_t, std::vector<uint64_t>>> label_to_elements;
第一个映射，element_to_label将原始数组中的整数值映射到它的唯一标签。
第二个映射，label_to_elements映射到元素值和元素在原数组中出现的索引列表。
现在构建这些映射:
element_to_label.reserve(arr.size());
label_to_elements.reserve(arr.size());
uint64_t next_label = 1;
for (size_t index = 0; index < arr.size(); index++)
{
const uint64_t elem = arr[index];
auto itor = element_to_label.find(elem);
if (itor == element_to_label.end())
{
// new element
element_to_label[elem] = next_label;
auto &p = label_to_elements[next_label];
p.first = elem;
p.second.push_back(index);
next_label++;
}
else
{
// existing element
uint64_t label = itor->second;
label_to_elements[label].second.push_back(index);
}
}
当上面的代码运行时，它建立了一个数据库，所有数组中的值，它们的标签，以及它们出现的索引。
所以现在要重新编号数组，这样所有元素都被替换为它们较小的标签值:
for (auto itor = label_to_elements.begin(); itor != label_to_elements.end(); itor++)
{
uint64_t label = itor->first;
auto& p = itor->second;
uint64_t elem = p.first; // technically, this isn't needed. It's just useful to know which element value we are replacing from the original array
const auto& vec = p.second;
for (size_t j = 0; j < vec.size(); j++)
{
size_t index = vec[j];
arr[index] = label;
}
}
注意这里我通过引用赋值变量使用&操作符，以避免对映射中的任何值进行昂贵的复制。
如果你的原始向量或数组是这样的
{ 100001, 2000002, 300003, 400004, 400004, 300003, 2000002, 100001 };
那么标签的应用程序会将数组呈现如下:{1,2,3,4,4,3,2,1}
你还有一个快速的0(1)查找操作符，可以使用label_to_elements