在pythoncython中绝对最快的查找

概述我想做一个查找映射32位整数=> 32位整数. 输入键不是连续的,也不是覆盖2 ^ 32 -1(我也不希望这个内存消耗那么多空间！). 用例适用于扑克评估者,因此查找必须尽可能快.完美的哈希会很好,但这可能有点超出范围. 我觉得答案是某种cython解决方案,但我不确定cython的基础,以及它是否真的对Python的dict()类型有任何好处.当然,只有一个简单的偏移跳跃的平面阵列会非常快,但后 我想做一个查找映射32位整数=> 32位整数.

输入键不是连续的,也不是覆盖2 ^ 32 -1(我也不希望这个内存消耗那么多空间！).

用例适用于扑克评估者,因此查找必须尽可能快.完美的哈希会很好,但这可能有点超出范围.

我觉得答案是某种cython解决方案,但我不确定cython的基础,以及它是否真的对Python的dict()类型有任何好处.当然,只有一个简单的偏移跳跃的平面阵列会非常快,但后来我在桌子的内存中分配了2 ^ 32 – 1个位置,这是我不想要的.

任何提示/策略？绝对速度和最小的内存占用是目标.

解决方法 首先,在进行任何其他 *** 作之前,您应该实际定义“足够快”对您意味着什么.你总是可以做得更快,所以你需要设定一个目标,这样你就不会疯狂.这个目标是双头的是完全合理的 – 例如“映射查找必须在这些参数中执行(最小/最大/平均)”,以及何时/如果我们达到这些数字,我们愿意花费更多的开发时间进一步优化,但我们会停止.“

其次,你应该做的第一件事就是复制cpython源代码树中的Objects / dictobject.c中的代码(像intdict.c那样做一些新的东西)然后修改它以便密钥不是python对象.追求更好的哈希函数可能不会很好地利用你的整数时间,但是消除INCREF / DECREF和PyObject_RichCompareBool调用你的密钥将是一个巨大的胜利.由于你没有删除键,你也可以忽略对虚拟值的任何检查(存在以保留已删除条目的冲突遍历),尽管你可以通过更好的分支预测获得免费的大部分胜利.你的新对象.

总结

以上是内存溢出为你收集整理的在python / cython中绝对最快的查找全部内容，希望文章能够帮你解决在python / cython中绝对最快的查找所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。