הפקודה in של פייתון מאפשרת לחפש אלמנט בתוך מבנה נתונים. למעשה כל מה שהיא עושה זה להפעיל את הפונקציה __contains__ של מבנה הנתונים, או בקוד זה אומר ש:

5 in [10, 20, 30, 5, 9]

בעצם מפעיל את:

[10, 20, 30, 5, 9].__contains__(5)

בגלל שפייתון היא שפה מונחית עצמים, כל מבנה נתונים יכול לממש את __contains__ בצורה שמתאימה עבורו, ולכן הזמן שייקח ל in להחזיר תשובה תלוי קודם כל בסוג מבנה הנתונים בו אתם מחפשים.

שלושת המקרים הנפוצים לחיפוש אלמנט הם חיפוש במילון, חיפוש ברשימה וחיפוש במפתחות של מילון. בואו נמדוד זמנים לכל אחד מהם ונראה מה אפשר ללמוד מזה.

1. חיפוש אלמנט במילון

הקוד הבא מייצר מילון של אלף ערכים אקראיים ומחפש בו את המפתח 5:

import random
import timeit

setup = """
import random
d = {}
for _ in range(10_000):
  d[random.randint(1, 1_000)] = random.randint(1, 1_000)
"""

print(timeit.timeit('5 in d', setup=setup))

בהפעלה אצלי על המחשב מתקבל זמן הריצה:

0.031794708

2. חיפוש ערך במפתחות של מילון

הפקודה keys של מילון מחזירה את אוסף המפתחות של אותו המילון. ב Python2 הפקודה החזירה רשימה רגילה, אבל ב Python3 פקודה זו מחזירה מבנה נתונים חדש שנקרא dict_keys. מבנה זה הוא בסך הכל Pointer למפתחות המילון ולכן יצירתו יחסית מהירה, אבל עדיין בבדיקה אנחנו יכולים לראות שזה לוקח קצת יותר זמן מאשר חיפוש ישיר במילון (כנראה בגלל שלוקח לפייתון קצת זמן לקרוא לפונקציה ולייצר את המבנה). חשוב להדגיש - אין העתקה של מפתחות המילון ולכן משך פעולה זו לא תלוי בגודל המילון.

הקוד הבא מייצר dict_keys ומחפש בו ערך. בשביל להבדיל בין הזמן שלוקח לייצר את ה dict_keys לזמן שלוקח לחפש במבנה כזה יצרתי שתי בדיקות, בראשונה יצירת ה dict_keys מתרחשת ב setup כך שאינה נספרת בזמן הבדיקה, ובשניה הבדיקה כוללת גם את יצירת ה dict_keys:

import random
import timeit

setup = """
import random
d = {}
for _ in range(10_000):
  d[random.randint(1, 1_000)] = random.randint(1, 1_000)

keys = d.keys()
"""

print(timeit.timeit('5 in d', setup=setup))
print(timeit.timeit('5 in keys', setup=setup))
print(timeit.timeit('5 in d.keys()', setup=setup))

תוצאת ההרצה אצלי על המחשב נראית כך:

0.031886886999999996
0.03299745899999999
0.10683095899999998

קל לראות ששני החיפושים הראשונים מאוד קרובים, והחיפוש השלישי שכולל גם את יצירת מבנה ה dict_keys לוקח קצת יותר זמן. זה אומר שבתוכנית אמיתית כשנרצה לחפש במילון כדאי לזכור להשתמש ב:

d = {'a': 10, 'b': 20}

if 'a' in d:
    pass

ולא בגירסא הארוכה יותר:

d = {'a': 10, 'b': 20}

if 'a' in d.keys():
    pass

למרות שגם אם כן בחרתם בגירסא השניה פער הזמנים לא יהיה יותר מדי מורגש.

3. חיפוש ערך ברשימה

מצד שני ברגע שאנחנו עוזבים את המילון ועוברים לרשימה מימוש הפונקציה __contains__ משתנה: ברשימה חיפוש אלמנט מחייב לסרוק את הרשימה אלמנט אחרי אלמנט וזה כבר תהליך שיכול לקחת זמן. התאמתי את תוכנית הבדיקה כדי שתהפוך את ה dict_keys שלנו לרשימה ואז תנסה לחפש שם את 5:

import random
import timeit

setup = """
import random
d = {}
for _ in range(10_000):
  d[random.randint(1, 1_000)] = random.randint(1, 1_000)

keys = d.keys()
keys_as_list = list(keys)
"""

print(timeit.timeit('5 in d', setup=setup))
print(timeit.timeit('5 in keys', setup=setup))
print(timeit.timeit('5 in d.keys()', setup=setup))
print(timeit.timeit('5 in keys_as_list', setup=setup))

ותוצאת זמני הריצה לא הפתיעה:

0.035458299000000006
0.03386534499999999
0.10725996600000004
5.69748644

חיפוש ברשימה לוקח משמעותית יותר זמן מחיפוש במילון, בגלל שהפונקציה __contains__ של רשימה עושה משהו שדורש הרבה יותר מאמץ מאשר הפונקציה המקבילה במילון. בעבודה עם פייתון3 אני חושב שיחסית קשה להמיר את המידע בטעות ממילון לרשימה לצורך החיפוש (בזכות התוספת של dict_keys), ועדיין שווה להכיר את ההבדלים האלה כשאתם בוחרים באיזה מבנה נתונים להשתמש ולבחור את מבנה הנתונים שיתאים בצורה הטובה ביותר לסיטואציה שלכם.