Выполнение списка (...).вставить(...)

Question

Я задумался над следующим вопросом об архитектуре компьютера.Предположим, я делаю на 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:].Недавно я прочитал, что узким местом обычно является связь между процессором и памятью, поэтому копирование в память мог бы будет сделано оперативной памятью довольно быстро.Вот как это работает?

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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