סטים בשפת פייתון

set סט הוא אוסף לא מסודר של אלמנטים ייחודיים. יש נטייה להזניח את הלימוד של הנושא כשרק מתחילים ללמוד פייתון אבל השימוש בסטים חיוני לכל מי שרוצה לקדם את ידיעתו והבנתו בתחום תכנות ה-Python.

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

ליצירת set נשתמש ברשימה מופרדת בפסיקים של אלמנטים בתוך סוגריים מסולסלים "{}". לדוגמה:

my_set = {1, 2, 3, 4, 5}

לא חייבים להגדיר סט באמצעות סוגריים מסולסלים. אפשר ליצור set באמצעות קונסטרוקטור:

empty_set = set()

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

איך ליצור סט מרשימה?

אפשר ליצור סט מרשימה על ידי שימוש בקונסטרקטור set() של פייתון. לדוגמה:

my_list = [1, 2, 3, 3, 4, 4, 5]
my_set = set(my_list)
print(my_set)

התוצאה:

{1, 2, 3, 4, 5}

• בדוגמה, יצרנו רשימה "my_list" המכילה גם כמה אלמנטים המופיעים יותר מפעם אחת ברשימה. אחר כך השתמשנו במתודה set() של פייתון כדי להמיר את הרשימה לסט ולהציב למשתנה "my_set". הסט שנוצר בתהליך מכיל אלמנטים ייחודיים בלבד.

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

אם אנחנו רוצים רשימה של ערכים ייחודיים, ולא חשוב לנו לשמור על הסדר, אז המרה של רשימה ל-set ואז חזרה לרשימה יכולה לעשות את העבודה במינימום של משאבי מחשוב. נשתמש בקונסטרוקטור list כדי להפוך סט לרשימה:

list(my_set)

סטים יכולים לערב סוגי נתונים שונים

סטים יכולים להכיל אלמנטים מסוגי נתונים שונים כל עוד הם אינם mutable. לדוגמה:

my_set = {42, 3.14, "hello", True, ('Moshe', 27, 'Israel', 'Python')}
print(my_set)

התוצאה:

{True, 3.14, 'hello', 42, ('Moshe', 27, 'Israel', 'Python')}

• בדוגמה, אנחנו יכולים לראות עירוב של סוגי נתונים שאינם mutable כולל: מספרים, בוליאנים, מחרוזות, טאפלים. מצד שני, אי אפשר להכניס לסט סוגי נתונים שהם mutable דוגמת: list, dictionary או set.
• אפשר לראות בתוצאה שהסדר לא נשמר.

מה האורך של סט?

אפשר לקבוע את אורכו של set (=מה מספר האלמנטים) על ידי שימוש במתודה len(). לדוגמה:

my_set = {1, 2, 3, 4, 5}
print(len(my_set))

התוצאה:

5

הפונקציה len() עובדת על סטים כפי שהיא עובדת על lists וטאפלים.

איך להגיע לכל אחד מהפריטים בסט?

אנחנו לא יכולים להשתמש באינדקס כדי לגשת לפריטים מהם מורכב הסט בגלל ש-set הוא מבנה נתונים בלתי מסודר בהגדרה.

ננסה לגשת לפריט הראשון כמו שאנחנו עושים במקרה של רשימה:

my_set = {1, 2, 3, 4, 5}
my_set[0]

התוצאה היא שגיאה כי לא ניתן לגשת לפריטים של סט על סמך אינדקס:

TypeError: 'set' object is not subscriptable

אנחנו כן יכולים להגיע לכל אחד מהפריטים בסט באמצעות לולאה:

my_set = {1, 2, 3, 4, 5}
for x in my_set:
    print(x)

התוצאה:

1
2
3
4
5

איך לבדוק אם הפריט נמצא בסט?

כדי לבדוק האם פריט נמצא בסט נשתמש במילת המפתח in. לדוגמה:

my_set = {1, 2, 3, 4, 5}

if 3 in my_set:
    print("3 is in the set")

התוצאה:

3 is in the set

גם ברשימות אנחנו משתמשים ב-in כדי לבחון האם פריט חבר ברשימה אבל החיפוש יעיל משמעותית יותר במונחי big-O כאשר משתמשים ב-set לעומת השימוש ב-list. חיפוש ב-set ייקח תמיד אותו זמן לא משנה היכן האלמנט נמצא. חיפוש ב-list תלוי באורך הרשימה. ככל שהרשימה ארוכה יותר מתארך זמן החיפוש, והקשר הוא לינארי.

איך להוסיף אלמנטים לסט?

נשתמש במתודה add() כדי להוסיף פריט אחד בכל פעם לסט:

my_set = {1, 2, 3, 4, 5}

my_set.add(3.14)

print(my_set)

התוצאה:

{1, 2, 3, 4, 5, 3.14}

ניתן להוסיף יותר מפריט אחד בכל פעם לסט. באמצעות המתודה update() אנחנו יכולים להוסיף רשימה של פריטים לסט:

my_set = {1, 2, 3, 4, 5}

my_set.update([5, 3.14, 'hello'])

print(my_set)

התוצאה:

{1, 2, 3, 4, 5, 3.14, 'hello'}

כיצד להסיר פריטים מסט?

נשתמש במתודה remove() להסרת אלמנטים מהסט:

my_set = {1, 2, 3, 4, 5}

my_set.remove(3)

print(my_set)

התוצאה:

{1, 2, 4, 5}

ננסה להשתמש ב-remove להסרת אלמנט שלא קיים בסט:

my_set = {1, 2, 3, 4, 5}

my_set.remove(8)

התוצאה היא שגיאה כי האלמנט לא קיים בסט:

KeyError: 8

צריך להיות מודע לכך שהמתודה remove גורמת לשגיאה אם מנסים להסיר אלמנט שלא קיים בסט.

המתודה discard() מאפשרת להסיר אלמנט כמוremove()  אבל אם האלמנט לא קיים בסט היא לא גורמת לשגיאה:

my_set = {1, 2, 3, 4, 5}

my_set.discard(3)

my_set.discard(8)

print(my_set)

התוצאה:

{1, 2, 4, 5}

המתודה pop() מסירה אלמנט אקראי מסט נתונים, ומחזירה אותו:

my_set.pop()

איך למצוא את המשותף בין סטים?

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

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
set3 = {4, 5, 6, 7}

# using intersection() method
intersection = set1.intersection(set2, set3)
print(intersection)

התוצאה:

{4}

אפשר להחליף את המתודה intersection עם האופרטור & ולקבל את המשותף בין 2 קבוצות או יותר.

לדוגמה:

# using & operator
intersection = set1 & set2 & set3
print(intersection)

התוצאה:

{4}

איך לאחד סטים?

איחוד union הוא פעולה על סט אחד או יותר שלוקחת את האלמנטים הייחודיים מכל הסטים ומאחדת אותם.

לדוגמה, נשתמש במתודה union כדי לאחד 3 סטים:

set1 = {1, 2, 3}
set2 = {3, 4, 5}
set3 = {5, 6, 7}

union_set = set1.union(set2, set3)
print(union_set)

התוצאה:

{1, 2, 3, 4, 5, 6, 7}

במקום להשתמש במתודה union אנחנו יכולים להשתמש באופרטור פייפ | ולקבל את אותה התוצאה:

union_set = set1 | set2 | set3

איך למצוא את ההבדל בין שני סטים או יותר?

כדי למצוא את ההבדל בין שני סטים או יותר בפייתון, אנחנו משתמשים במתודה difference()

נמצא אילו פריטים נמצאים בסט הראשון אך לא בשני על ידי הפעלת המתודה difference על הסט הראשון והעברת הסט השני כפרמטר:

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

# using difference() method
diff1 = set1.difference(set2)

print(diff1)

התוצאה:

{1, 2}

• התוצאה היא סט הפריטים הקיימים בסט הראשון ולא בשני.

אם נעשה הפוך סט 2 פחות סט 1:

diff2 = set2.difference(set1)

print(diff2)

נקבל תוצאה:

{5, 6}

• כי הפריטים 5 ו-6 קיימים בסט השני ולא בראשון.

תחביר חלופי משתמש בסימן המינוס "-" במקום במתודה difference. לדוגמה:

# using - operator
diff1 = set1 - set2
diff2 = set2 - set1

הרבה פעמים נרצה לקבל את סט הפריטים הייחודיים לסט הראשון או/וגם את אילו הקיימים רק בסט השני (XOR). בשביל זה אנחנו יכולים להשתמש ב-union() על שני הסטים שקיבלנו מהפעלת המתודה difference() על שני הסטים:

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

diff1 = set1 - set2
diff2 = set2 - set1

uniques = diff1 | diff2
print(uniques)

התוצאה:

{1, 2, 5, 6}

• uniques היא סט המחזיק את הייחודיים מהסט הראשון (1 ו-2) עם הייחודיים מסט 2 (5 ו-6).

האם רשימה מכילה ערכים כפולים

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

שם הפונקציה יהיה contains_duplicate(nums=[]). היא תקבל רשימה של מספרים שלמים nums, ותחזיר ערך בוליאני True/False.

לדוגמה:

Input: nums = [1, 6, 1, 4, 1]
Output: True

Input: nums = [0, 1, 2]
Output: False

נסה לפתור בעצמך.

גישה אחת היא לעבור באמצעות לולאה בתוך לולאה. הבעיה עם הגישה הזו שהיא מצריכה זמן ריצה O(n^2).

גישה שנייה היא לעבור על כל המספרים ברשימה בלולאה שרצה פעם אחת על הרשימה ומאחסנת כל איבר במערך שנקרא לו seen = [] אבל קודם בודקת האם המספר הנוכחי קיים כבר במערך. אם היא נתקלת במספר שכבר קיים במערך היא מחזירה True. אחרת, אם היא סיימה לרוץ על כל הרשימה ולא מצאה כפילות היא תחזיר False. הבעיה היא שבדיקת חברות membership checks במערכי פייתון באמצעות האופרטור in או המתודה .index() מתאפיינות בסיבוכיות זמן שהיא במקרה הגרוע לינארית מה שאומר שצריך להכפיל את סיבוכיות הזמן הלינארית של הריצה על הרשימה O(n) בסיבוכיות הזמן הלינארית של מבחני החברות שגם הוא O(n) מה שנותן במקרה הגרוע סיבוכיות זמן של O(n^2).

ניתן לייעל את הפתרון אם משתמשים במקום במערך בסט של פייתון seen = set(). סטים יעילים יותר ממערכים עבור הבעיה שאנו פותרים כיוון שהם מאפשרים ביצוע פעולות: הכנסה, חיפוש ומחיקה בזמן ממוצע קבוע O(1). בהתאם, נשתמש בלולאה שרצה פעם אחת על הרשימה ומאחסנת כל אחד מאברי הרשימה בסט אבל קודם בודקת האם האיבר הנוכחי קיים כבר בסט אם היא נתקלת במספר שכבר קיים בסט היא מחזירה True. להבדיל, אם היא סיימה לרוץ על כל הרשימה ולא מצאה כפילות היא תחזיר False. כיוון שהלולאה רצה פעם אחת וזמן האחסון והחיפוש של פריטים מהסט הוא בממוצע O(1) זמן הריצה הכולל של הפונקציה הוא בממוצע לינארי O(n).

להלן פתרון הבעיה המבוסס על סט של פייתון:

def contains_duplicate(nums):
    """
    This function checks if any value appears at least twice in the array.

    Parameters:
    nums (list): The array to check for duplicates.

    Returns:
    True if any value appears at least twice in the array, False otherwise.
    """
    
    # Create a set to store the seen numbers.
    seen_numbers = set()
    
    # Loop over the numbers in the array.
    for num in nums:
        # Check if the number is already in the set.
        if num in seen_numbers:
            # If the number is already in the set, return True.
            return True
        
        # Add the number to the set.
        seen_numbers.add(num)
    
    # If we reach the end of the array without returning True, 
    # then no duplicates were found.
    return False


# Test cases
nums = [1, 6, 1, 4, 1]
res = contains_duplicate(nums)
assert res == True

nums = [0, 1, 2]
res = contains_duplicate(nums)
assert res == False

nums = [0, 1, 1, 1, 3, 3, 3, 5, 8]
res = contains_duplicate(nums)
assert res == True

nums = []
res = contains_duplicate(nums)
assert res == False

סטים הם יעילים יותר לאחסון ושליפת נתונים עבור בעיות כדוגמת זו שאנו פותרים בגלל שסטים משתמשים במבנה נתונים מבוסס hash map המאפשר פעולות בזמן קבוע, בזמן ממוצע קבוע, O(1). כאשר אתה בודק אם רכיב קיים בסט באמצעות האופרטור in או מוסיף פריט באמצעות המתודה add(), טבלת ה-hash יכולה למפות ישירות את ה-hash של האלמנט למיקומו. המשמעות היא שהזמן שלוקח לבדיקת חברות (בממוצע) אינו תלוי בגודל הסט.

מדריכים נוספים בסדרה ללימוד פייתון

מילונים בשפת פייתון

טאפלים של פייתון - רשימות שלא ניתן לשנות

רשימות של פייתון

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים