Python / Cython 中最快的查找方法

Question

我想要进行32位整数到32位整数的查找映射。

输入键不一定是连续的，也不需要覆盖2^32 -1（我也不希望在内存中消耗这么多空间！）。

这个用例是为了扑克牌评估器，所以查找必须尽可能快。完美哈希会很好，但可能有点超出范围。

我觉得答案是某种Cython解决方案，但我不确定Cython的底层情况，也不确定它是否真的能够改善Python的 dict()类型。当然，只有一个简单的偏移跳跃的平面数组会非常快，但是我不想为表格分配 2 ^ 32-1 个位置的内存。

有什么提示/策略吗？目标是绝对速度和最小内存占用。

- lollercoaster

---

“绝对速度，最小内存消耗”：你知道这里没有最佳选择，是吗？它需要一种满足工程权衡的方法，这意味着只能得到一个或两个次优选择。如果Ignacio的答案内存消耗太大，那么模块sqlite3可能是您最好的简单替代方案。 - msw

你知道你的映射将有多少条目吗？你愿意牺牲初始创建时间来加快查找吗？ - Nick Bastin

另外，“绝对速度”对您来说意味着什么？是指表的整个生命周期（包括创建时间）中消耗的总CPU周期，还是只是用于查找的周期？ - Nick Bastin

@NickBastin：初始创建时间不是问题，只有在查找完成时的时间才是关键。该表最多可能有1.33亿条目。 - lollercoaster

如果你的瓶颈将是int→int映射，那么你应该使用PyPy并使用标准的PyPy dict。对于这种用例，PyPy非常快，甚至不好笑。 - Veedrac

Answer 1

你不够聪明来写比dict更快的东西。不要觉得难过；地球上99.99999% 的人也不行。使用dict。

- Ignacio Vazquez-Abrams

---

如果有帮助的话，一旦初始化，密钥空间就完全静态 - 不需要插入。 - lollercoaster

没改变什么。 - Ignacio Vazquez-Abrams

对于很多特定的使用情况，写一个比标准的dict更快的东西其实并不难，甚至可以直接拿dict的实现进行优化并将其作为一个新对象暴露出来。dict对于一般情况非常棒且相当优化，但这也意味着存在权衡，惩罚了几乎每个特定使用情况（可能除了对字符串进行哈希的一般情况，这是dict非常擅长的）。 - Nick Bastin

Answer 2

您正在描述一个完美的哈希索引集合的使用场景。您也在描述一种完美的策略：先写代码，然后再进行优化。

因此，首先使用Python中的dict。它快速且绝对能够完成您需要的工作。

然后进行基准测试。找出它需要多快以及您离目标有多近。然后有3个选择：

1. 它足够快，您完成了。 2. 它几乎快到足够的程度，比如差不多是两倍。编写自己的哈希索引，注意哈希函数和冲突策略。 3. 它太慢了，您无法完成。没有什么简单的方法可以让您获得10倍或100倍的提高。至少您没有浪费时间在更好的哈希索引上。

- david.pfx

Answer 3

首先，在做任何事情之前，你应该确切地定义“足够快”的含义。你总是可以让某件事变得更快，因此你需要设定一个目标，以避免自己变得疯狂。这个目标可以合理地设置为双重目标——比如说，“映射查找必须在这些参数（最小值/最大值/平均值）内执行，如果我们达到了这些数字，我们会再花费X小时来进一步优化，但然后我们就会停止”。

其次，要使它更快的第一件事是复制 CPython 源树中的代码 Objects/dictobject.c（创建一个新的，例如intdict.c），然后修改它，以便键不是 Python 对象。对于整数，追求更好的哈希函数可能不是一个好的时间利用方式，但消除你的键的 INCREF/DECREF 和 PyObject_RichCompareBool 调用将是一个巨大的胜利。由于你不删除键，你还可以省略对虚拟值的任何检查（这些值存在于被删除的条目中，以保留冲突遍历），尽管通过为你的新对象提供更好的分支预测，你可能已经免费获得了大部分胜利。

- Nick Bastin

---

你是指 cython 的源代码吗？在 https://github.com/cython/cython 上？我似乎找不到那里的 Objects/dictobject.c 文件，即使使用搜索也是如此... - lollercoaster

“cpython”源代码 - Python本身的源代码（C实现）。您可以从默认的dict对象开始，只需调整它以使其更快。 - Nick Bastin