א.12 — קבוצות — set

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

קבוצה (set) שומרת אוסף של איברים ייחודיים: אותו ערך אינו נשמר בה פעמיים. למשל, אם נשמור בקבוצה את המקומות שבהם שחקן כבר ביקר, ביקור חוזר באותו מקום לא יוסיף איבר נוסף.

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

פתיחת המחברת ב־Colab · השיעור וההרצאה באתר הקורס

מחברות האוניברסיטה הפתוחה — 11-מבני נתונים מתקדמים

יצירה, הוספה והסרה

קבוצה נכתבת בסוגריים מסולסלים {}, כמו מילון, אבל בלי נקודתיים: רק ערכים, מופרדים בפסיקים. נייצג את החדרים שבהם ביקר השחקן באמצעות מספריהם. add מוסיפה מספר לקבוצה, ו־remove מסירה אותו. הוספת מספר שכבר נמצא בקבוצה אינה משנה אותה; in בודקת אם המספר קיים.

האיברים צריכים להתאים לאותם כללים של מפתחות במילון (ניתנים לגיבוב, כלומר ערכים שאינם משתנים): למשל מספר, מחרוזת או tuple של ערכים כאלה. רשימה אינה מתאימה כאיבר בקבוצה.

visited = {1, 2, 2, 3}
visited.add(4)
visited.add(2)
visited.remove(1)
print(len(visited))
print(2 in visited)
empty = set()

פלט

3
True

הקבוצה נוצרה מהערכים {1, 2, 2, 3}, אך הכפילות של 2 נשמרה פעם אחת בלבד. אחרי הוספת 4, הוספה חוזרת של 2 (שאינה משנה דבר) והסרת 1, נשארו בקבוצה שלושה איברים: 2, 3 ו־4. קבוצה ריקה נכתבת set(); הסימון {} יוצר מילון ריק. remove דורשת שהאיבר יהיה בקבוצה. discard מסירה אותו אם הוא קיים, ללא שגיאה אם אינו קיים.

מעבר מרשימה לקבוצה

רשימת שמות יכולה להכיל אותו שם כמה פעמים. המרה ל־set שומרת כל שם פעם אחת ומתאימה לספירת שמות שונים:

names = ["Dana", "Noam", "Dana"]
unique_names = set(names)
print(len(names), len(unique_names))
print("Dana" in unique_names)

פלט

3 2
True

ברשימה שלושה איברים, אבל בקבוצה רק שניים, כי השם "Dana" נשמר פעם אחת. כך אפשר לספור בשורה אחת כמה שמות שונים יש. לא מסתמכים על סדר הסריקה של הקבוצה. אם רוצים גם סדר וגם כפילויות, שומרים את הרשימה המקורית.

איזה מבנה מתאים למשימה?

בפרקים א.8–א.12 הכרנו ארבעה מבני נתונים. בתוכנית אמיתית השאלה הראשונה היא איזה מהם לבחור, וטעות בבחירה מובילה לקוד מסורבל: למשל, בדיקת כפילויות ברשימה במקום בקבוצה, או חיפוש לפי שם ברשימה במקום במילון. בחירת מבנה הנתונים תלויה באופן שבו רוצים לשמור את המידע ולגשת אליו. הטבלה מרכזת את ההבדלים בין ארבעת המבנים שלמדנו.

ב־list וב־tuple פונים לפי אינדקס; במילון לפי מפתח; בקבוצה בודקים שייכות לפי ערך. מבני נתונים בתיעוד Python.