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

1. מה צריך?

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

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

דוגמת שימוש בפונקציה יכולה להיראות כך:

d = dict()
update_dict_with_subdicts(d, {"a": 4})
assert d == {"a": 4}

new_dict = {
        "b": {
            "c": {
                "d": 6
                }
            }
        }
update_dict_with_subdicts(d, new_dict)
assert d == {
        "a": 4,
        "b": {
            "c": {
                "d": 6
                }
            }
        }

new_dict = {
        "a": 3,
        "b": {
            "f": 7
            }
        }
update_dict_with_subdicts(d, new_dict)
assert d == {
        "a": 3,
        "b": {
            "c": {
                "d": 6
                },
            "f": 7
            }
        }

2. פיתרון בשפת Python

הדרך הכי קלה להחליף מימוש רקורסיבי במימוש איטרטיבי היא להוסיף מבנה נתונים של מחסנית. ב Python מבנה הנתונים collections.deque יכול לשמש בקלות בתור מחסנית אם נשתמש בפונקציות pop ו append מאחר ושתיהן עובדות על אותו הצד. הפונקציה append מוסיפה איבר לצד הימני של התור, ו pop מוציאה את האיבר הימני ביותר.

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

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

1. אם מפתח מסוים נמצא במילון השני אך לא במילון הראשון, פשוט מעתיקים אותו.

2. אם מפתח נמצא בשני המילונים, והערך שלו הוא dict בשניהם - נוסיף קריאה "רקורסיבית" למיזוג שני הערכים.

3. אם מפתח נמצא בשני המילונים, והערך שלו הוא dict רק בשני, עלינו לזרוק את הערך הישן מהראשון, להחליף אותו במילון ריק ואז לטפל כאילו אנחנו במקרה (2).

4. אם מפתח נמצא בשני המילונים אך במילון השני הערך איננו dict, אפשר פשוט להעתיק אותו, כמו במקרה (1).

הקוד עצמו לקח לי קצת פחות מ-20 שורות, ואני די בטוח שאפשר לכתוב את כל ה if-ים של האמצע בצורה יותר תמציתית אם מאחדים תנאים:

def update_dict_with_subdicts(dict1, dict2):
    q = collections.deque([(dict1, dict2)])
    while len(q) > 0:
        d1, d2 = q.pop()
        for k in d2.keys():
            if k not in d1:
                d1[k] = d2[k]
            elif type(d1[k]) == dict and type(d2[k]) == dict:
                q.append((d1[k], d2[k]))
            elif type(d1[k]) != dict and type(d2[k]) == dict:
                d1[k] = {}
                q.append((d1[k], d2[k]))
            elif type(d2[k]) != dict:
                d1[k] = d2[k]
            else:
                raise Exception("wtf")

    return dict1