python - كيف يتم ضبط()تنفيذها؟




data-structures set cpython (5)

للتأكيد أكثر على الفرق بين set's dict's ، هنا مقتطف من أقسام التعليقات setobject.c ، التي توضح الفرق الرئيسي في المجموعة ضد dicts.

تختلف حالات الاستخدام للمجموعات اختلافًا كبيرًا عن القواميس حيث من المرجح أن تكون المفاتيح المدروسة موجودة. في المقابل ، تكون المجموعات في المقام الأول حول اختبار العضوية حيث لا يكون وجود العنصر معروفًا مسبقًا. وبناءً على ذلك ، يحتاج التنفيذ المحدد إلى التحسين لكل من الحالة الموجودة وغير الموجودة.

المصدر على github

لقد رأيت الناس يقولون أن set الأجسام في الثعبان لديها O (1) التحقق من العضوية. كيف يتم تنفيذها داخليًا للسماح بذلك؟ ما نوع بنية البيانات التي يستخدمها؟ ما هي الآثار الأخرى التي ينطوي عليها هذا التنفيذ؟

كل إجابة هنا كانت مفيدة حقًا ، ولكن لا يمكنني قبول سوى واحدة ، لذلك سأذهب مع أقرب إجابة لسؤالي الأصلي. شكر جميع للمعلومات!


وفقا لهذا الموضوع :

في الواقع ، يتم تنفيذ مجموعات CPython كشيء مثل القواميس مع القيم الوهمية (المفاتيح التي هي أعضاء المجموعة) ، مع بعض التحسينات (التحسينات) التي تستغل هذا الافتقار للقيم

لذلك ، تستخدم set أساسًا هيكلًا قابلاً للتخزين كالبنية الأساسية للبيانات. وهذا ما يفسر التحقق من العضوية في O (1) ، حيث إن عملية البحث عن عنصر في جدول قابل للتسجيل هو عملية O (1) ، في المتوسط.

إذا كنت تميل إلى حد كبير ، يمكنك أيضًا تصفّح شفرة مصدر CPython للمجموعة ، والتي وفقًا لـ Achim Domma ، تكون في الغالب قصًا ولصقًا من تنفيذ dict .


لدينا جميعًا سهولة الوصول إلى المصدر ، حيث يقول التعليق السابق set_lookkey() :

/* set object implementation
 Written and maintained by Raymond D. Hettinger <[email protected]>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...

عندما يقول الناس أن مجموعات تحتوي على فحص العضوية (1) ، فإنهم يتحدثون عن الحالة العادية . في أسوأ الحالات (عندما تتصادم كل قيم التجزئة) ، يكون التحقق من العضوية هو O (n). انظر بايثون ويك في تعقيد الزمن .

تقول مقالة Wikipedia أن تعقيد وقت حالة أفضل لجدول تجزئة لا يتغير حجمه هو O(1 + k/n) . لا تنطبق هذه النتيجة مباشرة على مجموعات Python نظرًا لأن مجموعات Python تستخدم جدول تجزئة يتغير حجمه.

وقليلاً قليلاً على مقالة Wikipedia تقول أنه بالنسبة للحالة المتوسطة ، وعلى افتراض دالة تجزئ موحدة بسيطة ، فإن تعقيد الوقت هو O(1/(1-k/n)) ، حيث يمكن تقييد k/n بواسطة c<1 ثابتًا. c<1 .

يشير Big-O فقط إلى السلوك المقارب مثل n → ∞. بما أن k / n يمكن أن يحدها ثابت ، c <1 ، بغض النظر عن n ،

O(1/(1-k/n)) ليس أكبر من O(1/(1-c)) وهو ما يعادل O(constant) = O(1) .

وبافتراض تجزئة بسيطة موحدة ، في المتوسط ، فإن التحقق من العضوية لمجموعات بايثون هو O(1) .


هناك متغير آخر قابل للقراءة جدًا لـ Python 3.4 أو أحدث يستخدم pathlib.Path.glob:

print(files_list)
['file1.txt', 'file2.txt', .... ]

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

import os
[f for f in os.listdir(os.getcwd) if ...]




python data-structures set cpython