Выполнение списка (...). Insert (...)

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

from bisect import bisect
index = bisect(x, a)      # O(log n)  (also, shouldn't it be a standard list function?)
x.insert(index, a)        # O(1) + memcpy()

который принимает log n, плюс, если я правильно понимаю, операцию копирования памяти для x[index:]. Теперь я недавно прочитал, что узкое место обычно находится в связи между процессором и памятью, поэтому копия памяти может быть выполнена оперативной памятью довольно быстро. Как это работает?

Ответы

Ответ 1

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

Держу пари, что ссылки на объекты в списке хранятся в непрерывной памяти (конечно, не в виде связанного списка...). Если это действительно так, то вставка с использованием x.insert приведет к x.insert всех элементов за вставленным элементом. Это может быть эффективно выполнено аппаратными средствами, но сложность все равно будет O (n).

Для небольших списков операция bisect может занять больше времени, чем x.insert, даже если первый - O (log n), а последний - O (n). Однако для длинных списков я бы x.insert предположить, что x.insert является узким местом. В таких случаях вы должны рассмотреть возможность использования другой структуры данных.

Ответ 2

Используйте blist module, если вам нужен список с лучшей производительностью вставки.

Ответ 3

Списки CPython представляют собой непрерывные массивы. Какой из элементов O (log n) bisect и O (n) доминирует над вашим профилем производительности, зависит от размера вашего списка, а также от постоянных факторов внутри O(). В частности, функция сравнения, вызванная bisect, может быть чем-то дорогостоящим в зависимости от типа объектов в списке.

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