22-05-2018, 12:26 AM
القواميس في بيثون
# مقدمة: جدول الهاش (hash table)توضيح: بعد مطالعتك لهذه المقدمة واذا وجدت صعوبة في فهم جدول الهاش، فهذا لا يمنع من فهم القواميس فيما بعد.
جداول الهاش هي هيكل بيانات توفر حلولا لبعض المسائل التي لا تحلها المتتاليات (السلاسل النصية - القوائم - الصفوف...) واهمها وقت المعالج، حيث يرتفع وقت معالجة البيانات خطيا مع ارتفاع عدد عناصر المتتالية فالمتتاليات تم تحسين أدائها لتعمل مع المؤشرات غير أن هذا يؤدي الى وقت اطول كلما كان عدد المؤشرات أكبر لكنها غير محسنة لاختبار انتماء عنصر الى المتتالية.
- سنبحث ألف مرة عن عنصر 'x' غير موجود (وهي اسوأ الاحتمالات) في مجال(10000) وسنحسب وقت العملية:
كود :
from timeit import Timer # لحساب وقت تنفيذ عملية
e = "'x' in range(10000)" # التعبير الذي سنختبره
Timer(e).timeit(number=1000) # 0.28355575100067654
كود :
e = "'x' in range(100000)" # التعبير الذي سنختبره
Timer(e).timeit(number=1000) # 2.740653011998802
كود :
e = "'x' in range(1000000)" # التعبير الذي سنختبره
Timer(e).timeit(number=1000) # 27.296190940000088
اذا كنت تستخدم مفسر 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 # هنا يطلق بيثون خطأ
بغاية التبسيط الشديد يتركب جدول هاش من جدول ومن دالة تجزئة (هاش): سنعتبر أن لدينا جدولا يتكون من 6 عناصر فقط، وعندما نمرر للدالة مفتاحا تعيد لنا قيمة بين 1 و 6: رياضيا نقول
كود :
f(x) ∈ [1,6]
كود :
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
كود :
print(ages['Amr']) # 21
كود :
ages['Sam'] = 20 # key = Sam ; value = 20 => (َSam, 20) => case ?
نلاحظ أن العمليات على جدول الهاش من ادخال واستخراج وحذف وبحث غير مرتبطة بعدد العناصر ، وما يتحكم في سرعتها هو سرعة الدالة في اجراء العمليات المطلوبة: تقوم الدالة بعملياتها فنحصل على الخانة حيث نجد البيانات المطلوبة في شكل زوج (مفتاح، قيمة).
نلاحظ أيضا أن فعالية جدول الهاش مرتبطة بحجمه من ناحية (جدول صغير سيكون فيه الكثير من التصادم (collision) عندما يطابق مفتاحين او اكثر نفس الخانة) ، وبفعالية دالة الهاش في حسن توزيع ازواج المفاتيح والقيم داخل الجدول. في بيثون تم بناء جدول الهاش بطريقة شديدة الفعالية، بحيث ليس علينا ان ننشغل بكيفية عمل دالة الهاش الداخلي ولا بحجم الجدول؛ سيقوم بيثون تلقائيا بالعناية بهذه الناحية بحيث نحصل على الفعالية التي نطمح اليها. يمكننا اعتبار أن جدول الهاش سيتيح لنا وقت وصول ووقت ادخال ووقت حذف ووقت بحث مستقل عن عدد العناصر، كما سيتيح لنا تأشير قيم ليس فقط بمؤشرات رقمية بل بأنواع اخرى من المفاتيح على شرط ألا تكون قابلة للتعديل كالسلاسل النصية مثلا (على ان تكون فريدة).
في بيثون لدينا بنيتان من جداول الهاش: القواميس (dict) والمجاميع (set)
# القواميس dict
القواميس هي اذا نوع من جداول الهاش، بمعنى أن لدينا وقت وصول وتحرير وبحث الخ مستقل عن عدد العناصر في القاموس. أضف الى ذلك أن القواميس هي كائنات قابلة للتعديل (تذكر القوائم) أي أننا نستطيع تعديلها مباشرة (دون نسخ) وهذا مهم جدا من ناحية حسن ادارة ذاكرة الجهاز.
كل كائن غير قابل للتعديل يمكن استخدامه كمفتاح في قاموس: الاعداد والسلاسل النصية والصفوف (بشرط عدم احتوائها على عناصر قابلة للتعديل) يمكن استخدامها كمفاتيح، في المقابل جميع الكائنات القابلة للتعديل كالقوائم والقواميس نفسها لا يمكن أن تكون مفاتيحا. لو حللنا هذا مع ما سبق من حديثنا عن دالة الهاش، فقد قلنا ان هذه الدالة ستقوم بعملياتها على مفتاح فريد من نوعه، فلو تغير هذا المفتاح اثناء تشغيل البرنامج فدالة الهاش ستقوم بحسابات ستكون مختلفة في كل مرة وبالتالي يصبح جدول الهاش غير قابل للاستخدام. لهذا قلنا أن الكائنات غير القابلة للتعديل هي فقط ما يمكن استخدامه كمفاتيح.
## نمر الى كيفية انشاء القواميس
لانشاء قاموس نستخدم القوسين المعقفين {}:
كود :
ages = {} # قاموس فارغ
type(ages) # dict
ages = {'Amr':21, 'Zaid':35, 'Rima':30} # {key:value, ....}
كود :
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) # تطبع لنا المفاتيح فقط
كود :
ages = dict(Marc=32, Alice=22, Sam=19)
ages # {'Alice': 22, 'Sam': 19, 'Marc': 32}
قلنا أعلاه أن الوصول الى قيمة يتم بالطريقة التالية:
كود :
ages['Sam']
كود :
ages.get('Sam', -1) # 19
ages.get'Unknown', -1) # -1
رأينا ايضا أننا نقوم بتعديل قيمة مفتاح او اضافة زوج جديد بنفس الطريقة:
كود :
ages['sam'] = 20 # هذا المفتاح موجود سيتم تحرير قيمته
ages['Abdou'] = 38 # هذا المفتاح غير موجود، سيم اضافة زوج مفتاح:قيمة
يمكن اضافة عدة ازواج من قاموس آخر مثلا عبر الوظيفة update
كود :
ages.update({Jean:28, 'Eric':70})
راينا سابقا 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)
كود :
%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)
كود :
d[tt] = "bad key"
https://docs.python.org/3/library/stdtyp...types-dict