Код ниже инициализирует список случайных целых чисел и перебирает его. Учитывая subset_size
, на каждой итерации i
осуществляется доступ к подсписку i: i + subset_size
. Время доступа к подсписку растет с subset_size
. Для n = 100000
и subset_size = 50000
на моем i5 mbp требуется 15+ секунд. Я думал, что подсписки извлекаются с использованием 2 указателей и ленивых вычислений, но похоже, что за кулисами есть какой-то цикл c
, который заполняет новый список и возвращает его в результате. Является ли это правильным описанием того, что происходит на самом деле, или есть другое объяснение?
import random
from datetime import timedelta
from time import perf_counter
def example(n, subset_size):
x = [random.randint(0, 10000) for _ in range(n)]
t = perf_counter()
for i in range(n - subset_size):
_ = x[i : i + subset_size]
print(timedelta(seconds=perf_counter() - t))
if __name__ == '__main__':
example(100000, 50000)
0:00:15.131059
Проблема не в этом, на самом деле общее количество итераций равно n - subset_size
, что означает, что общее количество итераций (в данном случае 50000) уменьшается по мере роста subset_size
.
извините, я не уверен, что понимаю, что вы имеете в виду. если subset_size
растет, количество итераций уже не будет одинаковым. в вашем примере это 100 000–50 000 = 50 000 итераций, теперь, если вы увеличите subset_size
, скажем, до 80 000, вы закончите со 100 000–80 000 = 20 000 итераций. Поэтому, если вы сравните, сколько времени занимает 50 000 итераций против 20 000 итераций, вы наверняка увидите значительную разницу во времени.
Я согласен с тем, что вы сказали, но похоже, что вы утверждаете, что количество итераций растет вместе с subset_size
, что, возможно, объясняет увеличение продолжительности. Я уточняю, что это как раз наоборот, поэтому технически требуется меньше общего времени, потому что меньше количество итераций.
Хорошо, мы согласны. Таким образом, вы будете наблюдать разное время для разных значений subset_size
. Тогда в чем именно заключается ваш вопрос? Извините, я не понимаю, о чем вы спрашиваете. Вы измеряете время, необходимое для завершения цикла, и этот цикл зависит от переменной.
Вопрос в том, что происходит за кулисами, вызывая задержку, или, другими словами, почему для subset_size
из 100
требуется в 100 раз больше времени, чем для subset_size
из 1.
Срез списка не будет оцениваться лениво, список будет создаваться на каждой итерации. Используйте itertools.islice
, чтобы создать ленивый фрагмент:
islice(x, i, i + subset_size)
itertools.islice
работает с итераторами, а не с последовательностями. Он не будет выполнять эффективную ленивую арифметику индекса для обработки среза; он будет рассматривать x
как общую итерацию, извлекать итератор и перебирать элементы один за другим, пока не достигнет индекса i
, а затем начнет выдавать элементы оттуда. Это крайне неэффективно.
Я проверил, он работает, как и ожидалось, лениво. Итератор не выполняет итерацию элементов при создании
Он не будет повторяться при создании, но как только вы попытаетесь получить хотя бы один элемент, он будет повторяться. (Конечно, код в вопросе не пытается это сделать, но если все, что вам нужно, это реализация, которая работает до тех пор, пока вы не пытаетесь что-либо с ней сделать, вы можете просто использовать None
и притвориться, что это ваша кусочек.)
Вопрос касался ленивого создания, и предоставленный образец делает это с islice.
Я думал, что подсписки извлекаются с использованием 2 указателей и ленивых вычислений. но похоже, что за кулисами есть какая-то петля c, которая заполняет новый список и возвращает его как результат.
Ваше предположение верно. разрезание списка всегда создает новый список. Вот соответствующая часть исходного кода. Я добавил несколько комментариев, чтобы понять, что происходит на каждом этапе.
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
PyListObject *np;
PyObject **src, **dest;
Py_ssize_t i, len;
len = ihigh - ilow;
if (len <= 0) {
return PyList_New(0);
}
# create new list which is long enough to hold the slice length elements.
np = (PyListObject *) list_new_prealloc(len);
if (np == NULL)
return NULL;
# Adjust the pointer offset, because list internally uses an array of pointers.
src = a->ob_item + ilow;
dest = np->ob_item;
# Copy the elements back.
for (i = 0; i < len; i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
Py_SET_SIZE(np, len);
return (PyObject *)np;
}
Как вы можете видеть, когда вы нарезаете список, он должен сначала вызвать list_new_prealloc, где создается пустой список и выделяется память до длины среза.
static PyObject *
list_new_prealloc(Py_ssize_t size)
{
assert(size > 0);
# Create new list
PyListObject *op = (PyListObject *) PyList_New(0);
if (op == NULL) {
return NULL;
}
assert(op->ob_item == NULL);
# Allocating memory
op->ob_item = PyMem_New(PyObject *, size);
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
op->allocated = size;
return (PyObject *) op;
}
Нарезка списка не выполняется лениво и действительно создает новый объект списка; см., например, Неофициальное введение в Python, раздел 3.1.3. Списки:
Все операции над срезами возвращают новый список, содержащий запрошенные элементы.
Возможно, я что-то упускаю, но количество итераций вашего цикла for зависит от значения
subset_size
. Еслиsubset_size == n
вы повторяете 0 раз, но еслиsubset_size == 0
вы выполняете цикл n раз. Вы измеряете время, необходимое для завершения цикла for, поэтому повторение разного количества раз наверняка повлияет на то, сколько времени потребуется для завершения.