Python中最快的整数数组switch等效实现

Question

我想找到在C语言中实现switch功能的最快方法。我正在写一些Python代码来替代C代码，其他部分都运行得很好，但有一个瓶颈。这段代码在一个紧密的循环中使用，所以我必须确保性能最好。

优化尝试 1： 第一次尝试是根据之前的问题，比如这个，建议使用哈希表来查找。结果发现这样做非常慢。

优化尝试 2： 我做的另一个优化是创建一系列if ... return语句，这让我速度提升了13%。不过，速度还是让人失望。

优化尝试 3： 我创建了一个包含所有可能输入值的array.array，并进行了索引查找。这使得整体速度提升了43%，这个效果还不错。

我正在使用map遍历array.array，并传递一个变换函数给它。这个函数负责查找。我的switch是针对短整数的（这是一个类型数组）。如果这是用GCC C编写的，编译器会创建一个跳转表。知道Python要么是对我的值进行哈希查找表项，要么在使用if时进行大量比较，真让人沮丧。我从性能分析中知道，慢的函数正是那些在进行查找的。

有没有比上述方法更快的方式来将一个整数映射到另一个整数，特别是在array.array上？

编辑

虽然这让我看起来像个傻瓜，因为我才意识到这一点，但我还是想说！记住，在性能分析器中运行代码会让你的代码变得非常慢，很多。在我的情况下，慢了19倍。突然间，我的瓶颈看起来没那么糟糕了！非常感谢大家的回答。这个问题仍然有效。我会把问题保持开放一段时间，因为可能会有一些有趣的答案。

使用性能分析器，对于我的测试数据集：

real    0m37.309s
user    0m33.263s
sys     0m4.002s

没有：

real    0m2.595s
user    0m2.526s
sys     0m0.028s

Answer 1

在Python中，分支逻辑通常会很慢，特别是在这种应用场景下。如果你正在处理一个紧凑的循环，并且需要在整数之间转换，你已经找到了比较好的方法。这里还有一些可以尝试的东西：

你可以试试使用 np.array，或者使用 Cython（或者直接用C语言）来处理这个紧凑的循环。这些方法需要一些额外的设置（可能还需要把内部循环用C写），但对于这种类型的应用，它们可以大幅提高速度，并且能让你利用C语言的优化器。

还有一种微优化的方法是，你可以尝试用列表推导式替代map，或者确保在map中不使用lambda函数。不在 map() 中使用lambda函数其实是个很重要的点，而列表推导式和map之间的差别通常比较小。

Answer 2

我觉得其他人建议用numpy或者纯C语言是对的；不过如果只用纯Python，这里有一些时间测试的数据，看看这些数据有什么用。根据这些数据，我有点惊讶的是，array.array的表现比dict好得多。你是在循环里面动态创建这些表格吗？还是我对你的问题理解错了？无论如何，这说明其实用list是最好的选择。

>>> def make_lookup_func(table):
...     def lookup(val, t=table):
...         return t[val]
...     return lookup
... 
>>> lookup_tuple = make_lookup_func(tuple(range(10)))
>>> lookup_list = make_lookup_func(list(range(10)))
>>> lookup_array = make_lookup_func(array.array('i', range(10)))
>>> lookup_dict = make_lookup_func(dict(zip(range(10), range(10))))
>>> %timeit lookup_tuple(9)
10000000 loops, best of 3: 177 ns per loop
>>> %timeit lookup_list(9)
10000000 loops, best of 3: 158 ns per loop
>>> %timeit lookup_array(9)
10000000 loops, best of 3: 181 ns per loop
>>> %timeit lookup_dict(9)
10000000 loops, best of 3: 166 ns per loop

扩展行为：

>>> lookup_tuple = make_lookup_func(tuple(range(10000)))
>>> lookup_list = make_lookup_func(list(range(10000)))
>>> lookup_array = make_lookup_func(array.array('i', range(10000)))
>>> lookup_dict = make_lookup_func(dict(zip(range(10000), range(10000))))
>>> %timeit lookup_tuple(9000)
10000000 loops, best of 3: 177 ns per loop
>>> %timeit lookup_list(9000)
10000000 loops, best of 3: 158 ns per loop
>>> %timeit lookup_array(9000)
10000000 loops, best of 3: 186 ns per loop
>>> %timeit lookup_dict(9000)
10000000 loops, best of 3: 195 ns per loop