gpt4 book ai didi

c++ - 从整数 vector 列表中删除重复项的快速方法

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:16:06 24 4
gpt4 key购买 nike

假设我们有一个函数返回一百万个长度为 30 的整数 vector ,每个 vector 都有较小的条目(比如 -100 到 100 之间)。进一步假设输出只有大约 30000 个独特的 vector ,其余的都是重复的。检索唯一输出 vector 列表的良好数据结构和算法是什么?优选地,当 3% 的独特 vector 的比例大致恒定时,解决方案应该可以很好地扩展。

这个问题主要是关于数据结构的,但我计划使用 STL 在 C++ 中实现它,因此也欢迎任何有关实现的提示。

  • 朴素的算法是存储已知 vector 的列表(可能按字典顺序排序)。当一个新 vector 到达时,我们可以使用循环检查它是否已经在列表中(或在排序列表中搜索)。
  • 散列法:假设 vector 存储在 C 数组中。什么是整数 vector 的好散列函数?我看到的一个缺点是每个 vector 的每个分量都至少被触及一次。这似乎已经太多了。
  • 任何树数据结构都好吗?例如,我们可以将所有可见 vector 的第一个分量中的值存储为根,然后将第二个分量中的值存储为它们的子 vector ,...

我没有计算机科学背景。我也很高兴能提供一些文献资料,我可以从中学习如何处理此类问题。

最佳答案

您提出的建议有时称为后备表; A用于各种查找目的的辅助表。在你的情况下,你有很多不同的可能方式来组织这个 table 。最明显的是不组织它,使用线性搜索以查看下一个元素是否已知。自从table 最终将包含大约 30000 个元素,即可能不是一个好主意。来自标准库(至少在 C++11 中),有两种可能性:std::setstd::unordered_set . std::set使用某种形式的平衡树,因此对每个树最多进行 lg n 次比较查找(30000 个元素大约 15 个); std::unordered_set是一个哈希表,并具有良好的哈希函数,将需要尽可能小恒定的比较次数:你应该能够得到它平均下降到 2 以下(但可能要付出更多的代价memory——负载因子越低,概率越小的碰撞)。正如你所说,你确实有额外的费用计算散列函数,正如你所指出的,这确实涉及访问 vector 中的每个元素;在二进制文件中树,每次比较所需的一切就足够了比较元素以确定顺序——在许多情况下,那可能只是一两个。 (但是如果你说有一个很多重复......你无法检测到重复,直到你访问了所有 30 个条目,因为任何一个都可能不同。)唯一的方法知道哪个解决方案实际上会更快是衡量两者都使用典型数据;对于您描述的数据集(很多重复),我怀疑哈希表会赢,但它是远非确定。

最后,您可以使用某种非二叉树。如果可以的话确实将值限制在特定范围内(例如 -100..100),您可以使用带有指向的指针的普通 vector 或数组子节点,直接用元素值索引,转置有必要的。然后你就走树,直到你找到一个空指针,或者你到达终点。的最大深度树将是 30,事实上,每个元素的深度都是 30,但是通常,您会发现该元素在获取之前是唯一的那么深。我怀疑(但同样,你需要测量)在你的情况下,有很多重复,这实际上是明显比前两个建议慢。 (还有它你会做更多的工作,因为我不知道任何现有的实现。)

至于散列,几乎任何形式的线性全等散列应该足够了:例如 FNV。大部分的这种散列的文档涉及字符串(数组 char ), 但它们往往与任何积分一起工作类型。我通常使用类似的东西:

template <typename ForwardIterator>
size_t
hash( ForwardIterator begin, ForwardIterator end )
{
size_t results = 2166136261U
for ( ForwardIterator current = begin; current != end; ++ current ) {
results = 127 * results + static_cast<size_t>( *current );
}
return results;
}

我的选择127因为乘数主要取决于速度旧系统:乘以 127 比大多数系统快得多给出好的结果的其他值。 (我不知道这是否仍然如此。但乘法仍然是一个在许多机器上运行相对较慢,并且编译器将转换 127 * x变成类似 x << 7 - x 的东西如果说更快。)上述算法的分布是关于和 FNV 一样好,至少对于我的数据集测试。

关于c++ - 从整数 vector 列表中删除重复项的快速方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15728266/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com