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

Ответ 1

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

Добавление (вставка назад) 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)

Ответ 2

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

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

Ответ 3

Правильно, вставляя передние силы, перемещайте все элементы на место.

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

Ответ 4

Fwiw, существует более быстрый (для некоторых ops... insert is O (log n)) реализация списка называется BList, если вы нужно это. BList

Ответ 5

Я знаю, что этот пост старый, но я недавно немного поработал. Сложность 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 позиций, в которых можно выполнить вставку. Стоимость, конечно же, зависит от того, насколько велик список и насколько близко вы к началу списка (т.е. Сколько мест памяти необходимо перестроить).

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