Python сменные элементы

Question

Я знаю, что есть как минимум эти два метода:

array[i], array[j] = array[j], array[i]

И:

temp = array[i]
array[i] = array[j]
array[j] = temp

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

Проблема в том, что я хотел бы знать, есть ли еще более быстрый способ сделать это.

Я думал о распределении temp во внешней области видимости, чтобы его не нужно распределять при каждом вызове swap, но это не помогло.

Редактировать: я использую это для реализации минимальной кучи с десятками тысяч элементов в куче.

Также я не могу использовать numpy. Если бы массивы в python были похожи на связанные списки, лучше ли было бы имитировать истинный массив, используя словарь с индексами в качестве ключей?

Answer 1

На более низком уровне единственное различие между двумя способами обмена элементами заключается в том, что

array[i], array[j] = array[j], array[i]

выполняет ROT_TWO, чтобы поменять местами два верхних большинство элементов стека, в то время как

temp = array[i]
array[i] = array[j]
array[j] = temp

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

Answer 2

Только что увидел, что вы добавили "реализовать минимальную кучу" к вопросу. Возможно, вам удастся сделать это немного быстрее, сохранив значение «просеивающий в данный момент» в дополнительной переменной, а не внутри списка.

Замена двух элементов списка:

> python -m timeit -s "a = [1, 2]; i = 0; j = 1" "a[i], a[j] = a[j], a[i]"
2000000 loops, best of 5: 169 nsec per loop

Замена элемент списка с внешней переменной:

> python -m timeit -s "x = 1; a = [1, 2]; j = 1" "x, a[j] = a[j], x"
5000000 loops, best of 5: 101 nsec per loop

И если значение "в настоящее время отсеивается" остается тем же, вам даже не придется менять местами вообще:

> python -m timeit -s "a = [1, 2]; i = 0; j = 1" "a[i] = a[j]"
5000000 loops, best of 5: 91.3 nsec per loop

Зависит от хотя ваш код, который мы до сих пор не видим.

Answer 3

Таким образом, следующее предполагает, что массив - это python List, который в памяти действует как связанный список (а не массив, как обычно используется, например, в 'C')

Также вы не можете предварительно выделить место для переменной (как вы пытались это сделать с temp), поскольку каждая переменная в Python является только ссылкой на адрес памяти, поэтому каждый раз, когда вы делаете temp = array[i] temp будет назначаться ссылка на array[i] (которая уже находится в памяти, как и в array.

. Вы можете попробовать инвертировать список, используя list(reversed([array])) или array[::-1], в зависимости от того, что вы найдете больше

Если у вас действительно есть массив (если numpy здесь; это больше похоже на массив C), вы можете сделать

swapped_array = array[:, [1, 0]]  # Reads as 'Select all rows (:) of column 1 and then column 0 

, который должен быть моментально, когда numpy не будет перемещать элементы в памяти, а просто «назначит» столбец 1 столбцу 0 и наоборот.