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



1 Answers

عندما يقول الناس أن مجموعات تحتوي على فحص العضوية (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) .

Question

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

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




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

/* set object implementation
 Written and maintained by Raymond D. Hettinger <python@rcn.com>
 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)  
{
...



Related