تنفيذ القاموس في بيثون

مرحبًا بالجميع ، في 30 أبريل ، ستبدأ دورة " الخوارزميات للمطورين" في OTUS ، وهذا هو بالضبط ما يتم تخصيصه لنشر مواد اليوم. لنبدأ.



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

>>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3} 

يمكن الوصول إلى القيم كما يلي:

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd' 

المفتاح “d” غير موجود ، لذلك سيحدث خطأ KeyError.

تجزئة الجداول

يتم تطبيق القواميس في بيثون باستخدام جداول التجزئة. إنها صفائف يتم حساب مؤشراتها باستخدام وظائف التجزئة. الهدف من دالة التجزئة هو توزيع المفاتيح بالتساوي في الصفيف. دالة هاش جيدة تقلل من عدد الاصطدامات ، أي احتمال أن مفاتيح مختلفة سيكون لها نفس التجزئة. لا توجد وظائف التجزئة في بيثون. وظائف التجزئة الأكثر أهمية (للسلاسل والقيم الصحيحة) تنتج قيمًا متشابهة في الحالات العامة:

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462] 

سنفترض أننا حتى نهاية هذه المقالة سنستخدم الأوتار كمفاتيح. يتم تعريف دالة التجزئة في بيثون للسلاسل على النحو التالي:

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash 

إذا قمت بتنفيذ hash('a') في Python ، فسيتم 12416037344 string_hash() وإرجاع 12416037344 . نحن هنا نستخدم آلة 64 بت بشكل افتراضي.

إذا تم استخدام صفيف من الحجم لتخزين أزواج القيمة / المفتاح ، فسيتم استخدام قناع لحساب فهرس خلية الخلية في الصفيف ، والذي يتم حسابه على شكل -1 . هذا النهج يجعل حساب مؤشرات الخلية سريعة. احتمال العثور على خلية فارغة مرتفع جدًا بسبب آلية تغيير الحجم الموضحة أدناه. هذا يعني أن الحساب البسيط منطقي في معظم الحالات. حجم المصفوفة هو 8 ، وسيكون فهرس 'a' هو: hash('a') & 7 = 0 . مؤشر 'b' هو 2 ، ومؤشر 'c' هو 3 ، ومؤشر 'z' هو 3 ، تمامًا مثل 'b' ، وهذا هو المكان الذي نحصل فيه على تصادم.



كما نرى ، تقوم دالة هاش في Python بعملها بطريقة جيدة عندما تكون المفاتيح متسلسلة ، وهو أمر جيد ، حيث يجب عليك في كثير من الأحيان التعامل مع هذه البيانات. ومع ذلك ، بمجرد إضافة المفتاح 'z' ، يحدث التصادم لأنه لا يتوافق مع المفاتيح السابقة.

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

عنونة مفتوحة

فتح عنونة هو أسلوب دقة التصادم الذي يستخدم التحقيق. في حالة 'z' ، يتم استخدام فهرس الخلية 3 بالفعل في الصفيف ، لذلك نحن بحاجة للبحث عن فهرس آخر لم يتم استخدامه بعد. تستغرق عملية إضافة زوج مفتاح / قيمة في المتوسط ​​O (1) ، وكذلك عملية البحث.

للبحث عن الخلايا الحرة ، يتم استخدام تسلسل تحقيق تربيعي. يتم تنفيذه على النحو التالي:

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index; 

يزيد التكرار في (5 * j) +1 بسرعة من الاختلافات الكبيرة في البتات التي لم تؤثر على الفهرس الأصلي. يأخذ المتغير "perturb" في هذه الحالة البتات الأخرى من شفرة التجزئة.

دعونا نلقي نظرة بدافع الفضول ماذا يحدث إذا كان لدينا تسلسل عينة مع حجم الجدول 32 و ي = 3.

3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2 ...

يمكنك معرفة المزيد حول تسلسل التحقيق هذا بالرجوع إلى شفرة المصدر dictobject.c . يمكن الاطلاع على شرح مفصل لآلية التحقيق في أعلى الملف.



دعونا نلقي نظرة على شفرة مصدر بيثون مع هذا المثال.

هياكل القاموس C

يتم استخدام بنية C التالية لتخزين الإدخال في القاموس: زوج المفتاح / القيمة. يتم تخزين التجزئة والمفتاح والقيمة. PyObject هي الفئة الأساسية للكائنات في Python.

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry; 

الهيكل التالي هو قاموس. ma_fill هو إجمالي عدد الخلايا المستخدمة وغير النشطة. تعتبر الخلية غير نشطة عند حذف زوج مفاتيح. ma_used هو عدد الخلايا (النشطة) المستخدمة. تساوي ma_mask حجم المصفوفة -1 وتستخدم لحساب فهرس الخلية. ma_table عبارة عن صفيف ، و ma_smalltable هو الصفيف الأصلي من الحجم 8.

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; }; 

تهيئة المفردات

عندما تقوم فقط بإنشاء قاموس ، PyDict_New() وظيفة PyDict_New() . لقد حذفت بعض الأسطر وقمت بتحويل رمز C إلى رمز زائف للتركيز على المفاهيم الأساسية.

وظيفة PyDict_New() :

• إرجاع كائن القاموس ؛
• يخصص كائن القاموس الجديد ؛
• مسح جدول القاموس ؛
• يضبط عدد خلايا القاموس المستخدمة والخلايا غير المستخدمة ( ma_fill ) على 0 ؛
• يضبط عدد الخلايا النشطة ( ma_used ) على 0 ؛
• يضبط قناع القاموس ( ma_value ) على قيمة مساوية لحجم القاموس - 1 = 7 ؛
• تعيين وظيفة البحث عن القاموس lookdict_string ؛
• إرجاع كائن القاموس المخصص.

إضافة عنصر

عند إضافة زوج مفتاح / قيمة جديد ، PyDict_SetItem() استدعاء PyDict_SetItem() . تقبل هذه الوظيفة مؤشر لكائن القاموس وزوج مفتاح / قيمة كمدخل. إنه يتحقق مما إذا كان المفتاح عبارة عن سلسلة ويقوم بتقييم التجزئة أو إعادة استخدام ذاكرة التخزين المؤقت في حالة وجودها. يتم استدعاء insertdict() لإضافة زوج مفتاح / قيمة جديد ويتغير حجم القاموس إذا كان عدد الخلايا المستخدمة وغير المستخدمة أكثر من 2/3 من حجم الصفيف.

لماذا بالضبط 2/3؟ هذا ضروري لضمان أن تسلسل التحقيق يمكن العثور على الخلايا الحرة بسرعة كافية. في وقت لاحق سوف ننظر في وظيفة لتغيير الحجم.

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table 

يستخدم lookdict_string() دالة البحث lookdict_string() للعثور على خلية خالية. يتم استخدام نفس الوظيفة للبحث عن مفتاح.

lookdict_string() يحسب فهرس الخلية باستخدام قيم التجزئة والقناع. إذا لم تتمكن من العثور على المفتاح حسب قيمة مؤشر الخلية = تجزئة وقناع (slot index = hash & mask) ، فستبدأ في البحث باستخدام الدورة الموضحة أعلاه حتى تعثر على خلية حرة. في أول محاولة للتحقيق ، إذا كان المفتاح null ، فسوف تُرجع خلية غير مستخدمة إذا تم العثور عليها أثناء البحث الأول. هذا يضمن الأولوية لإعادة استخدام الخلايا المحذوفة مسبقًا.
نريد إضافة أزواج المفتاح / القيمة التالية: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} . إليك ما سيحدث:

يتم تخصيص بنية القاموس بحجم جدول 8.

• PyDict_SetItem: key = 'a' ، القيمة = 1
  
  • تجزئة = تجزئة ('a') = 12416037344
  • insertdict
    
    • lookdict_string
      
      • مؤشر الفتحة = التجزئة والقناع = 12416037344 و 7 = 0
      • لا يتم استخدام الفتحة 0 ، وإرجاع هذه الخلية
    • تهيئة الإدخال في الفهرس 0 مع المفتاح والقيمة والتجزئة
    • ma_used = 1 ، ma_fill = 1
• PyDict_SetItem: key = 'b' ، القيمة = 2
  
  • التجزئة = التجزئة ('b') = 12544037731
  • insertdict
    
    • lookdict_string
      
      • مؤشر الفتحة = التجزئة والقناع = 12544037731 و 7 = 3
      • لا يتم استخدام فتحة 3 ، وإرجاع هذه الخلية
    • تهيئة الإدخال في الفهرس 3 مع المفتاح والقيمة والتجزئة
    • ma_used = 2 ، ma_fill = 2
      
• PyDict_SetItem: key = 'z' ، القيمة = 26
  
  • التجزئة = التجزئة ('z') = 15616046971
  • insertdict
    
    • lookdict_string
      
      • مؤشر الفتحة = التجزئة والقناع = 15616046971 و 7 = 3
      • يتم استخدام فتحة 3 ، حاول خلية أخرى: 5 مجاني
        
      
      تهيئة الإدخال في الفهرس 5 مع المفتاح والقيمة والتجزئة
      ma_used = 3 ، ma_fill = 3
      
• PyDict_SetItem: key = 'y' ، القيمة = 25
  
  • التجزئة = التجزئة ('y') = 15488046584
  • insertdict
    
    • lookdict_string
      
      • مؤشر الفتحة = التجزئة والقناع = 15488046584 & 7 = 0
      • يتم استخدام فتحة 0 ، حاول خلية أخرى: 1 مجاني
    • تهيئة الإدخال في الفهرس 1 باستخدام المفتاح والقيمة والتجزئة
    • ma_used = 4 ، ma_fill = 4

PyDict_SetItem: key = 'c' ، القيمة = 3

• التجزئة = التجزئة ('c') = 12672038114
• insertdict
  
  • lookdict_string
    
    • مؤشر الفتحة = التجزئة والقناع = 12672038114 و 7 = 2
    • لا يتم استخدام فتحة 2 ، وإرجاع هذه الخلية
  • تهيئة الإدخال في الفهرس 2 مع المفتاح والقيمة والتجزئة
  • ma_used = 5 ، ma_fill = 5

PyDict_SetItem: key = 'x' ، القيمة = 24

• تجزئة = تجزئة ('x') = 15360046201
• insertdict
  
  • lookdict_string
    
    • مؤشر الفتحة = التجزئة والقناع = 15360046201 & 7 = 1
    • يتم استخدام فتحة 1 ، حاول خلية أخرى: 7 مجاني
  • تهيئة الإدخال في الفهرس 7 مع المفتاح والقيمة والتجزئة
  • ma_used = 6 ، ma_fill = 6

إليك ما نحصل عليه:



الآن يتم استخدام 6 من أصل 8 خلايا ، ويشغل أكثر من 2/3 من سعة الصفيف. يتم استدعاء dictresize() لتخصيص صفيف أكبر. تقوم هذه الوظيفة أيضًا بنسخ السجلات من الجدول القديم إلى الجدول الجديد.

يتم استدعاء dictresize () مع minused = 24 في حالتنا ، حيث 4 * ma_used . ma_used استخدام 2 * ma_used عندما يكون عدد الخلايا المستخدمة كبيرًا جدًا (أكثر من 50000). لماذا هو 4 مرات أكثر الخلايا؟ هذا يقلل من عدد الخطوات لتنفيذ تغيير الحجم ويزيد من sparseness.

يجب أن يكون الحجم الجديد للجدول أكبر من 24 ، ويتم حسابه عن طريق نقل الحجم الحالي بمقدار 1 بت إلى اليسار حتى يصبح حجم الجدول أكثر من 24. ونتيجة لذلك ، سيكون 32 ، على سبيل المثال ، 8 -> 16 -> 32.

إليك ما يحدث لطاولتنا أثناء تغيير الحجم: يتم تمييز جدول جديد من الحجم 32. يتم إدراج إدخالات الجدول القديمة في الجدول الجديد باستخدام قيمة القناع الجديدة البالغة 31. والنتيجة هي ما يلي:



حذف العناصر

يتم استدعاء PyDict_DelItem() لحذف السجلات. يتم حساب التجزئة لمفتاح السجل ، ثم يتم استدعاء وظيفة البحث لإرجاع السجل. الآن الخلية فارغة.

نريد إزالة المفتاح c من قاموسنا. نتيجة لذلك ، حصلنا على المجموعة التالية:



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

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