Стоимость списка функций в Python

Question

На основании этого старого потока , похоже, что стоимость функций списка в Python:

• Произвольный доступ: O (1)
• Вставка / удаление на лицевую сторону: O (n)
• Вставка / удаление на оборотной стороне: O (1)

Может ли кто-нибудь подтвердить, верно ли это в Python 2.6 / 3.x?

Answer 1

Взгляните здесь . Это PEP для другого вида списка. Указана версия 2.6 / 3.0.

Append (вставка сзади) - O(1), а вставка (везде) - O(n). Так что да , похоже, это все еще верно.

Operation...Complexity
Copy........O(n) 
Append......O(1)
Insert......O(n) 
Get Item....O(1)
Set Item....O(1)
Del Item....O(n) 
Iteration...O(n)
Get Slice...O(k)
Del Slice...O(n)
Set Slice...O(n+k)
Extend......O(k) 
Sort........O(n log n)
Multiply....O(nk)

Answer 2

Python 3 - это в основном эволюционное изменение, никаких больших изменений в структурах данных и их сложностях.

Каноническим источником для коллекций Python является TimeComplexity в вики.

Answer 3

Это правильно, вставка вперед заставляет двигаться все элементы, чтобы освободить место.

collections.deque предлагает аналогичную функциональность, но оптимизирован для вставки с обеих сторон.

Answer 4

Я знаю, что этот пост старый, но я недавно провел небольшой тест самостоятельно. Сложность list.insert () выглядит как O (n)

Код:

'''
Independent Study, Timing insertion list method in python
'''
import time

def make_list_of_size(n):
    ret_list = []
    for i in range(n):
        ret_list.append(n)
    return ret_list

#Estimate overhead of timing loop
def get_overhead(niters):
    '''
    Returns the time it takes to iterate a for loop niter times
    '''
    tic = time.time()
    for i in range(niters):
        pass #Just blindly iterate, niter times
    toc = time.time()
    overhead = toc-tic
    return overhead

def tictoc_midpoint_insertion(list_size_initial, list_size_final, niters,file):
    overhead = get_overhead(niters)
    list_size = list_size_initial
    #insertion_pt = list_size//2 #<------- INSERTION POINT ASSIGMNET LOCATION 1
    #insertion_pt = 0 #<--------------- INSERTION POINT ASSIGNMENT LOCATION 4 (insert at beginning)
    delta = 100
    while list_size <= list_size_final:
        #insertion_pt = list_size//2 #<----------- INSERTION POINT ASSIGNMENT LOCATION 2
        x = make_list_of_size(list_size)
        tic = time.time()
        for i in range(niters):
            insertion_pt = len(x)//2 #<------------- INSERTION POINT ASSIGNMENT LOCATION 3
            #insertion_pt = len(x) #<------------- INSERTION POINT ASSIGN LOC 5 insert at true end
            x.insert(insertion_pt,0)
        toc = time.time()
        cost_per_iter = (toc-tic)/niters #overall time cost per iteration
        cost_per_iter_no_overhead = (toc - tic - overhead)/niters #the fraction of time/iteration, #without overhead cost of pure iteration                                              
        print("list size = {:d}, cost without overhead = {:f} sec/iter".format(list_size,cost_per_iter_no_overhead))
        file.write(str(list_size)+','+str(cost_per_iter_no_overhead)+'\n')
        if list_size >= 10*delta:
            delta *= 10
        list_size += delta

def main():
    fname = input()
    file = open(fname,'w')
    niters = 10000
    tictoc_midpoint_insertion(100,10000000,niters,file)
    file.close()

main()

См. 5 позиций, где можно выполнить вставку. Стоимость, конечно, зависит от того, насколько велик список, и насколько вы близки к началу списка (то есть, сколько мест памяти должно быть реорганизовано)

Игнорировать левое изображение сюжета

Answer 5

Между прочим, есть более быстрая (для некоторых операций ... вставка - это O (log n)) реализация списка называется BList, если вам это нужно. Blist