改进Python比较和存在操作

Question

我对Python相当陌生，希望在继续前进之前能够得到一些建议。我有一组整数，我想检查一个给定的元素是否包含在该组中，尽可能快（速度在这里很重要）。使用Python，我应该看看为这些操作（BST等）定制的自定义数据结构，像使用any（）包装一样的python欺骗，还是有任何这类标准的着名Python/C库的东西。我不想在这里重新发明轮子，所以我很有兴趣听到在Python中使用这种方法的常用方法。

稍微有些背景，元素都是先插入组中，之后没有任何元素出现，因此插入时间无关紧要。这似乎意味着维护一个已排序的组并进行类似二进制搜索的操作将是最好的方法，但我相信这已经实现得比我能够实现的效率高得多，并且可以在Python/C库中使用。有兴趣听到你们的想法。

谢谢！

Answer 1

最Pythonic的方式是不将它们存储在已排序的容器中，而是使用set（或不可变的变体frozenset）。这些是基于散列的容器，因此查找是O（1）。更重要的是，哈希算法是Python中的核心操作之一（用于字典和属性查找），所以它用C编写，并且写成快速。

这通常与Python的情况。使用标准容器比在Python级别上自己的滚动要快，所以尽可能使用它们。

如果您确实想将它们存储在有序列表中，请查看标准库中的bisect模块。它具有二进制搜索的标准功能。 （呃，实际上并不是，我实际上会返回搜索到的项目的索引，你必须自己做最后的比较。）它可以在C中实现它们（取决于你的配置），所以它会比你自己写的要快。

Answer 2

由于DMS在评论中说，有一个内置set（和不可变的变体，frozenset，这是非常有用的，你不需要进行变异，并可以将值的生成放入单个生成器表达式中） 。它是基于散列的，因此牺牲了分期O（1）成员资格测试的顺序。它是用C语言编写的，花费更多的时间比它可以合理花费的时间更快。如果内存是正确的，它是基于字典实现的，这个实现可以存在于固定散列表（通常用法）中。

请注意，“散列”部分也将为O（1），因为整数散列为自己。这些算法适合于非常好地处理“非随机”（例如有些连续的）哈希。