अजगर

Question

में सूची कार्यों की लागत this older thread के आधार पर यह अजगर में सूची कार्यों की लागत की तरह लग रहा है:

• रैंडम एक्सेस: हे (1)
• निवेशन/हटाए जाने के सामने करने के लिए: O (n)
• निवेशन/विलोपन वापस करने के लिए: हे (1)

किसी को भी इस बात की पुष्टि कर सकते हैं कि क्या यह 2.6/3.x अजगर में सच अब भी है?

Answer 1

here पर एक नज़र डालें। यह एक अलग तरह की सूची के लिए एक पीईपी है। निर्दिष्ट संस्करण 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) 

Answer 2

यह सही है, सामने के बल में डालने के लिए सभी तत्वों को स्थानांतरित करने के लिए।

collections.deque समान कार्यक्षमता प्रदान करता है, लेकिन दोनों पक्षों में सम्मिलन के लिए अनुकूलित किया गया है।

Answer 3

पायथन 3 ज्यादातर एक विकासवादी परिवर्तन है, डेटास्ट्रक्चर और उनकी जटिलताओं में कोई बड़ा बदलाव नहीं है।

पाइथन संग्रह के लिए कैनोलिक स्रोत विकी पर TimeComplexity है।

Answer 4

Fwiw, एक तेज़ है (कुछ ops के लिए ... डालने ओ है (लॉग एन)) list implementation अगर आपको इसकी आवश्यकता है तो ब्लिस्ट कहा जाता है। BList

Answer 5

मुझे पता है कि यह पोस्ट पुराना है, लेकिन मैंने हाल ही में थोड़ा परीक्षण किया है।

''' 
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 पदों जहां प्रविष्टि किया जा सकता है देखें: list.insert की जटिलता() हे (एन) होने के लिए

कोड प्रकट होता है। लागत निश्चित रूप से की एक समारोह है कितनी बड़ी सूची है, और कितने करीब आप सूची की शुरुआत करने के लिए कर रहे हैं (यानी कितने स्मृति स्थल के पुनर्गठन किया जाना है)

साजिश के बाईं छवि पर ध्यान न दें