python - 单个元素的访问比列表慢

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操作执行以下操作:

b[100][100]以数组的形式返回b的第100行，然后获取该行的索引100处的值，并以对象的形式返回该值(例如np.int64类型)。

b[100,100]直接返回第100行和第100列的值(首先不返回中间数组)。

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 list 获取

在上面可以看到函数 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实际上是此函数的宏形式，它执行相同的操作(减去错误检查)。

这意味着将项目获取到Python列表的索引 i相对简单。在内部，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可以将引用( View )返回到正确的值。

总之，为NumPy找到“getitem”函数所花费的时间更长，并且处理数组索引的函数必然比Python列表的单个函数更复杂。