Какова сложность выполнения функций списка 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 который отвечает на ваш вопрос.

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

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

Answer 2

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

• Это правда, что списки Python имеют осуществлялись как прилегающие векторов в реализациях C Пока что Python.

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

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

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

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

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

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

Answer 5

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

индексация занимает O(1)

для pop и снова добавить это должно быть O (1) согласно документации

Подробности смотрите по следующей ссылке:

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-anaанализ/