4

我想将我已经编写的一些 Python 代码翻译成 C++ 或另一种快速语言，因为 Python 的速度不够快，无法完成我想做的事情。然而，有问题的代码滥用了 Python 集合的一些令人印象深刻的特性，特别是我在性能关键循环中发送垃圾邮件的平均 O(1) 成员资格测试，而且我不确定如何用另一种语言实现 Python 集合。

在Python 的 Time Complexity Wiki Page中，它指出集合平均具有 O(1) 成员资格测试，在最坏情况下为 O(n)。我亲自对此进行了测试timeit，并且惊讶于 Python 集执行成员资格测试的速度之快，即使 N 很大。我查看了这个 Stack Overflow 答案，以了解 C++ 集在使用find操作来查看元素是否是给定的成员时如何比较设置它说它是O（log（n））。

我假设时间复杂度find是对数的，因为 C++ 标准库集是用某种二叉树实现的。我认为因为 Python 集具有平均 O(1) 成员资格测试和最坏情况 O(n)，它们可能是用某种带有桶的关联数组实现的，它可以轻松查找一个元素并测试它的一些虚拟值这表明该元素不是集合的一部分。

问题是，我不想通过切换到另一种语言来减慢代码的任何部分（因为这是我试图首先解决的问题）所以我如何实现我自己的 Python 集版本（特别是只是快速会员测试）用另一种语言？有人知道 Python 集是如何实现的吗？如果不知道，谁能给我任何一般性的提示来指出正确的方向？

我不是在寻找源代码，只是在寻找有助于我入门的一般想法和链接。

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

附加说明：我要使用的有问题的集合最多有 50,000 个元素，并且集合中的每个元素都在一个很大的范围内（比如 [-999999999, 999999999]）。

4

2 回答 2

3
  1. 理论上的差异在实践O(1)中O(log n)意义不大，尤其是在比较两种不同的语言时。log n对于 的大多数实际值来说很小n。每个实现的常数因素很容易变得更重要。
  2. C++11 有unordered_set和unordered_map现在。即使你不能使用 C++11，也总是有 Boost 版本和 tr1 版本（后者被命名hash_*而不是unordered_*）。
于 2013-09-21T08:29:22.033 回答
2

几点：正如已经指出的那样，你有，std::set并且 std::unordered_set（后者仅在 C++11 中，但大多数编译器多年来都提供了类似的扩展）。第一个由某种平衡树（通常是红黑树）实现，第二个由 hash_table 实现。哪个更快取决于数据类型：第一个需要某种排序关系（例如 <，如果它是在类型上定义的，但您可以定义自己的）；第二个是等价关系（==例如 ）和与这种等价关系兼容的散列函数。如果你有一个好的散列函数，第一个是 O(lg n)，第二个是 O(1) 。因此：

  • 如果顺序比较比散列 std::set快得多，实际上可能更快，至少对于“较小”的数据集，其中“较小”取决于差异有多大——例如，对于字符串，比较通常会在第一个几个字符，而哈希码将查看每个字符。在我（多年前）进行的一项实验中，使用 30-50 个字符的字符串，我发现盈亏平衡点约为 100000 个元素。

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

  • 最后，两者都是基于节点的容器，这意味着它们比 eg 使用更多的内存std::vector，并且局部性非常差。如果查找是主要操作，您可能需要考虑std::vector，使其保持排序并std::lower_bound用于查找。根据类型的不同，这可能会显着加快速度，并减少内存使用量。

于 2013-09-21T10:21:32.773 回答