Различия в реализации и производительности между методом Python insert() и вставкой путем нарезки

Question

В чем разница между вставкой элемента в список python следующими способами?

myList.insert(at, myValue) 
myList[at:at] = [myValue] 

Я провел несколько тестов, и характеристики этих двух очень похожи, но нарезка вставки последовательно дает несколько лучшие результаты. Мой вопрос касается различия в реализации и производительности, а не поведения.

Answer 1

У нас есть такое же поведение, см ниже:

поведения

по умолчанию для вставки элемента по данному индексу; каждое значение при большем индексе сдвигается на одну позицию до конца.

>>> my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
>>> my_list.insert(5, 'item') 
>>> my_list 
['a', 'b', 'c', 'd', 'e', 'item', 'f', 'g'] 

>>> my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
>>> my_list.insert(-3, 'item') 
>>> my_list 
['a', 'b', 'c', 'd', 'item', 'e', 'f', 'g'] 

Если список пуст, элемент прилагается в обычном порядке.

>>> my_list = [] 
>>> my_list.insert(5, 'item') 
>>> my_list 
['item'] 

>>> my_list = [] 
>>> my_list.insert(-3, 'item') 
>>> my_list 
['item'] 

Если индекс выходит за пределы границ, элемент добавляется в конец, если индекс является положительным или к началу, если отрицательный. Исключено исключение.

>>> my_list = ['a', 'b'] 
>>> my_list.insert(5, 'item') 
>>> my_list 
['a', 'b', 'item'] 

>>> my_list = ['a', 'b'] 
>>> my_list.insert(-3, 'item') 
>>> my_list 
['item', 'a', 'b'] 

Мы имеем точно такое же поведение с ломтиком нотации, в случае диапазона одних и тех же показателей:

>>> my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
>>> my_list[5:5] = ['item'] 
>>> my_list 
['a', 'b', 'c', 'd', 'e', 'item', 'f', 'g'] 

>>> my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
>>> my_list[-3:-3] = ['item'] 
>>> my_list 
['a', 'b', 'c', 'd', 'item', 'e', 'f', 'g'] 

>>> my_list = [] 
>>> my_list[5:5] = ['item'] 
>>> my_list 
['item'] 

>>> my_list = [] 
>>> my_list[-3:-3] = ['item'] 
>>> my_list 
['item'] 

>>> my_list = ['a', 'b'] 
>>> my_list[5:5] = ['item'] 
>>> my_list 
['a', 'b', 'item'] 

>>> my_list = ['a', 'b'] 
>>> my_list[-3:-3] = ['item'] 
>>> my_list 
['item', 'a', 'b'] 

Срез обозначения те же, как вызов __setitem__() метод с slice объекта:

>>> my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
>>> my_list.__setitem__(slice(5, 5), ['item']) 
>>> my_list 
['a', 'b', 'c', 'd', 'e', 'item', 'f', 'g'] 

Answer 2

детали реализации

Согласно реализации CPython доступны на GitHub в https://github.com/python/cpython/blob/master/Objects/listobject.c и https://github.com/python/cpython/blob/master/Objects/listobject.c, мы имеем:

Метод insert() определяется в следующей функции:

static PyObject * 
listinsert(PyListObject *self, PyObject *args) 
{ 
    Py_ssize_t i; 
    PyObject *v; 
    if (!PyArg_ParseTuple(args, "nO:insert", &i, &v)) 
     return NULL; 
    if (ins1(self, i, v) == 0) 
     Py_RETURN_NONE; 
    return NULL; 
} 

Что вызывает ins1() функцию, здесь является C код:

static int 
ins1(PyListObject *self, Py_ssize_t where, PyObject *v) 
{ 
    Py_ssize_t i, n = Py_SIZE(self); 
    PyObject **items; 
    if (v == NULL) { 
     PyErr_BadInternalCall(); 
     return -1; 
    } 
    if (n == PY_SSIZE_T_MAX) { 
     PyErr_SetString(PyExc_OverflowError, 
      "cannot add more objects to list"); 
     return -1; 
    } 

    if (list_resize(self, n+1) < 0) 
     return -1; 

    if (where < 0) { 
     where += n; 
     if (where < 0) 
      where = 0; 
    } 
    if (where > n) 
     where = n; 
    items = self->ob_item; 
    for (i = n; --i >= where;) 
     items[i+1] = items[i]; 
    Py_INCREF(v); 
    items[where] = v; 
    return 0; 
} 

вызов ломтика осуществляется с помощью функции PyList_SetSlice():

int 
PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) 
{ 
    if (!PyList_Check(a)) { 
     PyErr_BadInternalCall(); 
     return -1; 
    } 
    return list_ass_slice((PyListObject *)a, ilow, ihigh, v); 
} 

Оптимизированной реализации осуществляется в:

static int 
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) 

Вставка делается в следующем фрагменте коды:

else if (d > 0) { /* Insert d items */ 
    k = Py_SIZE(a); 
    if (list_resize(a, k+d) < 0) 
     goto Error; 
    item = a->ob_item; 
    memmove(&item[ihigh+d], &item[ihigh], 
     (k - ihigh)*sizeof(PyObject *)); 
} 
for (k = 0; k < n; k++, ilow++) { 
    PyObject *w = vitem[k]; 
    Py_XINCREF(w); 
    item[ilow] = w; 
} 

Надеется, что это помогает!