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

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

arr = [1, 2, 3, 10, 2, 3, 4, 5, 6, 9, 9, 1, 2, 3, 1, 2, 3]

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

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

(0, 3)
(3, 1)
(4, 5)
(9, 1)
(10, 1)
(11, 3)
(14, 3)

כל רצף מזוהה על ידי האינדקס בו מתחיל הרצף (המספר הראשון) ואורך הרצף (המספר השני). כך המערך מתחיל באינדקס 0 ברצף של שלושה מספרים עוקבים - המספרים 1, 2 ו-3 ואחריהם באינדקס 3 יש לנו רצף קצר יותר של מספר יחיד הוא המספר 10.

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

def consecutives(arr):
    start = 0
    i = start
    while i < len(arr) - 1:
        if arr[i] + 1 == arr[i + 1]:
            i += 1
        else:
            yield(start, i - start + 1)
            start = i + 1
            i = start
    yield(start, i- start + 1)

ואחרי שיש לנו את הפונקציה קל למצוא את כל הרצפים עם לולאת for רגילה:

for seq in consecutives(arr):
    print(seq)

או למצוא את הרצף הכי ארוך עם פונקציית max:

print(max(consecutives(arr), key=lambda s: s[1]))

או למצוא את הרצף שסכום האיברים בו הוא הגדול ביותר (שוב עם max):

print(max(consecutives(arr), key=lambda s: sum(arr[s[0]:s[0]+s[1]])))

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

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

SELECT  courses.*, count(lessons.id) as lessons_count,
    count(course_labels.id) as labels_count
    FROM "courses"
    LEFT OUTER JOIN "course_labels" ON "course_labels"."course_id" = "courses"."id"
    LEFT OUTER JOIN "lessons" ON "lessons"."course_id" = "courses"."id"
    GROUP BY courses.id

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

הבעיה עם השאילתה היא שה join הכפול גורם לשכפול של כל השורות בטבלה השניה - במילים אחרות כך נראית התוצאה כשאני מוריד את ה count וה group by:

sqlite> SELECT courses.id, lessons.id as lessons_count, course_labels.id as labels_count_1 FROM "courses" LEFT OUTER JOIN "course_labels" ON "course_labels"."course_id" = "courses"."id" LEFT OUTER JOIN "lessons" ON "lessons"."course_id" = "courses"."id";
id|lessons_count|labels_count_1
1|1|6
1|2|6
1|3|6
1|5|6
2|4|
3||

ה id של ה course_label היחיד במערכת הבדיקה שלי הוא 6, והוא מופיע 4 פעמים כדי להתאים ל-4 שיעורים שיש בקורס.

הפיתרון במקרה של ספירה הוא ממש פשוט ומורכב מהמילה היחידה distinct. הנה השאילתה המתוקנת:

SELECT 
    courses.*,
    count(distinct lessons.id) as lessons_count,
    count(distinct course_labels.id) as labels_count_1
FROM "courses"
    LEFT OUTER JOIN "course_labels" ON "course_labels"."course_id" = "courses"."id"
    LEFT OUTER JOIN "lessons" ON "lessons"."course_id" = "courses"."id"
GROUP BY courses.id

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

Lesson.joins(course: :user).select('lessons.*', 'users.id as user_id').where('user_id = ?', user.id)

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

גישה הרבה יותר מדויקת תיראה כך:

Lesson.where(course: user.courses)

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

word =~ /^[A-Z]/

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

word =~ /^\p{Lu}/

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

גם אם הקוד עובד - כשהוא טיפש מדי, או חכם מדי, שווה להתאמץ ולתקן.

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

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

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

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

שפת רובי מציעה 3 דרכים לייצר משתנה גלובאלי - כלומר משתנה שאפשר לגשת אליו מכל מקום בתוכנית. הנה ה-3 בקצרה עם הצעה מתי להשתמש בכל דרך.

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

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

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

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

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

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

const parent = document.getElementById('parent');
let childNodes = parent.childNodes;
let childNodesCount = childNodes.length;

for (let i=0; i < childNodesCount; i++) {
    console.log(childNodes[i].textContent);
}

בעוד שבפרויקט אחר אנחנו עשויים למצוא את:

const parent = document.getElementById('parent');
let childNodes = parent.childNodes;

for (let i=0; i < childNodes.length; i++) {
    console.log(childNodes[i].textContent);
}

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

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

התמיכה של פייתון בביטויים רגולאריים היא לא רעה אבל גם לא טובה במיוחד. לדברים לוקח זמן להיכנס והיא כמעט תמיד מרגישה קצת מאחורי שפות כמו Ruby או אפילו perl בכל מה שקשור לחיפושים על טקסטים. דוגמא פשוטה לזה היא (חוסר) היכולת לחפש Character Properties ב Unicode.

בעברית Character Properties אומר שאנחנו מחפשים תו לפי מאפיין מסוים, בלי להתחייב לשפה. למשל אני יכול לחפש אות במחרוזת בלי שיהיה אכפת לי אם מדובר באות באנגלית או בעברית. ה Property הוא מאפיין של קבוצת תווים וחיפוש לפיו הוא חוצה שפות. אפשר למצוא רשימה של המון Unicode Properties בקישור הזה: http://unicode.org/reports/tr44/#Properties.

אז בפייתון לא מצאתי תמיכה מובנית בחיפוש לפי מאפייני יוניקוד, אבל כן הצלחתי למצוא מודול בשם regex שמאפשר לשלב Character Properties בתוך הביטויים הרגולאריים שאנחנו כותבים ב Python. במשחק שלנו אם מה שאני רוצה זה למצוא אות בתוך מחרוזת אוכל להשתמש בקוד הבא:

In [2]: regex.search(r'\p{L}', 'hello')
Out[2]: <regex.Match object; span=(0, 1), match='h'>

ואנחנו רואים שבמילה hello יש אות. אותו ביטוי מתאים גם לשפות אחרות:

In [4]: regex.search(r'\p{L}', 'שלום')
Out[4]: <regex.Match object; span=(0, 1), match='ש'>

In [5]: regex.search(r'\p{L}', 'привет')
Out[5]: <regex.Match object; span=(0, 1), match='п'>

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

In [3]: regex.search(r'\p{L}', '💩')

אחד התרגילים שאני אוהב לתת כשאני מלמד Multi Threaded Programming בשפת Python הוא פיתוח של Web Spider - או בעברית כלי שמקבל דף אינטרנט ומתחיל ממנו לחפש ולהוריד את כל דפי האתר. העכביש מתחיל בעמוד הראשון, מחפש שם לינקים לדפים נוספים, מוריד אותם ואז ממשיך לחפש בהם לינקים לדפים נוספים.

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

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

import threading
from threading import Thread, Lock
from queue import Queue, Empty
from urllib.parse import urlparse, urlunparse
from pathlib import Path
from bs4 import BeautifulSoup
import requests

base = 'https://www.python.org'
path = '/dev/peps/'
dest = Path('./pydoc')
found_links = set()
found_links_lock = Lock()
q = Queue()

tls = threading.local()

def run(q):
    tls.session = requests.Session()
    while True:
        href = q.get()
        if href is None:
            return

        with found_links_lock:
            if href in found_links:
                print(f"Found {href} that was already downloaded")
                q.task_done()
                continue

            found_links.update([href])

        discover(href)
        q.task_done()


def download(url, to):
    r = tls.session.get(url, allow_redirects=True)
    open(to, 'wb').write(r.content)


def parse(htmlfile):
    with open(htmlfile) as f:
        soup = BeautifulSoup(f.read(), 'lxml')
        new_links = set([
            a['href'] for a in soup.find_all('a')
            if a['href'].startswith('/dev/peps') and
               a['href'] not in found_links])

        for link in new_links:
            q.put(link)

        print(f"Parse done - added {len(new_links)} new tasks")


def discover(href):
    try:
        url = urlparse(href)
        srcpath = url.path

        if not srcpath.startswith(path):
            print("Path out of scope - ignore: ", href)
            return

        if srcpath.endswith('/'):
            destpath = Path(dest) / Path(srcpath[1:]) / 'index.html'
        else:
            destpath = Path(dest) / Path(srcpath[1:])

        destpath.parents[0].mkdir(parents=True, exist_ok=True)

        if url.netloc == '':
            href = base + href

        download(href, destpath)
        parse(destpath)

    except Exception as e:
        print("Failed to discover href ", href, e)
        raise e


def main():
    found_links.add('/dev/peps/')
    start = 'https://www.python.org/dev/peps/'
    q.put(start)
    workers = [Thread(target=run, args=(q,)) for _ in range(4)]
    for w in workers: w.start()
    q.join()
    for _ in range(4):
        q.put(None)

    for w in workers: w.join()


main()

מה הקוד עושה בגדול:

1. הפונקציה download מורידה קובץ מהרשת ושומרת אותו. בשביל שהפונקציה תעבוד יחסית מהר אני משתמש ב requests.Session. בגלל ש requests.Session לא עובד טוב בין תהליכונים לכל תהליכון יש Session משלו שנשמר באמצעות Thread Local Storage.

2. הפונקציה parse מקבלת קובץ html ומחפשת בו קישורים. כל פעם שמצאה קישור חדש היא מוסיפה אותו לתור.

3. הפונקציה המרכזית היא discover. פונקציה זו לוקחת קישור מהתור, מורידה אותו ומפעילה עליו את parse כדי לחפש בו קישורים.

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

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

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

אבל לפני הכל - מה Jest עוזרת לנו? אז Jest היא Test Runner שזה אומר שהיא לוקחת את הקוד שלכם, שולחת אותו ל Babel ואז מריצה אותו בתוך Node.JS כדי לראות אם הכל עובד כמו שצריך. זה אומר שאתם לא צריכים אפילו לפתוח דפדפן כדי לוודא שלא שברתם שום לוגיקה, ואפשר משורת הפקודה להפעיל את הבדיקה ולקבל:

➜  my-jsoneditor git:(master) npm run test

> my-jsoneditor@1.0.0 test /Users/ynonperek/work/projects/intel/my-jsoneditor
> jest

 PASS  src/redux/reducer.test.js
 PASS  src/label.test.js

Test Suites: 2 passed, 2 total
Tests:       2 passed, 2 total
Snapshots:   0 total
Time:        2.723s
Ran all test suites.

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

ג'סט משתמש ב jsdom כדי לאפשר לכם לכתוב גם קוד שצריך את הרכיבים של הדפדפן ולכן לא היתה לו בעיה להריץ לי למשל בדיקה כמו זו:

test('browser dont work', () => {
  expect(document.body).toBeTruthy();
});

נשמע טוב? בואו נלך להתקין אותו ולכתוב כמה בדיקות.