Какова сложность времени выполнения функций списка Python?

Question

Я писал функцию Python, которая выглядела примерно так

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

чтобы оно вызывалось с

x = [0, 1, 2, 3, ... ]
foo(x)

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

Тогда мой вопрос: как реализованы списки Python и какова сложность во время выполнения следующего

• Индексирование: list[x]
• Отрываясь от конца: list.pop()
• Отпуск с начала: list.pop(0)
• Расширение списка: list.append(x)

Для дополнительного кредита, сплайсинга или произвольных всплывающих окон.

Answer 1

есть очень подробная таблица на Python Wiki , которая отвечает на ваш вопрос.

Однако в вашем конкретном примере вы должны использовать enumerate, чтобы получить индекс итерируемого в цикле. вот так:

for i, item in enumerate(some_seq):
    bar(item, i)

Answer 2

Ответ "неопределен". Язык Python не определяет базовую реализацию. Вот несколько ссылок на ветку списка рассылки, которая может вас заинтересовать.

• Это правда, что списки Python имеют был реализован как смежный векторы в реализациях C Пока Python.

• Я не говорю, что O () поведение этих вещей должно быть держал в секрете или что-нибудь. Но ты нужно интерпретировать их в контексте о том, как Python работает в целом.

Кроме того, более Pythonic способ написания вашего цикла будет следующим:

def foo(some_list):
   for item in some_list:
       bar(item)

Answer 3

Списки действительно O (1) для индексации - они реализованы как вектор с пропорциональным перераспределением, поэтому выполняйте столько, сколько вы ожидаете. Вероятная причина, по которой вы нашли этот код медленнее, чем вы ожидали, - это вызов "range(0, len(some_list))".

range() создает новый список указанного размера, поэтому, если у some_list есть 1 000 000 элементов, вы заранее создадите новый список миллионов элементов. Это поведение изменяется в python3 (диапазон является итератором), для которого эквивалент python2 равен xrange , или даже лучше для вашего случая, перечисление

Answer 4

Пока не можете комментировать, поэтому

если вам нужны индекс и значение, используйте перечисление:

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item

Answer 5

Список Python на самом деле ничего, кроме массивов. Таким образом,

индексирование занимает O (1)

для всплывающих окон и добавлений снова должно быть O (1) согласно документации

Проверьте следующую ссылку для деталей:

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/