在python / cython中绝对最快的查找
发布时间：2020-12-20 12:07:01 所属栏目：Python 来源：网络整理
导读：我想做一个查找映射32位整数= 32位整数. 输入键不是连续的,也不是覆盖2 ^ 32 -1(我也不希望这个内存消耗那么多空间！). 用例适用于扑克评估者,因此查找必须尽可能快.完美的哈希会很好,但这可能有点超出范围. 我觉得答案是某种cython解决方案,但我不确定cytho
|
我想做一个查找映射32位整数=> 32位整数.
输入键不是连续的,也不是覆盖2 ^ 32 -1(我也不希望这个内存消耗那么多空间！). 用例适用于扑克评估者,因此查找必须尽可能快.完美的哈希会很好,但这可能有点超出范围. 我觉得答案是某种cython解决方案,但我不确定cython的基础,以及它是否真的对Python的dict()类型有任何好处.当然,只有一个简单的偏移跳跃的平面阵列会非常快,但后来我在桌子的内存中分配了2 ^ 32 – 1个位置,这是我不想要的. 任何提示/策略？绝对速度和最小的内存占用是目标. 解决方法
首先,在进行任何其他操作之前,您应该实际定义“足够快”对您意味着什么.你总是可以做得更快,所以你需要设定一个目标,这样你就不会疯狂.这个目标是双头的是完全合理的 – 例如“映射查找必须在这些参数中执行(最小/最大/平均)”,以及何时/如果我们达到这些数字,我们愿意花费更多的开发时间进一步优化,但我们会停止.“
其次,你应该做的第一件事就是复制Cpython源代码树中的Objects / dictobject.c中的代码(像intdict.c那样做一些新的东西)然后修改它以便密钥不是python对象.追求更好的哈希函数可能不会很好地利用你的整数时间,但是消除INCREF / DECREF和PyObject_RichCompareBool调用你的密钥将是一个巨大的胜利.由于你没有删除键,你也可以忽略对虚拟值的任何检查(存在以保留已删除条目的冲突遍历),尽管你可以通过更好的分支预测获得免费的大部分胜利.你的新对象. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |