python - पायथन की सूची कैसे कार्यान्वित की जाती है?




arrays list (5)

क्या यह एक लिंक्ड सूची है, एक सरणी? मैंने चारों ओर खोज की और केवल लोगों को अनुमान लगाया। मेरा सी ज्ञान स्रोत कोड को देखने के लिए पर्याप्त नहीं है।


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

यह समझने के लिए कि क्यों ओ (1) अमूर्तता है, सामान्यता के नुकसान के बिना, मान लें कि हमने एक = 2 ​​^ एन तत्व डाले हैं, और अब हमें अपनी तालिका को 2 ^ (एन + 1) आकार में दोगुना करना है। इसका मतलब है कि हम वर्तमान में 2 ^ (एन + 1) संचालन कर रहे हैं। अंतिम प्रति, हमने 2 ^ एन ऑपरेशन किया था। इससे पहले हमने 2 ^ (एन -1) किया ... सभी तरह से नीचे 8,4,2,1। अब, अगर हम इन्हें जोड़ते हैं, तो हमें 1 + 2 + 4 + 8 + ... + 2 ^ (एन + 1) = 2 ^ (एन + 2) - 1 <4 * 2 ^ एन = ओ (2 ^ एन) = ओ (ए) कुल सम्मिलन (यानी ओ (1) अमूर्त समय)। साथ ही, यह ध्यान दिया जाना चाहिए कि यदि तालिका हटाने की अनुमति देता है तो तालिका घटने को एक अलग कारक (उदाहरण के लिए 3x) पर किया जाना चाहिए।


मैं लॉरेन लूस के लेख "पायथन सूची कार्यान्वयन" का सुझाव दूंगा । वास्तव में मेरे लिए उपयोगी था क्योंकि लेखक बताते हैं कि सूची सीपीथॉन में कैसे लागू की जाती है और इस उद्देश्य के लिए उत्कृष्ट आरेखों का उपयोग करती है।

सूची वस्तु सी संरचना

सीपीथॉन में एक सूची वस्तु निम्नलिखित सी संरचना द्वारा दर्शायी जाती है। ob_item सूची तत्वों के पॉइंटर्स की एक सूची है। आवंटित स्मृति में आवंटित स्लॉट की संख्या है।

typedef संरचना {

PyObject_VAR_HEAD

PyObject ** ob_item;

Py_ssize_t आवंटित;

} PyListObject;

आवंटित स्लॉट और सूची के आकार के बीच अंतर को ध्यान में रखना महत्वपूर्ण है। सूची का आकार लेन (एल) जैसा ही है। आवंटित स्लॉट की संख्या स्मृति में आवंटित की गई है। अक्सर, आप देखेंगे कि आवंटित आकार से अधिक हो सकता है। जब भी सूची में नए तत्व जोड़े जाते हैं, तो यह कॉलल रीयलोक की आवश्यकता से बचने के लिए है।

...

जोड़ना

हम सूची में एक पूर्णांक संलग्न करते हैं: l.append (1)। क्या होता है?

हम एक और तत्व जोड़कर जारी रखते हैं: l.append (2)। list_resize को n + 1 = 2 के साथ बुलाया जाता है, लेकिन आवंटित आकार 4 है, इसलिए अधिक स्मृति आवंटित करने की आवश्यकता नहीं है। वही बात होती है जब हम 2 और पूर्णांक जोड़ते हैं: l.append (3), l.append (4)। निम्नलिखित चित्र दिखाता है कि अब तक हमारे पास क्या है।

...

सम्मिलित करें

आइए स्थिति 1: l.insert (1,5) पर एक नया पूर्णांक (5) डालें और देखें कि आंतरिक रूप से क्या होता है।

...

पॉप

जब आप अंतिम तत्व पॉप करते हैं: l.pop (), listpop () को कॉल किया जाता है। list_resize को listpop () के अंदर बुलाया जाता है और यदि नया आकार आबंटित आकार के आधे से कम है तो सूची कम हो जाती है।

आप देख सकते हैं कि स्लॉट 4 अभी भी पूर्णांक को इंगित करता है लेकिन महत्वपूर्ण बात यह है कि सूची का आकार अब 4 है। आइए एक और तत्व पॉप करें। List_resize (), आकार - 1 = 4 - 1 = 3 आवंटित स्लॉट के आधे से भी कम है, इसलिए सूची 6 स्लॉट तक कम हो गई है और सूची का नया आकार अब 3 है।

आप देख सकते हैं कि स्लॉट 3 और 4 अभी भी कुछ पूर्णांक को इंगित करते हैं लेकिन महत्वपूर्ण बात यह है कि सूची का आकार अब 3 है।

...

पाइथन सूची ऑब्जेक्ट को निकालें एक विशिष्ट तत्व को निकालने का एक तरीका है: l.remove (5)।


यह कार्यान्वयन निर्भर है, लेकिन आईआईआरसी:

  • सीपीथन पॉइंटर्स की एक सरणी का उपयोग करता है
  • ज्योथन एक ऐरेलिस्ट का उपयोग करता है
  • आयरनपीथन स्पष्ट रूप से एक सरणी का भी उपयोग करता है। आप पता लगाने के लिए स्रोत कोड ब्राउज़ कर सकते हैं।

इस प्रकार वे सभी ओ (1) यादृच्छिक पहुंच है।


सी कोड वास्तव में बहुत सरल है। एक मैक्रो का विस्तार करना और कुछ अप्रासंगिक टिप्पणियों को listobject.h , बुनियादी संरचना listobject.h , जो एक सूची को परिभाषित करती है:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEAD में एक संदर्भ गणना और एक प्रकार पहचानकर्ता शामिल है। तो, यह एक वेक्टर / सरणी है जो कुल मिलाकर है। जब यह पूर्ण हो जाता है तो इस तरह के सरणी को आकार देने के लिए कोड listobject.c । यह वास्तव में सरणी को दोगुना नहीं करता है, लेकिन आवंटित करके बढ़ता है

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

प्रत्येक बार क्षमता के लिए, जहां newsize अनुरोधित आकार होता है (जरूरी नहीं कि allocated + 1 क्योंकि आप उन्हें एक-एक करके newsize तत्वों की मनमानी संख्या से extend कर सकते extend )।

docs.python.org/2/faq/design.html#how-are-lists-implemented भी देखें।


documentation मुताबिक,

पायथन की सूचियां वास्तव में चर-लंबाई वाली सरणी हैं, लिस्पी-स्टाइल लिंक्ड सूचियां नहीं।





python-internals