Выполнение списка (...). Вставка (...) - PullRequest
13 голосов
/ 10 июля 2009

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

Ответы [ 3 ]

14 голосов
/ 10 июля 2009

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

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

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

11 голосов
/ 11 июля 2009

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

6 голосов
/ 10 июля 2009

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

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

...