0

有一个数据结构就像一个不断增长的数组。当且仅当这些整数在此数据结构中没有重复时，未知数量的整数将被一一插入。

最初我认为 astd::set就足够了，它会随着新整数的进入而自动增长，并确保没有重复。

但是，随着集合变大，插入速度会下降。那么除了哈希之外还有其他想法来完成这项工作吗？

附言

我想知道任何技巧，例如对所有元素进行异或或构建稀疏表（就像 rmq 一样）会适用吗？

4

6 回答 6

3

如果您愿意在问题上花费内存，2^32 位是 512MB，此时您可以只使用一个位字段，每个可能的整数一位。抛开 CPU 缓存影响，这给出了 O(1) 的插入和查找时间。

在不了解您的用例的更多信息的情况下，很难说这是值得使用内存还是几乎没有任何收益的巨大内存开销。

于 2012-09-15T08:41:57.773 回答
2

该站点包括所有可能的容器并为每个操作布置它们的运行时间，所以这可能会很有用：

http://en.cppreference.com/w/cpp/container

似乎建议的 unordered_set 是您最好的方法。

于 2012-09-15T08:41:49.723 回答
1

如果数字在某个范围内，那么您可以创建几个std::set作为存储桶。

编辑-根据您指定的范围，std::set,应该足够快。O(log n) 对于大多数目的来说已经足够快了，除非你做了一些测量并且发现它对你的情况来说很慢。

您也可以使用鸽洞原则来sets拒绝任何可能的重复，（当集合变大时适用）。

于 2012-09-15T08:29:43.293 回答
1

You could try a std::unordered_set, which should be implemented as a hash table (well, I do not understand why you write "besides hash"; std::set normally is implemented as a balanced tree, which should be the reason for insufficient insertion performance).

于 2012-09-15T08:35:58.763 回答
0

对于最佳决策，甚至需要更多的要求。该建议基于以下约束：Alcott 32 位整数，大约有 10.000.000 个元素（即 2^32 中的任何 10m）

它是一个 BST（二叉搜索树），其中每个节点存储两个值，即连续区域的开始和结束。第一个元素存储区域开始的数字，第二个元素存储最后一个。这种安排允许大区域，希望你用很小的树高达到 10M 的限制，所以便宜的搜索。具有 10m 个元素的数据结构将占用每个节点 8 个字节，加上每个节点最多两个子节点的链接（2x4 字节）。这样就可以为所有 10M 元素制作 80M。当然，如果通常插入更多元素，您可以跟踪一次没有插入的元素。现在，如果您需要非常小心空间，并且在运行模拟和/或统计检查后发现有很多小区域（长度小于 32 位），您可能希望将节点类型更改为一个开始的数字该区域，

如果您不必对齐对位图的访问，例如，您只有只有 8 个元素的连续块，那么您的备忘录要求是节点为 4+1，子节点为 4+4 字节。希望这可以帮助。

于 2012-09-16T22:31:23.263 回答
0

位向量可用于检测重复项

于 2012-09-15T14:23:48.537 回答