Почему тасование списка (диапазон (n)) медленнее, чем тасование [0] * n?

Question

Используя random.shuffle, я заметил, что перетасовка list(range(n)) занимает примерно на 25% больше времени, чем перетасовка [0] * n. Вот времена для размеров n от 1 миллиона до 2 миллионов:

Почему перемешивание list(range(n)) медленнее? В отличие от сортировки списка (который должен смотреть на объекты) или копирования списка (который увеличивает счетчики ссылок внутри объектов), объекты здесь не должны иметь значения. Это должно просто переставить указатели внутри списка.

Я также пытался numpy.random.shuffle, где перетасовка list(range(n)) в три раза (!) Медленнее, чем перетасовка [0] * n:

Я также попробовал третий способ перестановки элементов в списке, а именно list.reverse. Что, как и ожидалось, заняло одинаково много времени для обоих списков:

На всякий случай, если порядок перемешивания имеет значение, я также попытался list.reverse после перетасовки списки. Опять же, как и ожидалось, это заняло одинаково много времени для обоих списков, а также одинаково долго, как без предварительного перемешивания:

Так в чем же разница? Как для перетасовки, так и для реверса нужно только переставить указатели внутри списка, почему объекты имеют значение для перетасовки, а не для реверсирования?

Мой тестовый код выдает время:

import random
import numpy
from timeit import repeat, timeit
from collections import defaultdict

shufflers = {
    'random.shuffle(mylist)': random.shuffle,
    'numpy.random.shuffle(mylist)': numpy.random.shuffle,
    'list.reverse(mylist)': list.reverse,
    }

creators = {
    'list(range(n))': lambda n: list(range(n)),
    '[0] * n': lambda n: [0] * n,
    }

for shuffler in shufflers:
    print(shuffler)
    for creator in creators:
        print(creator)
        times = defaultdict(list)
        for _ in range(10):
            for i in range(10, 21):
                n = i * 100_000
                mylist = creators[creator](n)
                # Uncomment next line for pre-shuffling
                # numpy.random.shuffle(mylist)
                time = timeit(lambda: shufflers[shuffler](mylist), number=1)
                times[n].append(time)
                s = '%.6f ' * len(times[n])
        # Indent next line further to see intermediate results
        print([round(min(times[n]), 9) for n in sorted(times)])

Answer 1

(примечание: у меня не было времени закончить sh этот ответ, поэтому начнем - это определенно не вписывается в комментарий, надеюсь, это может помочь кому-то другому sh это out!)

---

это, похоже, связано с местностью ссылки (и, возможно, подробностями реализации cpython - я не вижу таких же результатов в pypy, например )

несколько точек данных перед попыткой объяснения:

random.shuffle реализован в чистом python и работает для любого типа изменяемой последовательности - это не специализируется на списках.

• это означает, что каждый своп включает __getitem__, увеличивая счет счета элемента, __setitem__, уменьшая счет счета элемента

list.reverse реализован в C и работает только для list (с использованием подробностей реализации списка)

• это означает, что каждый своп происходит без вызова __getitem__ или изменение количества ссылок. внутренние элементы списка упорядочены напрямую

, причем важным битом является счетчик ссылок

in cpython , счетчик ссылок хранится вместе с самим объектом , и почти все объекты хранятся в куче. чтобы отрегулировать счетчик ссылок (даже временно), запись на ob_refcnt переместится в структуру PyObject в кэш / память / et c.

(вот где у меня закончилось время - Я бы, наверное, сделал анализ ошибок памяти, чтобы подтвердить эту гипотезу)

Answer 2

Разница в том, что list.reverse как функция list имеет доступ к базовому массиву указателей. Таким образом, он действительно может переставлять указатели, не смотря ни на какие объекты ( source ):

reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

Функции random.shuffle и numpy.random.shuffle, с другой стороны, имеют только внешний вид и go через интерфейс списка, который включает кратковременную загрузку объектов для их замены:

random.shuffle:

    def shuffle(self, x, random=None):
        ...
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = randbelow(i+1)
                x[i], x[j] = x[j], x[i]

numpy.random.shuffle:

    def shuffle(self, object x, axis=0):
          ...
                for i in reversed(range(1, n)):
                    j = random_interval(&self._bitgen, i)
                    x[i], x[j] = x[j], x[i]

Таким образом, существует как минимум потенциал для большого количества ошибок кэша. Но давайте в качестве теста попробуем reverse in Python:

    def my_reverse(x):
        lo = 0
        hi = len(x) - 1
        while lo < hi:
            x[lo], x[hi] = x[hi], x[lo]
            lo += 1
            hi -= 1

Сравнительный тест:

Реверс list(range(n)) был так же быстр, как задний ход [0] * n, несмотря на загрузку объектов. Причина в том, что Python создает объекты в значительной степени последовательно в памяти. Вот тест с миллионами объектов. Почти все были расположены на 16 байт после предыдущего:

>>> mylist = list(range(10**6))
>>> from collections import Counter
>>> ctr = Counter(id(b) - id(a) for a, b in zip(mylist, mylist[1:]))
>>> for distance, how_often in ctr.most_common():
        print(distance, how_often)

16 996056
48 3933
-1584548240 1
-3024 1
2416 1
-2240 1
2832 1
-304 1
-96 1
-45005904 1
6160432 1
38862896 1

Так что неудивительно, что это быстро, поскольку это очень удобно для кэша.

Но теперь давайте используем наш Python реверс на перетасованный список (как в вопросе с list.reverse, где это не имеет значения):

Большой Разница в том, что my_reverse загружает объекты случайным образом повсюду, что противоположно кеш-памяти.

И, конечно, это то же самое, что происходит с функциями shuffle. В то время как list(range(n)) изначально является кеш-памятью, перестановка выбирает случайные индексы j для обмена, что очень кеш-кеш. И хотя i просто движется последовательно, он столкнется с множеством уже случайным образом поменянных объектов, так что это также недружественно для кэша.