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


python list architecture memory memcpy
person ilya n.    schedule 10.07.2009    source источник

Ответы (3)


arrow_upward
16
arrow_downward

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

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

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

person Stephan202    schedule 10.07.2009
comment
Ну, я не говорю, что memcpy() — это O(1) — я знаю, что это O(n), но константа может быть маленькой — и я не уверен, действительно ли она оптимизирована по памяти. Но если он оптимизирован, чтобы быть, скажем, в 1000 раз быстрее, чем вы наивно думаете, об этом, вероятно, стоит знать. - person ilya n.; 10.07.2009
comment
В некоторых случаях в списке может не остаться места, поэтому после выделения новой свободной памяти необходимо скопировать весь список, а не только memmove/memcpy. - person Torsten Marek; 10.07.2009
comment
Ответ правильный, но первый абзац не обязательно верен в целом. Язык может указывать, какие операции должны быть эффективными при определенных обстоятельствах, так что даже не глядя на исходный код конкретной реализации, вы можете быть уверены в определенных свойствах производительности этих операций, предполагая, что реализация соответствует требованиям. - person LarsH; 07.04.2017

arrow_upward
11
arrow_downward

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

person Seun Osewa    schedule 10.07.2009

arrow_upward
7
arrow_downward

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

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

person Ants Aasma    schedule 10.07.2009