优化Python中稀疏数组的`__getitem__`和`__setitem__`

Question

我正在写一个自己的稀疏（一维）数组类，但遇到了一些性能问题。通过分析，我发现瓶颈之一可能是我的 __getitem__ 和 __setitem__ 的实现，特别是我使用 isinstance 的地方。现在在 __getitem__ 中我调用了 5 次 isinstance，从 cProfile 得到的数据如下：

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    86462    0.076    0.000    0.084    0.000 sparse.py:107(__setitem__)
   189730    0.147    0.000    0.166    0.000 sparse.py:45(__getitem__)
   276366    0.028    0.000    0.028    0.000 {built-in method isinstance}

我的 __getitem__ 不仅实现了数组访问，还支持切片，所以我觉得某种类型检查是必要的……但我在想，使用 isinstance 真的是最好的方法吗？

另一方面，我的 __setitem__ 不支持切片（而且在任何情况下只调用 isinstance 一次），所以我不知道怎么才能让它更快。每行的分析数据如下：

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
   108                                              @profile
   109                                              def __setitem__(self, key, value):
   110     88705       121012      1.4     23.0         if not isinstance(key, int):
   111                                                      raise TypeError('list indices must be be integers')
   112                                                  
   113     88705        95905      1.1     18.3         if key >= self._length:
   114                                                      raise IndexError('list index out of range')
   115                                                  
   116     88705        85328      1.0     16.2         if key < 0:
   117                                                      key = self._length + key
   118                                                  
   119     88705        89186      1.0     17.0         if value == self._default:
   120     35043        37087      1.1      7.1             if key in self._entries:
   121     35042        39359      1.1      7.5                 del self._entries[key]
   122                                                  else:
   123     53662        57527      1.1     10.9             self._entries[key] = value

（我也愿意接受建议，推荐一个合适的快速稀疏数组 Python 模块。我的一个要求是能够快速遍历非零条目的键。）

Answer 1

那我们来看看怎么去掉这些异常吧？

def __setitem__(self, key, value):
   # This checks that:
   # - key is an integer (or can be converted to an integer)
   # - key is replaced by an appropriate positive value when < 0
   # - key is made = self._length when key >= self._length (not exactly as before)
   key = slice(key).indices(self._length)[1]

   if value == self._default:
       self._entries.pop(key, None) # assuming _entries is of type dict
   else:
       self._entries[key] = value

Answer 2

你可以试着把...

if not isinstance(key,int):
    raise TypeError('list indices must be integers')

...换成...

key = int(key)

我觉得这样做会更快，而且如果有人给你的函数传入可以转换成整数的东西，它也能正常工作，这样会更灵活。

---

你也可以考虑直接不检查键的类型。只需说明使用非int类型的东西是未定义的行为，这样就由用户自己负责确保他们正确使用。

Answer 3

为了回答你的问题，isinstance()这个函数比较慢，因为它是全局的。你可以通过在__setitem__()的参数中加上isinstance=isinstance来让它快很多，像这样：

def __setitem__(self, key, value, isinstance=isinstance):
    # und so weiter

这样做会把全局的名字转换成局部的名字，这样在运行时查找会快很多。而且，局部名字在函数定义的时候就和内置的isinstance函数绑定了，所以在调用的时候不会有额外的开销。

不过，正如其他人所说的，在你提供的代码中，其实你可能根本不需要调用这个函数，可以直接尝试把键转换成int，或者干脆不做这个转换。（不过，如果你在方法参数中加上int=int，也能稍微提高速度，因为int也是一个全局名字……）

但是如果你要进行错误检查，还应该测试一下索引是否小于零。比如说，如果长度是50，而用户想要的是-100这个项，那该怎么办呢？:-)