如何在另一种语言中（可能是C++）实现Python集合？

Question

我想把已经写好的Python代码翻译成C++或其他更快速的语言，因为Python并不够快以完成我想做的事情。但是，所涉及的代码滥用了Python集合的一些卓越特性，特别是平均O(1)成员测试，这在关键性能循环中被频繁使用，我不确定如何在另一种语言中实现Python集合。

在Python的时间复杂度维基页面上，它指出集合具有平均O(1)的成员测试和最坏的情况O(n)。我亲自使用timeit进行了测试，惊讶于Python集合执行成员测试的极快速度，即使N很大。我查看了此Stack Overflow答案，看看当使用find操作来查找给定集合中的元素是否是成员时，C++集合的表现如何，它说它是O(log(n))。

我假设find的时间复杂度是对数级别的，因为C ++ std库集合是用某种二叉树实现的。我认为这是因为Python集合具有平均O（1）成员测试和最坏情况O（n），它们可能是使用带有桶的某种关联数组实现的，可以轻松查找元素并测试其是否为一些指示该元素不是集合一部分的虚拟值。

问题在于，我不想通过切换到另一种语言来减慢代码的任何部分（因为这是我试图解决的问题），那么我如何在另一种语言中实现自己的Python集合版本（仅特别快速的成员测试）？ 有人知道Python集合的实现方式吗？如果不知道，是否有人能给我任何一般提示以指引我正确的方向？

我不需要源代码，只需要一般想法和链接，以帮助我入门。

我已经对关联数组进行了一些研究，我认为我理解了它们实现背后的基本思想，但我不确定它们的内存使用情况。如果Python集合确实只是真正的关联数组，那么我如何以最小的内存使用实现它们？

额外说明：我想使用的这些集合将具有高达50,000个元素，并且集合中的每个元素都将在一个大范围内（例如[-999999999，999999999]）。

- Shashank

---

如果你想在C++中进行O(1)查找，请使用std::unordered_set。然而，50000个元素并不算太多，使用标准的std::set只需要不到16次比较就可以完成查找。 - Oliver Charlesworth

我肯定想要O(1)的查找，因为我在循环内有多个查找。感谢您提供unordered_sets的链接，我不知道std库有这个功能。这可能会为我节省很多麻烦。 - Shashank

Answer 1

1. O(1)和O(log n)之间的理论差异在实践中意义不大，特别是当比较两种不同的语言时。对于大多数实际值的n来说，log n是很小的。每个实现的常量因素更容易更显著。
2. C++11现在有unordered_set和unordered_map。即使您不能使用C++11，也总会有Boost版本和tr1版本（后者命名为hash_*而不是unordered_*）。

- n. m.

---

谢谢，我会记住你的建议。我会先尝试使用 set，如果速度不够快，我会使用 unordered_set。我想当我考虑到 n 为 50k 时，O(log(n)) 其实并不算很大。 - Shashank

@ShashankGupta 很多年前我进行了一项测试，std::set和我的哈希表实现之间的盈亏平衡点大约在10万个元素左右。然而，这非常取决于集合中的内容；对于比较次数，std::set是O(lg n)；如果你有一个好的哈希函数，std::unordered_set是O(1)。根据数据不同，计算一个好的哈希可能需要与几十个或更多的比较一样多的时间，也可能不需要。这取决于数据。(顺便说一句：Python使用哈希表。如果你创建自己的类型，并给它一个糟糕的__hash__，它将非常慢。) - James Kanze

Answer 2

几点需要注意：正如其他人指出的那样，你可以使用`std::set`和`std::unordered_set`(后者仅在C++11中，但大多数编译器现在都提供了类似的扩展)。前者使用一种平衡树(通常是红黑树)实现，后者使用哈希表。哪一个更快取决于数据类型:前者需要某种排序关系(例如，如果它在类型上定义了<)，但你也可以自己定义; 后者需要等价关系(例如"==")和与此等价关系兼容的哈希函数。前者是O(lg n)，后者是O(1)，只要你有一个好的哈希函数。因此:

• 如果用于比较顺序的时间显著比哈希快，那么对于“较小”的数据集，`std::set`可能实际上更快，其中“较小”取决于差异有多大-例如，对于字符串，比较通常会在前几个字符之后解决，而哈希码将查看每个字符。在我做过的一个实验中(很多年前)，针对30-50个字符的字符串，我发现平衡点大约是10万个元素。

• 对于某些数据类型，仅找到一个与该类型兼容的好哈希函数可能很困难。Python使用哈希表来存储其集合，如果你定义一个具有始终返回1的`__hash__`函数的类型，它将非常非常慢。编写一个好的哈希函数并不总是显而易见。

• 最后，两者都是基于节点的容器，这意味着它们使用的内存比如`std::vector`多得多，而且局部性很差。如果查找是主要操作，你可能需要考虑使用`std::vector`，并使其保持排序状态，并使用`std::lower_bound`进行查找。根据类型，这可以导致显着的加速和更少的内存使用量。

- James Kanze