python - ما هي بنية البيانات الأساسية لقوائم بايثون؟




list data-structures (3)

يتم تنفيذ عناصر القائمة كمصفوفات. يتم تحسينها للعمليات ذات الطول الثابت السريع وتحمل تكاليف حركة الذاكرة O (n) للبوب (0) وإدراج العمليات (0، v) التي تغير كل من حجم وموضع تمثيل البيانات الأساسية.

راجع أيضًا: http://docs.python.org/library/collections.html#collections.deque

راجع للشغل ، أجد من المثير للاهتمام أن البرنامج التعليمي بايثون على هياكل البيانات توصي باستخدام البوب ​​(0) لمحاكاة طابور ولكن لا يذكر O (n) أو خيار deque.

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

ما هي بنية البيانات الأساسية المعتادة المستخدمة لتنفيذ نوع بيانات قائمة بايثون المدمجة؟


سي بايثون:

typedef struct {
    PyObject_VAR_HEAD
    /* 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
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

كما يمكن رؤيته في السطر التالي ، يتم الإعلان عن القائمة كصفيف من المؤشرات إلى PyObjects .

PyObject **ob_item;

مع وجود قائمة مرتبطة ، لا تكون العناصر بجانب بعضها البعض ، لذلك لا يمكنك على الفور حساب موضع العنصر الأوسط في الذاكرة:

يجب عليك التكرار على جميع العناصر للحصول على العنوان للعنصر الثاني ، ثم الانتقال إلى العنصر الثاني للحصول على عنوان العنصر الثالث ، وهكذا حتى تصل إلى العنصر الخامس.







data-structures