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

[محمد]

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

# مقدمة: جدول الهاش (hash table)

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

جداول الهاش هي هيكل بيانات توفر حلولا لبعض المسائل التي لا تحلها المتتاليات (السلاسل النصية - القوائم - الصفوف...) واهمها وقت المعالج، حيث يرتفع وقت معالجة البيانات خطيا مع ارتفاع عدد عناصر المتتالية فالمتتاليات تم تحسين أدائها لتعمل مع المؤشرات غير أن هذا يؤدي الى وقت اطول كلما كان عدد المؤشرات أكبر لكنها غير محسنة لاختبار انتماء عنصر الى المتتالية.

- سنبحث ألف مرة عن عنصر 'x' غير موجود (وهي اسوأ الاحتمالات) في مجال(10000) وسنحسب وقت العملية:

كود :

from timeit import Timer                # لحساب وقت تنفيذ عملية
e = "'x' in range(10000)"               # التعبير الذي سنختبره
Timer(e).timeit(number=1000)            # 0.28355575100067654

- نكرر البحث ألف مرة في مجال(100000) أي 10000*10

كود :

e = "'x' in range(100000)"              # التعبير الذي سنختبره
Timer(e).timeit(number=1000)            # 2.740653011998802

- نكرر البحث ألف مرة في مجال(1000000) أي 100000*10

كود :

e = "'x' in range(1000000)"             # التعبير الذي سنختبره
Timer(e).timeit(number=1000)            # 27.296190940000088

نلاحظ ان وقت العملية يتضاعف 10 مرات تقريبا عند كل مضاعفة. ويمكننا أن نستنتج كما ذكرنا أعلاه أن الوقت يرتفع خطيا مع عدد عمليات المعالجة.

اذا كنت تستخدم مفسر ipython يمكنك اجراء نفس التجربة كما يلي:

كود :

%timeit 'x' in range(10000)             # 269 µs
%timeit 'x' in range(100000)            # 2.7 ms
%timeit 'x' in range(1000000)           # 29.2 ms

من المعتاد دائما اجراء اختبار انتماء عنصر الى مجموعة، بحيث نرغب في الحصول على نتائج في وقت لا يتأثر بعدد العناصر في المجموعة محل البحث.

محدودية ثانية في المتتاليات: لنفترض أن لدينا قائمة اشخاص وقائمة ثانية بأعمارهم

كود :

persons = ['Amr', 'Zaid']               # قائمة الاشخاص
ages = [18, 35]                         # قائمة الأعمار
ages[0]                                 # هذا ممكن لكنه لا يربط الشخص بعمره مباشرة
ages['Amr'] = 21                        # هنا يطلق بيثون خطأ

يسمح لنا هيكل البيانات hash table بتجاوز هاتين المحدوديتين في المتتاليات: الحصول على وقت ثابت مهما كان عدد العناصر في المتتالية واستخدام انواع اخرى غير الاعداد كمفاتيح فريدة. سنبدأ بدراسة كيفية عمل الـhash table

بغاية التبسيط الشديد يتركب جدول هاش من جدول ومن دالة تجزئة (هاش): سنعتبر أن لدينا جدولا يتكون من 6 عناصر فقط، وعندما نمرر للدالة مفتاحا تعيد لنا قيمة بين 1 و 6: رياضيا نقول

كود :

f(x) ∈ [1,6]

فهدف الدالة إذا هو انشاء علاقة ترابط بين كائن ما وخانة في الجدول. فلو فرضنا أننا نريد انشاء علاقة ترابط بين Amr والعدد 21 كما في المثال أعلاه، سنمرر ما نسميه مفتاحا فريدا من نوعه (Amr) كوسيط لدالة الهاش التي ستقوم بعملها الداخلي على هذا المفتاح(الفريد من نوعه) Amr وتعيد لنا خانة في الجدول، لنقل أنها الخانة رقم 2 حيث نكتب الزوج (Amr,21)، ثم نواصل كما يلي:

كود :

ages['Amr'] = 21            # key = Amr ; value = 21  => (َAmr, 21)  => case 2
ages['Zaid'] = 35           # key = Zaid ; value = 35 => (َZaid, 35) => case 4
ages['Rima'] = 30           # key = Rima ; value = 30 => (َRima, 30) => case 1
ages['Bob'] = 25            # key = Bob ; value = 25  => (َBob, 25)  => case 6
ages['Eve'] = 17            # key = Eve ; value = 17  => (َEve, 17)  => case 3
ages['Jo'] = 33             # key = Jo ; value = 33   => (َJo, 33)   => case 5

والآن اذا رغبنا في استرجاع القيمة المرتبطة بـ Amr مثلا، ستقوم الدالة بنفس العملية على المفتاح Amr لكي تجد لنا نفس الخانة(افترضنا أنها الخانة رقم 2) وتستخرج لنا منها عمر Amr أي القيمة الموافقة للمفتاح

كود :

print(ages['Amr'])           # 21

نلاحظ أننا انطلقنا من جدول يتكون من 6 عناصر: المقصود من ذلك هو أن الجدول له حجم محدود مهما كبر، وقد تكون البيانات اكثر من الخانات، فمثلا اذا رغبنا في اضافة زوج (مفتاح، قيمة) كما يلي:

كود :

ages['Sam'] = 20             # key = Sam ; value = 20   => (َSam, 20)   => case ?

ماذا ستفعل دالة الهاش؟ سترد لنا خانة غير فارغة أي موجود فيها زوج أو ازواج من المفاتيح والقيم. لنقل مثلا أنها سترد لنا الخانة رقم 2 مرة أخرى. أي أننا سنحفظ الزوج (َSam, 20) في الخانة 2 مع الزوج (َAmr, 21)، وهذا ممكن: عندما تبحث دالة الهاش عن القيمة المرتبطة بالمفتاح Sam او المفتاح Amr ستجد أنهما في الخانة 2 وبما أن كل مفتاح هو فريد من نوعه فهي ستواصل البحث داخل الخانة نفسها ليس بواسطة الهاش بل بواسطة المفتاح لتجد القيمة الموافقة له.

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

نلاحظ أيضا أن فعالية جدول الهاش مرتبطة بحجمه من ناحية (جدول صغير سيكون فيه الكثير من التصادم (collision) عندما يطابق مفتاحين او اكثر نفس الخانة) ، وبفعالية دالة الهاش في حسن توزيع ازواج المفاتيح والقيم داخل الجدول. في بيثون تم بناء جدول الهاش بطريقة شديدة الفعالية، بحيث ليس علينا ان ننشغل بكيفية عمل دالة الهاش الداخلي ولا بحجم الجدول؛ سيقوم بيثون تلقائيا بالعناية بهذه الناحية بحيث نحصل على الفعالية التي نطمح اليها. يمكننا اعتبار أن جدول الهاش سيتيح لنا وقت وصول ووقت ادخال ووقت حذف ووقت بحث مستقل عن عدد العناصر، كما سيتيح لنا تأشير قيم ليس فقط بمؤشرات رقمية بل بأنواع اخرى من المفاتيح على شرط ألا تكون قابلة للتعديل كالسلاسل النصية مثلا (على ان تكون فريدة).

في بيثون لدينا بنيتان من جداول الهاش: القواميس (dict) والمجاميع (set)



# القواميس dict

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

كل كائن غير قابل للتعديل يمكن استخدامه كمفتاح في قاموس: الاعداد والسلاسل النصية والصفوف (بشرط عدم احتوائها على عناصر قابلة للتعديل) يمكن استخدامها كمفاتيح، في المقابل جميع الكائنات القابلة للتعديل كالقوائم والقواميس نفسها لا يمكن أن تكون مفاتيحا. لو حللنا هذا مع ما سبق من حديثنا عن دالة الهاش، فقد قلنا ان هذه الدالة ستقوم بعملياتها على مفتاح فريد من نوعه، فلو تغير هذا المفتاح اثناء تشغيل البرنامج فدالة الهاش ستقوم بحسابات ستكون مختلفة في كل مرة وبالتالي يصبح جدول الهاش غير قابل للاستخدام. لهذا قلنا أن الكائنات غير القابلة للتعديل هي فقط ما يمكن استخدامه كمفاتيح.

## نمر الى كيفية انشاء القواميس
لانشاء قاموس نستخدم القوسين المعقفين {}:

كود :

ages = {}                               # قاموس فارغ
type(ages)                              # dict
ages = {'Amr':21, 'Zaid':35, 'Rima':30} # {key:value, ....}

فالقواميس اذا هي مجموعة من الازواج {مفتاح:قيمة} يُفصل بينها بالنقطتين : في المثال الأخير لدينا قاموس يحتوي على ثلاثة مفاتيح Amr وZaid و Rima وثلاثة قيم 21 و 35 و 30. يمكننا الوصول الى مختلف عناصر القاموس:

كود :

ages['Amr']                             # 35

## طريقة ثانية لانشاء القواميس:

كود :

a = [('Bob', 25), ('Eve', 17), ('Jo', 33)]  # قائمة صفوف
ages = dict(a)          # انشاء قاموس انطلاقا من قائمة صفوف
ages                    # {'Eve': 17, 'Jo': 33, 'Bob': 25}
ages['Bob']             # 25
ages['Bob'] = 26        # القاموس قابل للتعديل
ages                    # {'Eve': 17, 'Jo': 33, 'Bob': 26}

## ملاحظة هامة يتوجب التنبيه اليها: القواميس ليست مرتبة، العناصر يمكن أن تظهر بترتيب مختلف لا يمكن التحكم فيه، فوجب التنبيه.

## التحرير والحذف
راينا أنه يمكن تعديل زوج (مفتاح،قيمة)؛ يمكننا ايضا حذف ازواج من المفاتيح والقيم:

كود :

del ages['Bob']         # حذف
ages                    # {'Eve': 17, 'Jo': 33}

## عدد ازواج المفاتيح والقيم (طول القاموس)

كود :

len(ages)               # 2

## اختبار انتماء مفتاح الى القاموس:

كود :

'Eve' in ages           # True
'Bob' in ages           # False

## الوصول الى مفاتيح القاموس او القيم او كلاهما
الوظائف التالية ترد كل منها كائنا يمكن تصفحه داخل حلقة تكرار او اختبار انتماء عنصر اليه عبر in. كما أن من خصائص الكائنات أنه يقع تحديثها تلقائيا عند كل تغيير في القاموس (قارنها بالـview في قواعد البيانات)

كود :

ages.keys()             # dict_keys(['Eve', 'Jo'])
ages.values()           # dict_values([17, 33])
ages.items()            # dict_items([('Eve', 17), ('Jo', 33)])
k = ages.keys()         # مجموعة المفاتيح
k                       # dict_keys(['Eve', 'Jo'])
ages['Ana'] = 27        # اضافة زوج مفتاح:قيمة
k                       # dict_keys(['Eve', 'Jo', 'Ana'])
'Ana' in k              # True
'Bill' in k             # False

## استخراج عناصر قاموس

كود :

for k, v in ages.items():
   print(k, v)

## مكرر القاموس فهو مكرر للمفاتيح فقط، كما في المثال التالي:

كود :

for e in ages:          # حلقة تكرار على القاموس مباشرة
   print(e)            # تطبع لنا المفاتيح فقط

## طريقة اضافية لانشاء قاموس ولاحظ عدم استخدام '' للمفاتيح، ذلك أنها هنا وسائط تم تمريرها مع قيمها للدالة dict:

كود :

ages = dict(Marc=32, Alice=22, Sam=19)
ages                    # {'Alice': 22, 'Sam': 19, 'Marc': 32}

## الوظيفة dict.get

قلنا أعلاه أن الوصول الى قيمة يتم بالطريقة التالية:

كود :

ages['Sam']

فماذا لو لم يكن في القاموس مفتاح Sam؟ سيطلق بيثون خطأ، ولتجنب ذلك يمكن استخدام الوظيفة get التي تقبل قيمة افتراضية ترجعها اذا لم تجد المفتاح:

كود :

ages.get('Sam', -1)     # 19
ages.get'Unknown', -1)  # -1

## التعديل والاضافة مرة أخرى
رأينا ايضا أننا نقوم بتعديل قيمة مفتاح او اضافة زوج جديد بنفس الطريقة:

كود :

ages['sam'] = 20        # هذا المفتاح موجود سيتم تحرير قيمته
ages['Abdou'] = 38      # هذا المفتاح غير موجود، سيم اضافة زوج مفتاح:قيمة

## الوظيفة dict.update
يمكن اضافة عدة ازواج من قاموس آخر مثلا عبر الوظيفة update

كود :

ages.update({Jean:28, 'Eric':70})

## خاصية Dict comprehension

راينا سابقا list comprehension

كود :

myList = [(x, x**2) for x in range(10)]
myList                  # list of tuples

يمكن بنفس الطريقة بناء قاموس باستخدام القوسين المعقفين:

كود :

myDict = {x:x**2 for x in range(10)}
myDict

لاحظ أن بناء قاموس بهذه الطريقة لا يستغرق وقتا:

كود :

big_dict = {k : k**2 for k in range(1000000)}

from timeit import Timer
s = '{k : k**2 for k in range(1000000)}'
Timer(s).timeit(number=1)

أو، إذا كنت تستخدم مفسر ipython

كود :

%timeit {k : k**2 for k in range(1000000)}

لكن سيستغرق الامر وقتا أطول من ذلك بكثير اذا اردت تحويل القاموس الى قائمة أو حتى تحويل المفاتيح فقط الى قائمة:

كود :

%timeit list(big_dict)
big_keys = big_dict.keys()
%timeit list(big_keys)

## ما يصلح ليكون مفتاحا في قاموس

- المفتاح يجب أن يكون غير قابل للتعديل:   int - float - complex - bool - str - frozenset - tuple

لكن هذا لا يكفي خصوصا بالنسبة الى tuple حيث يجب أن تكون العناصر المكونة للصف tuple غير قابلة للتعديل هي الاخرى

كود :

d = {}
t = (1, 2)              # هذا الصف يصلح كمفتاح
d[t] = "good key"
tt = (3, [4, 5])        # هذا الصف لا يصلح كمفتاح

في هذا المثال الاخير، احد مكونات الصف هو قائمة، ورغم أن الصف لا يقبل التعديل لكن أحد عناصرها يمكن تعديله:

كود :

tt[1].append(6)
print(tt)

لو حاولت اضافة tt كمفتاح للقاموس سيطلق بيثون خطأ:

كود :

d[tt] = "bad key"

للمزيد من المعلومات عن القواميس:

https://docs.python.org/3/library/stdtyp...types-dict