Как упорядочить существующий список чисел Python последовательно в памяти?

Question

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

https://rickystewart.wordpress.com/2013/09/03/why-sorting-an-array-makes-a-python-loop-faster/

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

import copy
a = [i for i in range(1000000)]
shuffle(a)
# Approach 1
a = copy.deepcopy(a)

Однако это не улучшило производительность, предполагая, что элементы не переупорядочиваются последовательно в памяти.

Я также попробовал следующие модификации после перетасовки, что также не улучшило производительность.

# Approach 2
a = [x for x in a]

# Approach 3
a = [copy.deepcopy(x) for x in a]

Следующий подход повышает производительность, предполагая, что элементы переупорядочиваются в памяти.

# Approach 4
a = [x+0 for x in a]

Мой вопрос: почему подходы с 1 по 3 не переупорядочивают элементы в памяти, тогда как подход 4 делает это?

Есть ли предлагаемый способ сделать это, отличный от подхода 4?

Answer 1

Это сводится к тому, создаете ли вы новые объекты или нет. Оказывается, подходы с 1 по 3 не создают новые объекты, вот почему.

Подход 1 и 3: ❌

Хотя они выглядят по-разному, эти два подхода одинаковы. При вызове copy.deepcopy для целого числа (или любого неизменяемого встроенного типа) модуль copy использует следующий метод.

def _deepcopy_atomic(x, memo):
    return x

Поэтому, когда вы копируете целое число глубже, возвращается тот же самый объект . Точно так же, глубокое копирование списка целых чисел фактически возвращает поверхностную копию.

from copy import deepcopy

l = [1000]
print(l[0] is deepcopy(l)[0]) # True

Подход 2: 101

Делая [x for x in a], вы тривиально создаете новый список с точно такими же объектами. Вот проверка здравомыслия.

l1 = [1000]
l2 = [x for x in l1]

print(l1[0] is l2[0]) # True

Подход 4: ✅

Теперь этот подход фактически создает новый объект для целых чисел больше 256.

x = 1000
print(x is x + 0) # False

Последнее слово

Хотя последний подход является единственным, который фактически создает новый объект, я не смог найти ничего в документе, утверждающем, что это свойство языка. Так что имейте в виду, что это может зависеть от реализации и что весьма вероятно, что возникнет интерпретация, которая оптимизирует x + 0, чтобы всегда возвращать один и тот же объект.