Chi phí của các chức năng danh sách bằng Python

Question

Dựa trên this older thread, có vẻ như chi phí của các chức năng danh sách bằng Python là:

• truy cập ngẫu nhiên: O (1)
• chèn/xóa để phía trước: O (n)
• chèn/xóa để sao: O (1)

bất cứ ai có thể xác nhận liệu này vẫn còn đúng trong Python 2.6/3.x?

Answer 1

Hãy xem here. Đó là một PEP cho một loại danh sách khác. Phiên bản được chỉ định là 2.6/3.0.

Nối (chèn vào sau) là O(1), trong khi chèn (ở mọi nơi khác) là O(n). Vì vậy, có, có vẻ như điều này vẫn đúng.

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

Đúng vậy, việc chèn trước sẽ chuyển tất cả các yếu tố thành hiện thực.

collections.deque cung cấp chức năng tương tự, nhưng được tối ưu hóa để chèn ở cả hai bên.

Answer 3

Python 3 chủ yếu là thay đổi tiến hóa, không có thay đổi lớn về cơ sở dữ liệu và phức tạp của chúng.

Nguồn chuẩn cho bộ sưu tập Python là TimeComplexity trên Wiki.

Answer 4

Fwiw, có một nhanh hơn (đối với một số ops ... chèn là O (log n)) list implementation gọi là BList nếu bạn cần. BList

Answer 5

Tôi biết bài đăng này cũ, nhưng gần đây tôi đã tự làm một bài kiểm tra nhỏ. Sự phức tạp của list.insert() dường như là O (n)

Code:

''' 
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() 

Xem 5 vị trí nơi chèn có thể được thực hiện. Chi phí là tất nhiên một chức năng như thế nào lớn danh sách là, và khoảng cách giữa bạn với đầu danh sách (tức là có bao nhiêu vị trí bộ nhớ phải được tái tổ chức)

Bỏ qua hình ảnh bên trái của âm mưu