改进Python比较和存在操作

Question

我是Python的新手,希望在向前推进之前能得到一些建议.我有一组整数,我想检查一个给定的元素是否尽可能快地包含在该组中(速度在这里很重要).

使用Python,我应该看看为这些操作(BST等)定制的自定义数据结构,python技巧,如使用any()包装,还是有任何众所周知的Python/C库是这类事情的标准.我不想在这里重新发明轮子,所以我很想知道在Python中使用它的常用方法.

更多背景,元素都预先插入到组中,之后没有发生,因此插入时间无关紧要.这似乎意味着维护一个已排序的组并执行类似二进制搜索的操作将是最好的方法,但我确信这已经实现得比我实现的更有效,并且可以在Python/C lib中使用.有兴趣听听你们的想法.

谢谢!

Answer 1

最Pythonic方式是不将它们存储在已排序的容器中,而是使用set(或不可变的变体frozenset).这些是基于散列的容器,因此查找是O(1).更重要的是,散列算法是Python中的核心操作之一(用于字典和属性查找),因此它用C语言编写,并且写得很快.

这通常是Python的情况.使用标准容器比在Python级别滚动自己更快,所以尽量使用它们.

如果您确实希望将它们存储在已排序的列表中,请查看bisect标准库中的模块.它具有二进制搜索的标准功能.(好吧,实际上并非如此.我实际上返回了搜索项目所在的索引.你必须自己做最后的比较.)它可以在C中实现它们(取决于你的配置),所以它会比你自己写的要快.

Answer 2

正如DMS在评论中所说,有一个内置的set(和不可变的变体,frozenset这是非常有用的,你不需要变异,并且可以将值生成适合单个生成器表达式).它是基于散列的,因此牺牲了摊销的O(1)成员资格测试的顺序.它是用C语言编写的,并且有更多的时间用于使它快速合理地花费在它上面.如果内存服务正确,它基于字典实现,它可以存在于紧急哈希表(常见用法)中.

请注意,"哈希"部分也将是O(1),因为整数哈希自己.算法适合于非常好地处理"非随机"(例如,稍微连续)的散列.