python - 改进 Python 比较和存在操作

标签 python c performance comparison binary-search

我是 Python 的新手,希望在继续学习之前能得到一些建议。我有一组整数,我想尽快检查给定元素是否包含在该组中(速度在这里很重要)。

对于 Python,我应该查看为这些操作(BST 等)量身定制的自定义数据结构,像用 any() 包装这样的 python 技巧,或者是否有任何众所周知的 Python/C 库是这种类型的标准事物。我不想在这里重新发明轮子,所以我很想听听在 Python 中处理这个问题的常用方法。

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

谢谢!

最佳答案

正如 DMS 在评论中所说,有一个内置的 set(和不可变的变体,frozenset,这非常有用,您不需要改变和可以将值的生成放入单个生成器表达式中)。它是基于散列的,因此牺牲了分期 O(1) 成员资格测试的顺序。它是用 C 语言编写的,花在让它变得更快上的时间比你在它上面合理花费的时间还要多。如果内存没问题,它是基于字典实现的,它可能是现有最快的哈希表(用于常见用途)之一。

请注意,“散列”部分也将是 O(1),因为整数对自身进行散列。这些算法经过专门设计,可以很好地处理“非随机”(例如,有些连续的)哈希。

关于python - 改进 Python 比较和存在操作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6266641/

相关文章:

python - 重命名不同文件夹中同名的文件

python - tf.boolean_mask 不接受轴参数

c - 声明符是否有可能具有零声明说明符?

Hyperledger Fabric 的性能测试

java - sun.misc.Perf 文档或替代品

Python:一维数组循环卷积

c - C 中的双截断和数学问题

编译错误 :/usr/bin/ld: cannot find -lclntsh

c++ - 有多少 "large"对象被带入缓存?

Python 模块导入问题