python - 在 Python 中为稀疏数组优化 `__getitem__` 和 `__setitem__`

Question

我正在编写自己的稀疏(一维)数组类，但遇到了一些性能问题。分析表明瓶颈之一是我的 __getitem__和 __setitem__实现，特别是，似乎罪魁祸首之一可能是我对 isinstance 的使用.目前我有 5 个电话给 isinstance在__getitem__我从 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}

My __getitem__ implements slicing as well as array access, so I suspect some kind of type introspection is necessary... but I'm wondering if isinstance is really the best way to do that?

My __setitem__, on the other hand, doesn't support slicing (and only calls isinstance once in any case), so I'm at a loss as to how I could make it faster. The per-line profiling data is as follows:

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

为了回答您的直接问题，isinstance() 是一个缓慢的调用，因为该名称是全局的。您可以通过将 isinstance=isinstance 添加到 __setitem__() 的签名中来显着加快速度，如下所示:

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

这会将全局名称转换为本地名称，这在运行时查找起来要快得多。作为奖励，局部名称在函数定义时绑定(bind)到内置的 isinstance 函数，因此在调用变量时没有初始化变量的开销。

然而，正如其他人所指出的，在您展示的代码中，您可能甚至不需要该调用，但可以简单地尝试将 key 转换为 int，或者跳过即使。 (但是，您可以通过将 int=int 添加到您的方法签名来获得一点速度提升，因为 int 也是一个全局名称...)

但是如果您要进行错误检查，您还应该测试索引是否小于零。如果长度为 50 而用户想要项目 -100 怎么办？ :-)