לפני שבועיים העליתי פוסט עם אלגוריתם שמוודא שלוח סודוקו הוא תקין (אתן יכולות לקרוא אותו פה) ולפני כמה ימים הקוראת העירנית @rinaarts הפנתה את תשומת לבי לעובדה שבפונקציה הבסיסית שמוודאה את לוח הסודוקו שלי השתמשתי באלגוריתם בזבזני בסיבוכיות (O(N2, ואף הציעה פתרון יעיל יותר ב-(O(N.
אז קודם כל, תודה לרינה 🙂
שנית, לפני שאגיע לפתרון החלופי שהיא הציעה, אני חייבת לשאול איך בעצם קרה המצב הזה?
אני ממש לא מתיימרת למצוא את הפתרון הטוב ביותר לכל שאלה, אבל הפעם אכן היה מדובר בטעות בולטת מאוד, איך פספסתי אותה?
מה שקרה הוא שבשאלת הסודוקו המקורית לא עשיתי בדיקת סיבוכיות. אולי זה היה בגלל שחזרתי מראיון מעייף, אולי זה היה בגלל מזג האוויר החם, אבל העובדה היא ששכחתי לחשב את הסיבוכיות של האלגוריתם שלי ולבדוק אם אני יכולה לשפר אותה, וזה מיד התנקם בי. אז קחו את זה כלקח לעתיד – אף פתרון לא גמור עד שלא בדקתן את הסיבוכיות שלו והשתכנעתן שאתן לא יכולות לשפר אותה!
כעת לשאלה עצמה.
בפתרון הסודוקו המקורי שלי חילקתי את הבדיקה לשני חלקים – חלק שבונה את השורות/עמודות/קוביות, ופונקציה שבודקת את התקינות של המספרים באותה חתיכה.
הנה פונקציית הבדיקה שלי –
def check_valid_vector(vector): for i in range(0,9): if vector.count(i) != 1: return False return True
הוקטור כאן הוא מערך של 9 איברים שמייצגים שורה/עמודה/קוביה.
מה הסיבוכיות של פונקציית הבדיקה שלי?
יש כאן לולאה יחידה בגודל N (עבור N=9), ובכל איטרציה אני מבצעת פעולה “יחידה” – count. הבעיה היא בדרך שבה מתבצעת פעולת count. למרות שמדובר בפקודה יחידה ולא בלולאה, מה שקורה בפועל הוא ש-count עוברת על כל האיברים במערך וסופרת את מספר החזרות של i. כלומר, הסיבוכיות של count היא (O(N, והסיבוכיות הכללית של הפונקציה היא (O(N2.
עכשיו כשהבנתי מה קרה – איך אני יכולה לשפר את הסיבוכיות של check_valid_vector?
ההצעה של רינה הייתה להשתמש בסט.
סטים (בפייתון, לא מתחייבת על שפות אחרות) ממומשים כ-hash-table, ולכן הסיבוכיות של הכנסה והוצאה של איברים מהם היא (O(1. אני יכולה להשתמש בסט כדי לעשות מעקב אחרי האיברים בכל וקטור – אני ארוץ על הוקטור ואכניס את כל האיברים שאני מוצאת לסט. אם הסט הסופי שהתקבל הוא באורך 9, זה אומר שכל האיברים בין 1 ל-9 הופיעו בוקטור, כל אחד פעם אחת בדיוק. אם יש איברים שחזרו על עצמם פעמיים, הסט יהיה קטן יותר.
אני אכתוב את הפתרון הזה –
def check_valid_vector(vector): num_set = set() for n in vector: num_set.add(n) return len(num_set) == 9
*כמובן שבמקום לבנות ידנית את הסט יכולתי להשתמש בפקודת יחידה שממירה רשימה לסט, אבל רציתי להדגים את הסיבוכיות בבירור.
הסיבוכיות של הפונקציה החדשה שלי היא (O(N, ולכן הפונקציה של האלגוריתם המלא שבודק תקינות של לוח סודוקו, היא (O(N2.
תודה לרינה ולכל שאר הקוראים ששולחים לי הצעות ותיקונים, זה מדהים ואני סופר מעריכה את זה.
קוד משופר בגיט – https://github.com/mgershovitz/maya_solves/blob/master/sudoku_checker_better.py
אני בכלל לא בטוח שזה שיפור (אבל אני גם לא בטוח שזה לא).
כאילו, כן, גישה למערך היא O(N) zz בעוד גישה למפת גיבוב היא O(1) zzz, אבל הקבועים הרבה יותר גדולים עבור מפת גיבוב (כי בכל גישה צריך להפעיל פונקציית גיבוב, כי בהכנסות יכול להיות rehash, וכו’).
היות והגודל הוא קבוע ויחסית קטן (כי מבנה הנתונים המדובר תמיד מכיל רק תשעה איברים), יש סיכוי מאוד טוב שדווקא עדיף להשתמש כאן במבנה נתונים יותר פשוט כדי להפחית את הקבועים.
לדעתי יכול להיות מעניין לתזמן את שתי הגרסאות ולבדוק מי מהירה יותר.
היי, שי.
אז כמובן שאתה צודק לגבי הזמנים.
בשאלה הזו (ובבלוג באופן כללי) אני מתייחסת רק לסיבוכיות ולא לזמנים (כי בדרך כלל אני גם
פותרת ל-n כללי, ולא קבוע כמו פה) ולכן תמיד שואפת לסיבוכיות הטובה ביותר.
אבל זו נקודה חשובה, וברור שכשעוברים מהתיאוריה לעולם האמיתי זה קריטי לשים לב לקבועים ולזמנים בפועל, כי אלגוריתם עם סיבוכיות גרועה יותר אכן יכול להיות פשוט ומהיר יותר.
אפשר לקחת בחשבון bitset כמימוש חסכוני במקום (עם גישה מעט יקרה יותר מאשר מערך).
פעולת הכנסה לסט מתבצעת בזמן קבוע בממוצע אבל בזמן לינארי במקרה הגרוע ביותר. כלומר, במקרה הגרוע ביותר, הפעולה שאת מבצעת עדיין יכולה לרוץ בזמן ריבועי.
אבל כשאת יודעת מאיפה מגיעים האיברים אפשר לעבוד חכם יותר. ספציפית, אם את רוצה לוודא שוקטור באורך n מכיל את המספרים 1 עד n אפשר לאתחל רשימה ריקה באורך n, לעבור על הוקטור שלך ולכל כניסה שהערך שלה הוא k לשים 1 ברשימה שלך במקום k-1. אחרי שאת עושה את זה סכום הרשימה שלך הוא n אם ורק אם הוקטור שלך תקין, והזמן הוא לינארי במקרה הגרוע ביותר.
היי, נעם.
זה נכון כשמסתכלים על פעולת הכנסה יחידה שפעולת הכנסה לסט יכולה להתבצע ב-(O(N, אבל כשמבצעים n פעולות הכנסה נהוג להתייחס לסיבוכיות ה-amortized – הסיבוכיות הכוללת של כל הפעולות מחולקת במספר הפעולות, ולכן הסיבוכיות של הכנסה יחידה עדיין נחשבת ל-(O(1.
יש פה משהו קצת יותר עדין – הניתוח של פעולות על מבנה שמתמשי ב-hashing הוא ניתוח הסתברותי. גם ניתוח amortized של מבנה כזה הוא ניתוח הסתברותי ולכן אפשר לדבר על expected amortized time. ידוע לי על מנגנוני hash רבים שמבטיחים זמן קבוע ב-expected amortized analysis, אבל לא ידוע לי על אף מגנון שמבטיח שזמן הפעולה יהיה תמיד O(1)zz בניתוח amortized.
ההצעה שאני הצעתי לעומת זאת פעולת ב-O(n)zz תמיד, בלי ניתוח amortized ובטח שבלי ניתוח הסתברותי.
מעבר לכך לא ברורה לי ההתעקשות על שימוש ב-hashing כשאפשר לפתור את הבעיה הזו באופן דטרמיניסטי, יעיל לפחות באותה מידה (ולטעמי, כאמור, יותר) ופשוט (המימוש של האלגוריתם בפייתון לוקח מספר זהה של שורות כמו המימוש שמשתמש ב-set).
אם כבר לעבוד חכם, בשביל מה הסכימה?
תתחיל עם מערך של אפסים באורך n, לכל מספר k תבדוק את התא ה-k, אם הוא 0 תשים 1 ואם הוא 1 תחזיר False.
אחרי שסיימת תחזיר True.
זה מעלים את הסכימה המיותרת של המערך, ומשתמש בעובדה שהשורה\טור\קוביה לא חוקית אם ורק אם יש מספר שמופיע בה פעמיים, שזה בעצם בדיוק הפתרון של רינה\מאיה רק עם גיבוב טריוויאלי.
כמה הערות:
1. אם כבר משתמשים בhash table למה לא לבדוק אם האיבר קיים לפני שמכניסים אותו. ככה אם האיבר כבר קיים אז עוצרים מיידית ואין צורך לחשב את כל האיברים. הבדיקה היא גם כן O(1).
2. יש כאן הנחה סמויה שחישוב אורך של set הוא פונקציה בO(1). האם את בטוחה שזה נכון?
3. אם מדובר על כמות יחסית קטנה של איברים בווקטור (עד 32 או 64) אפשר להשתמש בbitmask. מאתחלים לאפס ב O(1) ואז על כל איבר בווקטור בודקים אם הביט המתאים כבר דלוק ואם לא אז מדליקים אותו.