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

Я писал функцию 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)

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

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

Подробнее см. в следующей ссылке:

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