Numpy单个元素访问速度比列表慢

Question

我刚开始使用Numpy,并注意到迭代Numpy数组中的每个元素比执行相同但比列表更慢4倍.我现在知道这会破坏Numpy的目的,如果可能的话我应该对该函数进行矢量化.我的问题是,为什么它慢了4倍.这似乎是相当大的数额.

我使用下面的测试 %timeit

import numpy as np
b = np.eye(1000)
a = b.tolist()

%timeit b[100][100] #1000000 loops, best of 3: 692 ns per loop
%timeit a[100][100] #10000000 loops, best of 3: 70.7 ns per loop
%timeit b[100,100] #1000000 loops, best of 3: 343 ns per loop
%timeit b.item(100,100) #1000000 loops, best of 3: 297 ns per loop

我试图用它dis.dis来看看引擎盖下发生了什么,但得到了:

TypeError: don't know how to disassemble method-wrapper objects

然后我试着查看Numpy源代码,但无法确定哪个文件对应于数组元素访问.我很好奇是什么导致了额外的开销,更重要的是如何在将来为自己解决这个问题.似乎python不能轻易编译成C代码,以便我可以看到差异.但有没有办法看到为每一行生成了什么字节码,以了解差异？

Answer 1

总结:从NumPy数组中获取项目需要创建新的Python对象,而列表不是这种情况.此外,对于NumPy阵列而言,索引比使用可能增加一些额外开销的列表更复杂一些.

回顾一下,您列出的NumPy操作执行以下操作:

1. b[100][100]返回b作为数组的第100行,然后获取该行的索引100处的值,将该值作为对象返回(例如,np.int64类型).
2. b[100,100]直接返回第100行和第100列的值(不首先返回中间数组).
3. b.item(100,100)与上面相同,b[100,100]只是将值转换为本机Python类型并返回.

现在这些操作,(1)是最慢的,因为它需要两个连续的NumPy索引操作(我将解释为什么这比下面的列表索引慢).(2)最快,因为只执行一次索引操作.操作(3)可能更慢,因为它是方法调用(这些在Python中通常很慢).

为什么列表访问速度仍然快于b[100,100]？

对象创建

Python列表是指向内存中对象的指针数组.例如,列表 [1, 2, 3]不直接包含那些整数,而是指向内存地址的指针,每个整数对象都已存在.要从列表中获取项目,Python只返回对该对象的引用.

NumPy数组不是对象的集合.该数组np.array([1, 2, 3])只是一个连续的内存块,其位设置为表示这些整数值.要从此数组中获取整数,必须在与数组分开的内存中构造新的Python对象.例如,np.int64索引操作可能返回一个对象:此对象先前不存在,必须创建.

索引复杂性

另外两个原因a[100][100](从列表中获取)比b[100,100](从数组中获取)更快的原因是:

• BINARY_SUBSCR在索引列表和数组时执行字节码操作码,但它针对Python列表进行了优化.

• Python列表的内部C函数处理整数索引非常简短.另一方面,NumPy索引要复杂得多,并且执行大量代码以确定正在使用的索引类型,以便可以返回正确的值.

下面,更详细地描述了使用a[100][100]和访问列表和数组中的元素的步骤b[100,100].

字节码

列表和数组都触发相同的四个字节码操作码:

  0 LOAD_NAME                0 (a)           # the list or array
  3 LOAD_CONST               0 (100)         # index number (tuple for b[100,100])
  6 BINARY_SUBSCR                            # find correct "getitem" function
  7 RETURN_VALUE                             # value returned from list or array

注意:如果您开始对多维列表进行链索引,例如a[100][100][100],您开始重复这些字节码指令.使用元组索引的NumPy数组不会发生这种情况:b[100,100,100]仅使用四条指令.这就是随着尺寸数量的增加,时间间隔开始接近的原因.

找到正确的"getitem"功能

访问列表和数组的功能不同,每种情况都需要找到正确的功能.此任务由BINARY_SUBSCR操作码处理:

w = POP();                                            // our index
v = TOP();                                            // our list or NumPy array
if (PyList_CheckExact(v) && PyInt_CheckExact(w)) {    // do we have a list and an int?
    /* INLINE: list[int] */
    Py_ssize_t i = PyInt_AsSsize_t(w);
        if (i < 0)
             i += PyList_GET_SIZE(v);
        if (i >= 0 && i < PyList_GET_SIZE(v)) {
             x = PyList_GET_ITEM(v, i);               // call "getitem" for lists
             Py_INCREF(x);
        }
        else
            goto slow_get;
     }
     else
       slow_get:
         x = PyObject_GetItem(v, w);                  // else, call another function
                                                      // to work out what is needed
     Py_DECREF(v);
     Py_DECREF(w);
     SET_TOP(x);
     if (x != NULL) continue;
     break;

此代码针对Python列表进行了优化.如果函数看到一个列表,它将快速调用该函数PyList_GET_ITEM.现在可以在所需索引处访问此列表(请参阅下面的下一部分).

但是,如果它没有看到列表(例如我们有一个NumPy数组),它将采用"slow_get"路径.这又调用另一个函数PyObject_GetItem来检查对象映射到哪个"getitem"函数:

PyObject_GetItem(PyObject *o, PyObject *key)
{
    PyMappingMethods *m;

    if (o == NULL || key == NULL)
        return null_error();

    m = o->ob_type->tp_as_mapping;
    if (m && m->mp_subscript)
        return m->mp_subscript(o, key);
    ...

在NumPy的阵列的情况下,正确的功能位于mp_subscript在PyMappingMethods结构.

注意在调用此正确的"get"函数之前的附加函数调用.这些调用增加了开销b[100],但是多少将取决于Python/NumPy的编译方式,系统架构等等.

从Python列表中获取

在上面看到该函数PyList_GET_ITEM被调用.这是一个简短的函数,基本上看起来像这样*:

PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    if (!PyList_Check(op)) {                            // check if list
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {                    // check i is in range
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];           // return reference to object
}

*PyList_GET_ITEM 实际上是这个函数的宏形式,它做同样的事情,减去错误检查.

这意味着在iPython列表的索引处获取项目相对简单.在内部,Python检查项目的类型是否i为列表,是否在列表的正确范围内,然后返回对列表中对象的引用.

从NumPy数组获取

相比之下,NumPy必须在返回所请求索引的值之前做更多工作.

数组可以用各种不同的方式编制索引,NumPy必须决定需要哪个索引例程.各种索引例程主要由代码处理mapping.c.

用于索引NumPy数组的任何内容都会通过函数prepare_index开始解析索引并存储有关广播,维度数等信息.这是函数的调用签名:

NPY_NO_EXPORT int
prepare_index(PyArrayObject *self, PyObject *index,
              npy_index_info *indices,
              int *num, int *ndim, int *out_fancy_ndim, int allow_boolean)

 /* @param the array being indexed
  * @param the index object
  * @param index info struct being filled (size of NPY_MAXDIMS * 2 + 1)
  * @param number of indices found
  * @param dimension of the indexing result
  * @param dimension of the fancy/advanced indices part
  * @param whether to allow the boolean special case 
  */

该功能必须进行大量检查.即使对于相对简单的索引,例如b[100,100],也必须推断出许多信息,以便NumPy可以将引用(视图)返回到正确的值.

总之,找到NumPy的"getitem"函数需要更长的时间,处理数组索引的函数必然比Python列表的单个函数更复杂.