在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}

我的__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

要回答您的直接问题,这isinstance()是一个缓慢的呼叫,因为名称是全局的.只需添加isinstance=isinstance到__setitem__()签名就可以显着加快速度,如下所示:

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

这会将全局名称转换为本地名称,这在运行时查找速度要快得多.作为奖励,本地名称isinstance在函数定义时绑定到内置函数,因此在调用变量时没有开始初始化变量.

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

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