הבלוג של ינון פרק

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

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

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

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

def find_primes(start, end):
    primes = set(range(start, end))
    k = 2

    while k < end:
        for number in set(primes) - set([k]):
            if (number % k) == 0:
                primes.remove(number)

        k += 1

    return primes

הנה ההסבר שלי בעברית: ניקח את כל המספרים בטווח ואז נמחק מהם את כל הכפולות של 2. אחרי זה מוחקים מהם את כל הכפולות של 3, ואז את כל הכפולות של 4 וכך הלאה עד שמסיימים למחוק את כל הכפולות של כל המספרים.

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

קל גם לראות את הבעיות במנגנון רק מתוך הקוד (או מתוך התיאור בעברית):

1. לא צריך לבדוק את כל הכפולות של 4. הרי כבר מחקנו את 4 כשמחקנו את 2, ולכן מחקנו גם את כל הכפולות שלו.

2. לא צריך להתקדם עם k עד סוף הטווח, מספיק להתקדם עד שורש של end.

3. לא צריך להתקדם כל פעם ב-1, אפשר לדלג על מספרים זוגיים ולקדם את k ב-2.

4. לא צריך ליצור set חדש כל איטרציה, אפשר למחוק תמיד מאותו set מקורי.

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

אחרי שחיברתי את כל האופטימיזציות הגעתי לקוד הבא:

def find_primes(start, end):
    k = start if start % 2 == 1 else start + 1
    primes = set(range(start, end)) - set(range(4, end, 2))

    while k < math.sqrt(end) + 1:
        i = 2 * k
        while i < end:
            if i in primes:
                primes.remove(i)
            i += k

        while True:
            k += 2
            if k in primes: break

    return primes

אני אוהב אותו. אולי אפשר לכתוב גירסא יותר קריאה אבל בגדול הוא די ממחיש את האלגוריתם אחרי כל האופטימיזציות וכמובן מבחינת מהירות עם זה כבר אפשר לעבוד. איתור כל 1229 המספרים הראשוניים עד 10,000 לקח 0.04 שניות, וגם כשעליתי לחפש את כל המספרים הראשוניים עד מיליון הצלחתי למצוא את כל 78,498 המספרים בפחות משניה (0.53 שניות למי שרוצה לדייק).

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

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

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

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

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

ואפשר כמובן גם אחרת - "זה יהיה מוכן כשזה יהיה מוכן" זו עמדה לגיטימית לגמרי אם איכות המוצר חשובה לכם יותר מאשר לשחרר אותו. ללארי וול לקח עשרים שנה לשחרר את perl6, אבל יש הרבה מאוד פרויקטי קוד פתוח שמתאמצים לשחרר גירסא בזמן אבל לא מתאבדים על זה. אף אחד לא נפל מהכסא כש Concurrent Mode של ריאקט לא היה מוכן באמצע 2019 (ועדיין לא מוכן לקראת אמצע 2020).

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

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

אני מזכיר שהקוד למימוש BFS שכתבתי נראה במקור כך (זה הקוד עם הבאג):

def bfs(q, callback):
    while len(q) > 0:
        node = q.popleft()

        # Skip this node, we've already visited it
        if hasattr(node, 'visited') and node.visited is True: continue

        # Now we can start processing the node:
        # 1. Let's notify outside code that we found a new node
        callback(node)

        # 2. Let's mark it as visited so we won't have to
        #    process it again
        node.visited = True

        # 3. Let's add all of its neighbors to the queue
        #    so we'll be able to process them too
        for friend in node.neighbours:
            q.append(friend)

זיהיתם את הבאג? אם לא, קחו כמה דקות לקרוא את זה שוב.

הבעיה היא המנגנון ששומר האם כבר ביקרנו ב Node מסוים או לא: המנגנון מסמן את ה Node בתור כזה שביקרנו בו כדי שלא נחזור לאותו Node פעמיים, אבל מה קורה אם נרצה להפעיל את bfs פעם שניה על אותו עץ?

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

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

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

def bfs(q, callback):
    visited_nodes = set()
    while len(q) > 0:
        node = q.popleft()

        # Skip this node, we've already visited it
        if node in visited_nodes: continue

        # Now we can start processing the node:
        # 1. Let's notify outside code that we found a new node
        callback(node)

        # 2. Let's mark it as visited so we won't have to
        #    process it again
        visited_nodes.add(node)

        # 3. Let's add all of its neighbors to the queue
        #    so we'll be able to process them too
        for friend in node.neighbours:
            q.append(friend)

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

פיתרון שני שמעניין לראות עושה שימוש ב ExitStack כדי להוסיף קוד ניקוי אחרי כל שינוי, זה נראה כך:

from contextlib import ExitStack
def bfs(q, callback):
    with ExitStack() as stack:
        while len(q) > 0:
            node = q.popleft()

            # Skip this node, we've already visited it
            if hasattr(node, 'visited') and node.visited is True: continue

            # Now we can start processing the node:
            # 1. Let's notify outside code that we found a new node
            callback(node)

            # 2. Let's mark it as visited so we won't have to
            #    process it again
            node.visited = True
            stack.callback(node.reset_visited)

            # 3. Let's add all of its neighbors to the queue
            #    so we'll be able to process them too
            for friend in node.neighbours:
                q.append(friend)

פיתרון זה יותר גנרי ויותר אופייני לגישה מונחית עצמים כיוון שאפשר להוסיף כל Callback Function שרוצים ל Exit Stack, ובסוף בלוק ה with באופן אוטומטי פייתון יריץ את כל קודי הניקוי שלנו. הוא גם יותר מתאים לגישת ה Object Oriented כיוון שכל אוביקט Node אחראי על קוד הניקוי שלו.

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

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

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

הקוד הבא מדפיס 9, וזה הגיוני אבל קצת מוזר:

let x = 09;
console.log(x);

מוזר כי ב Python קוד דומה זורק שגיאה:

# Error: SyntaxError: leading zeros in decimal integer literals are not permitted
x = 09
print(x)

ב Ruby הקוד זורק שגיאה:

# SyntaxError ((irb):1: Invalid octal digit)
x = 09

ב Clojure הקוד זורק שגיאה:

;; Invalid number: 09
(let [x 09] (print x))

והאמת שרק Scheme הסכימה לשתף איתי פעולה ולהדפיס את המספר 9 בדומה ל JavaScript:

(display 09)

אבל, ופה JavaScript מתחילה להיות מוזרה, נסו לחשוב מה קורה כשמחליפים את ה-9 ל-10:

let x = 010;
console.log(x);

ולחידה - מה קורה שם? למה זה קורה (רמז בהודעות השגיאה של כל השפות האחרות)? ואיך Strict Mode יכול לעזור לי להיזהר ממצבים כאלה?

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

עד עכשיו כל פעם שהיה לי קוד שנראה כך:

for (let i=99; i > 0; i--) {
    consoe.log(`${i} bottles of beer on the wall`);
}

ורציתי לעצור למשל כש i היה שווה ל-10, הוספתי את התנאי הבא לקוד (באמת!):

for (let i=99; i > 0; i--) {
    consoe.log(`${i} bottles of beer on the wall`);
    if (i == 10) debugger;
}

והנה, לגמרי במקרה הגעתי היום לשים נקודת עצירה בכרום, אבל במקום ללחוץ על הכפתור השמאלי של העכבר כשהצבעתי על מספר השורה בחלון ה Debugger, נלחץ הכפתור הימני. מסתבר שבמצב כזה כרום פותח תפריט כפתור ימני ואחת האופציות בתפריט נקראת Conditional Breakpoint. לוחצים על הפריט, כותבים את התנאי (i == 10 במקרה שלנו) ו... Voila, לא צריך לכתוב קוד JavaScript בשביל לעצור רק כשתנאי מסוים מתקיים.

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

אחד הטריקים השימושיים באתרי מובייל הוא להפוך את ה Placeholder של תיבת קלט ל Label של אותה תיבה. במילים אחרות במקום לכתוב תווית Email ואחריה תיבת טקסט עבור אימייל עם placeholder שמייצג קלט אפשרי כמו זה:

<label>
    Email:
    <input type="email" placeholder="demo@gmail.com" />
</label>

אנחנו רואים תיבות טקסט שנראות כך:

<input type="email" placeholder="Email Address" />

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

פיתרון אפשרי אחד למצב נקרא Floating Labels או תוויות צפות. זה עובד ככה:

1. במצב רגיל אנחנו מסתירים את התווית כדי שמשתמש יראה רק את ה Placeholder בתוך התיבה.

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

קוד? ברור. הנה ה HTML:

<label>
  <input type="text" placeholder="name" />
  <span class="label-text">Name</span>
</label>

וזה ה CSS:

label {
    position: relative;
    height: 50px;
    display: flex;
    flex-direction: column-reverse;
}

.label-text {
  left:-10000px;
  position:absolute;
  top:auto;
  width:1px;
  height:1px;
  overflow: hidden;
  background: orange;
  color: white;
}

label input {
  font-size: 24px;
  height: 100%;
  border: 1px solid orange;
  box-sizing: border-box;
}

input:focus::placeholder {
  color: transparent;
}

input:focus + .label-text {
  position: relative;
  width: auto;
  height: auto;
  left: 0;
}

input:focus {
  font-size: 18px;
  height: auto;
}

שימו לב שבגלל מגבלות של CSS אני צריך לכתוב את ה label-text אחרי ה input (כדי שאוכל להשתמש בסימן הפלוס לעצב את ה label-text).

דבר נוסף ששווה לראות הוא השימוש ב position כדי להסתיר את הטקסט, אבל להשאיר אותו קריא עבור Screen Readers. בצורה כזאת כשמגיע קורא מסך לקרוא את הדף הוא עדיין יוכל להקריא את טקסט התווית (זה פותר לנו בעיה שהיתה בשימוש רגיל ב Placeholder לצורך הגדרת תווית לתיבה). המנגנון שולח את הטקסט אלף פיקסלים שמאלה אבל משאיר אותו בגודל פיקסל אחד, כי קוראי מסך מתעלמים מאלמנטים בגודל 0.

ויש גם קודפן בקישור: https://codepen.io/ynonp/pen/Vwvbrxm, או בהטמעה:

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

השבוע העליתי פיצ'ר של Server Side Rendering שדחף אותי לפתור לפחות לאתר טוקוד את הבעיה השניה ובפוסט היום אנסה לסכם את עיקרי הדברים.

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

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