单个元素的访问比列表慢

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列表的单个函数更复杂。