רשימת המילים בעברית בפחות מ-50 שורות קוד

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

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

איך נייצר את הרשימה?

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

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

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

החומרים הדרושים

כדי לקרוא קוד HTML נשתמש בספרייה BeautifulSoup, ובספריית re הסטנדרטית של python. המחלקה Counter מהמודול collections תשמש לשמירת מיפוי בין כל מילה למספר ההופעות שלה, והספרייה progressbar2 תשמש ליצירת מד התקדמות.

from bs4 import BeautifulSoup
from collections import Counter
from progressbar import ProgressBar
import re, os

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

שלב ראשון – יצירת רשימה של שמות הקבצים

נתחיל בחילוץ (unzipping) הקובץ שהורדנו, המכיל את כל הערכים בויקיפדיה, ע"י שימוש בתוכנה 7Zip. התוצאה היא עץ תיקיות ענקי המחולק לתיקיות לפי האות הראשונה של שם הערך, לאחר מכן האות השנייה וכו'. נרצה לעבור על כל הקבצים בעץ, ולשמור את הנתיבים שלהם ברשימה אחת ארוכה.

נעשה זאת ע"י שימוש בפונקציה walk של מודול os, המקבל תיקייה, ומחזירה איטרטור (iterator) על כל הקבצים והתיקיות בה בצורה רקורסיבית:

all_files = []
for root, folders, filenames in os.walk(u'wikipedia-he-html'):
  for filename in filenames:
    all_files.append(os.path.join(root, filename))

שימו לב שאנו מעבירים לפונקציה את שם התיקייה בתור מחרוזת unicode (מתחילה באות u). דבר זה נדרש כדי שהפונקציה תתמוך בנתיבים המכילים עברית.

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

נסו להדפיס את אורך הרשימה all_files כדי לוודא שהיא אכן ארוכה מאוד.

שלב שני – קריאת תוכן הקבצים

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

with ProgressBar(max_value = len(all_files)) as progress:
  for i, file_path in enumerate(all_files):
    progress.update(i)
    html = open(file_path, "rb").read().decode('utf8')

שימו לב שקריאת הקובץ מורכבת משלושה שלבים:

  1. פתיחת הקובץ לקריאה באמצעות הפונקציה open. בחלק ממערכות ההפעלה (בעיקר Windows) חשוב להעביר את הפרמטר "rb" (שמשמעותו read binary) כדי שהקובץ ייקרא בדיוק כמו שהוא.
  2. קריאת תוכן הקובץ לתוך מחרוזת ע"י הפונקציה read.
  3. פתיחת הקידוד של הקובץ, כלומר המרת תוכנו מפורמט בינארי בקידוד UTF-8 למחרוזת מסוג unicode, ע"י הפונקציה decode.

אם שאלתם את עצמכם איך אנחנו יודעים שקידוד הקובץ הוא UTF-8, התשובות הן: (א) זהו הקידוד הנפוץ ביותר לדפי HTML; (ב) כמעט כל עורך טקסט מתקדם יזהה זאת עבורכם כשתפתחו באמצעותו את אחד הקבצים; (ג) זה כתוב בתוך הקבצים: charset=UTF-8.

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

all_files = all_files[:1000]

כעת נסו להריץ את הקוד, סביר להניח שקיבלתם את השגיאה הבאה:

UnicodeDecodeError: 'utf8' codec can't decode byte 0x89 in position 0: invalid start byte

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

try:
  html = open(file_path, "rb").read().decode('utf8')
except UnicodeDecodeError:
  continue

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

שלב שלישי – מציאת כל הטקסט בעמוד

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

הדרך הפשוטה ביותר היא שימוש בספרייה BeautifulSoup הנועדה לפענוח קוד HTML:

soup = BeautifulSoup(html, 'html.parser')
for p in soup.find_all('p'):
  # do something with p

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

דרך חלופית ומהירה הרבה יותר היא מציאת כל התגיות <p> בקובץ ע"י שימוש בביטויים רגולרים (regular expressions), ופענוח התוכן שלהן בלבד:

PARAGRAPHS_PATTERN = re.compile(r"<p>(.*?)</p>")

for p_html in PARAGRAPHS_PATTERN.findall(html):
  p = BeautifulSoup(p_html, 'html.parser')

נתעכב על הביטוי הרגולרי: הוא מתחיל בתגית הפותחת <p> ומסתיים בתגית הסוגרת </p>. תוכן התגית מותאם (matched) ע"י הביטוי הנפוץ נקודה-כוכבית, והוא בתוך סוגריים מכיוון שרק בו אנו מעוניינים, ללא תגיות הפסקה. אך מה פשר סימן השאלה?

נניח שיש לנו שתי פסקאות בעמוד:

<p>hello from icode.co.il</p>
<p>don't forget to subscribe</p>

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

<p>hello from icode</p>
<p>don't forget to subscribe</p>

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

<p>hello from icode</p>
<p>don't forget to subscribe</p>

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

  1. פעמים רבות התגית p תכיל תכונות (attributes) שונות, למשל <p class="blue">, ולכן לא תיתפס ע"י הביטוי הרגולרי. בויקיפדיה תגיות הפסקה לא מכילות תכונות.
  2. במידה ותגית p נמצאת בתוך תגית p אחרת, הביטוי הרגולרי יחזיר תוצאה שגויה. אמנם הדבר לא חוקי בקוד HTML, אך אתרים רבים עדיין מבצעים את הטעות הזאת, והדפדפנים סלחנים כלפיה. למזלנו בויקיפדיה קוד ה-HTML הוא תקני (ואף מיוצר אוטומטית), ולכן הבעיה הזאת לא קיימת.

בשלב זה המשתנה p מכיל אובייקט מטיפוס Tag (של BeautifulSoup), המכיל ייצוג כלשהו של תוכן הפסקה. אך זה עדיין לא מספיק, מכיוון שהייצוג הזה עלול להכיל בעצמו קוד HTML:

<p>hello from <a href="/">icode</a><p>

למזלנו, BeautifulSoup מספקת פונקציה פשוטה להמרת קוד HTML לטקסט:

p_text = p.get_text() # => "hello from icode"

שלב רביעי ואחרון – חלוקה למילים וספירתן

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

words = p_text.split()

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

CHARS_PATTERN = re.compile(ur"""[^אבגדהוזחטיכלמנסעפצקרשתןףץםך'\- "]""")
p_text = CHARS_PATTERN.sub('', p_text)

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

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

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

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

  • קובץ הקוד שלנו צריך להיות שמור בקידוד UTF-8. רוב עורכי הטקסט תומכים בשמירה בקידוד זה.
  • מחרוזות המכילות עברית חייבות להתחיל בתו u (מסמל unicode) לפני המחרוזת.
  • יש להוסיף בתחילת הקובץ את ההערה הבאה:
# -*- coding: utf-8 -*-

כעט נשתמש במבנה הנתונים Counter כדי לספור כמה מופעים יש מכל מילה:

freq = Counter()

for word in words:
  word = word.strip('="')
  if len(word) > 1:
    freq[word] += 1

בקטע קוד זה אנו מבצעים 3 פעולות עבור כל מילה:

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

סיימנו! בסיום הריצה המשתנה freq הוא Counter (סוג של מילון) שמפתחותיו הן כל המילים, וערכיו הם מספר ההופעות של כל מילה בכל הטקסט. כל שנשאר הוא לשמור לקובץ בפורמט לבחירתנו, למשל:

open('words.txt', "wb").write(
  u"\n".join("%s, %s" % x for x in freq.most_common()).encode('utf8'))

חשוב לזכור לקודד כ-UTF-8 (או קידוד אחר התומך בעברית) טרם השמירה.

קובץ המילים אמור להיראות כך:

של, 523462
את, 362830
על, 280208
הוא, 155791
לא, 122371
...
פילי, 44
הלשכות, 44
שליחו, 43
בבואה, 43
...

העשרה: שיפור מהירות הריצה

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

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

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

נסו לעבור על הקוד המלא ולמצוא אותן.

מה הלאה?

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

  1. זיהוי והסרת אותיות קישור מהמילים. למשל המילה "במכונית" תיספר כמו המילה "מכונית"
  2. הסרת מילים שתדירותן נמוכה מדי
  3. שימוש במקור טקסט אחר
  4. השוואה בין מקורות טקסט שונים ליצירת רשימת מילים שאינה מוטה למקור מסויים
  5. חיפוש ביטויים נפוצים במקום מילים נפוצות
  6. תמיכה בשפות נוספות
  7. שימוש ב-dump עדכני יותר של ויקיפדיה (קיים בפורמטים שאינם HTML)

הקוד המלא

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

טריקים שכל מפתח Python חייב להכיר – חלק ב'

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

אינדקס שלילי

שפת פייתון מאפשר גישה לאיבר במיקום ה-x מסוף הרשימה ע"י שימוש באינדקס שלילי. לדוגמה:

my_list[-1]

יחזיר את האיבר האחרון ו-

my_list[-3]

יחזיר את האיבר השלישי מהסוף.

defaultdict ו-Counter

כנראה שאתם כבר מכירים את המילון (dict), אבל האם ידעתם ש-Python מספקת גם מילון עם ערכי ברירת מחדל? לדוגמה:

from collections import defaultdict
groups = defaultdict(list)
groups["fruits"].append("banana") // groups["fruits"] = ["banana"]
print groups["vegetables"] // []

מבנה נתונים דומה הוא Counter, המזכיר את defaultdict(int) אך מספק מספר פונקציות שימושיות עבור מניה של אובייקטים:

from collections import Counter
counter = Counter()
for char in "banana":
  counter[char] += 1
print counter.most_common() // [('a', 3), ('n', 2), ('b', 1)]

Interactive Debugging

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

שיטה נוספת ולעתים נוחה יותר לביצוע דיבאג היא שימוש בדיבאגר המובנה של python ששמו הוא, באופן לא מפתיע, Python Debugger, ובקיצור PDB. באמצעות הוספת שורה אחת לקוד שלכם, תוכלו לעצור את הקוד בזמן ריצה, ולקבל python shell בתור ה-context הנוכחי של התוכנית שלכם, ממנו תוכלו לגשת למשתנים ולהריץ כל קוד Python שבא לכם:

import pdb; pdb.set_trace()

כמו לכל דיבאגר, גם ל-PDB יש פקודות שונות עליהן ניתן לקרוא כאן.

הפונקציה partial

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

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

def round3(n):
    return round(n, 3)

>> round3(3.141592653)
3.142

הפונקציה partial מאפשרת לנו להגיע לאותה תוצאה בשורה אחת:

round3 = partial(round, ndigits = 3)

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

המודול itertools

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

  • הפונקציה chain משרשרת מספר איטרטורים לאיטרטור אחד, שכאשר רצים עליו, פשוט רץ על כל האיטרטורים אחד אחרי השני:
chain('ABC', xrange(3)) // A B C 0 1 2
  • הפונקציה product מחזירה מכפלה קרטזית של מספר איטרטורים. למשל עבור שני איטרטורים היא תחזיר את אוסף כל הזוגות המורכבים מאיבר מהאיטרטור הראשון ואיבר מהאיטרטור השני, בדומה לשתי לולאות מקוננות:
product("AB", "12") // ('A', '1'), ('A', '2'), ('B', '1'), ('B', '2')
  • הפונקציה izip דומה לפונקציה המובנית zip (אין קשר לדחיסת נתונים, אלא ל"ריץ' רץ'"), אבל מחזירה איטרטור במקום רשימה. שימושית כאשר רוצים לרוץ על שני איטרטורים או יותר המכילים מספר רב של ערכים, בלי לטעון את כל המידע לזיכרון בבת אחת.
  • פונקציות מעניינות נוספות: combinations, permutations, groupby, cycle.

Pylint

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

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

> pip install pylint
> pylint --reports=n myapp.py
F:  5, 1: Unable to import 'non.existing' (import-error)

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

המודול logging

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

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

import logging
...
logging.warning("Invalid parameter %s", param)

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

import logging.config
logging.config.dictConfig({
  'version': 1,
  'formatters': { 
    'standard': { 
      'format': '%(asctime)s [%(levelname)s] %(name)s: %(message)s'
    },
  },
 'handlers': { 
    'file': { 
      'formatter': 'standard',
      'class': 'logging.FileHandler',
      'filename': 'myapp.log',
    },
  },
  'loggers': { 
    '': { 
      'handlers': ['file'],
      'level': 'INFO',
      'propagate': True,
    },
  },
})

למה Javascript מרגישה לחלקנו כמו סינית?

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

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

בתור מישהו שכותב Javascript כבר שנים רבות, הבעיה הזאת תמיד סיקרנה אותי. הרי התחביר של Javascript דומה מאוד לשפות אחרות (כמו C++) ויכולותיה "out of the box" מצומצמות מאוד, אז מדוע מתכנתים רבים מתקשים בהבנתה? אחרי מחשבה רבה אני מאמין שמצאתי את שורש הבעיה.

אסינכרוניות מובנית

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

ניקח לדוגמה את הפסאודו קוד הבא, הכתוב בסגנון קלאסי:

name = wait_for_user_input()
print "Welcome " + name

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

אחד המאפיינים המעניינים והחשובים ביותר של שפת Javascript הוא הריצה ב-thread אחד בלבד. כלומר אם היינו כותבים קוד כזה ב-JS, כל ממשק המשתמש (אתר, אפליקציה וכד') היה נתקע עד לקבלת הקלט.

אז איך בכל זאת מאפשרת שפת Javascript פעולות המצריכות המתנה (למשתמש, לשרת וכד')? התשובה לכך היא, לדעתי, המפתח להבנת Javascript.

פונקציות Callback ותכנות מבוסס אירועים

ניקח את הדוגמה הקודמת ונשכתב אותה למשהו דומה יותר לקוד Javascript:

function handle_user_input(name) {
    console.log("Welcome " + name);
}

wait_for_user_input(handle_user_input);

למעשה שינינו שלושה דברים:

  1. הגדרנו פונקציה חדשה המטפלת בקלט שהגיע מהמשתמש. או במילים אחרות, הגדרנו event handler, כאשר האירוע (event) בו הוא מטפל הוא הגעת קלט מהמשתמש.
  2. העברנו את הפוקציה החדשה בתור פונקציית callback לפונקציה wait_for_user_input. כלומר, רק כאשר יתקבל הקלט מהמשתמש, הפונקציה שלנו שלנו תיקרא ותכתוב את הקלט ללוג.

ע"י ביצוע שינוי פשוט זה הפכנו את הקוד ל-non blocking, כלומר הקוד לא יעצור ויחכה לקלט, אלא ימשיך לרוץ וכאשר יגיע קלט – הוא יטופל מיד (כמובן שיש צורך לשנות את המימוש של wait_for_user_input, אבל כרגע זה פחות חשוב).

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

wait_for_user_input(function(name) {
    console.log("Welcome " + name);
})

אני מאמין שהשינוי הקטן הזה הוא המפתח להבנת קוד Javascript. אז מה קרה פה? במקום להגדיר בנפרד את פונקציית ה-callback ולתת לה שם, הפכנו אותה לפונקציה אנונימית (anonymous function) והעברנו אותה ישירות לפונקציה wait_for_user_input.

השינוי הזה הפך את הקוד למשהו שלא דומה לקוד של אף שפת תכנות קלאסית!

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

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

document.getElementById("btn").addEventListener("click", function(evt) {
  if (validate_data()) {
    do_ajax_call(function (data) {
      if (data.success) {
        document.getElemenetById("next").addEventListener("click", function() {
          window.location.href = '/thank-you';
        });
      } else {
        console.log("error: " + data.msg);
      }
    });
  }
});

לא עוד Callback Hell

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

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

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

fetch_data_from_server(function(data) {
    // handle data
    fetch_more_data_from_server(more_data) {
        // handle more data
    }
});

ניתן שמות לפונקציות האנונימיות ונחלץ אותן החוצה:

fetch_data_from_server(handle_data);

function handle_data(data) {
    // handle data
    fetch_more_data_from_server(handle_more_data);
}

function handle_more_data(more_data) {
    // handle more data
}

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

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

Callback Hell

לקריאה נוספת:

פרוטוקול TCP במילים פשוטות

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

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

פרולוג

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

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

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

בעיה ראשונה – שינוע מידע רב

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

בעיה שניה – סדר ההגעה

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

מכיוון שמטרתו של פרוטוקול TCP הוא לאפשר העברת זרם מידע רציף, שיתקבל בדיוק כפי שנשלח, יש צורך לסדר את הפקטות שהתקבלו לפי הסדר בו נשלחו. הפתרון: הצמדת מספר סידורי רץ (sequence number) לכל פקטה1 ע"י הצד השולח, כך שהצד המקבל יוכל לשחזר את הסדר המקורי שלהן, גם אם הן הגיעו בסדר שונה מהסדר בו נשלחו. לדוגמה, אם צד א' שלח 3 פקטות, וצד ב' קיבל את פקטות 2 ו-3 בלבד, הוא יחכה עד להגעת פקטה מספר 1 ורק לאחר מכן ירכיב את המידע ויעביר אותו הלאה.

בעיה שלישית – פקטות אבודות

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

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

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

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

שאלה מתבקשת היא – האין כל ה-acks הללו מוסיפים תקורה רבה מדי על הקו? התשובה המיידית היא – לא, זאת מכיוון שה-acks לרוב אינם נשלחים בתור פקטות בפני עצמן! פרוטוקול TCP מנצל את העובדה שהחיבור הוא דו כיווני (full duplex, שני הצדדים שולחים מידע אחד לשני), כדי לצרף את האישורים לפקטות נתונים שגם ככה היו אמורות להישלח בכיוון ההפוך. תכונה זאת נקראת piggybacking. אך אם צד אחד רק מקבל מידע ולא שולח כלום? במקרה זה הוא יחכה כדי "לצבור" פקטות, ולאחר שעבר זמן מסויים הוא ישלח אישור אחד שיכסה את כל הפקטות בבת אחת.

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

בעיה רביעית – הצב והארנב

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

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

הנה סרטון נחמד הממחיש את העיקרון:

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

בעיה חמישית – מישהו שומע אותי?

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

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

חבר: "הלו?"
אני: "היי, מה שלומך?"
חבר: "מצויין, מה איתך?"

תהליך זה נקרא "לחיצת יד תלת שלבית" (Three-way handshake) והוא השלב הראשון בכל חיבור TCP. שמותיהן המקצועיים של שלושת ההודעות הנשלחות הם SYN, SYN-ACK, ACK. לחיצת יד זאת מבטיחה (בסבירות גבוהה) ששני הצדדים מוכנים לדבר אחד עם השני, ומסמלת את תחילת חיבור ה-TCP. בנוסף, כחלק מהתהליך שני הצדדים מסכמים ביניהם איך תתבצע התקשורת – למשל מהו המספר הסידורי של הפקטה הראשונה, מהו גודל החלון ההתחלתי ועוד.

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

אני: "אני סבבה, ואתה?"

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

בעיה שישית – אתה עוד שם?

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

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

בעיה שביעית – "את-ה מק-קו-טע"

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

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

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

בעיה שמינית – מספר חיבורים במקביל

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

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

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

כאשר אנו מבקשים ליצור חיבור TCP חדש, אנו חייבים לציין את מספר הפורט. כדי לפשט עניינים, קיימים מספרי פורטים סטנדרטיים עבור שירותים שונים, למשל פורט 80 משמש לתקשורת HTTP (אתרי אינטרנט), פורט 22 עבור SSH ועוד.

לסיכום

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

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

 

1 המספר הסידורי משקף למעשה כל בית (byte) של נתונים ולא כל חבילה. למשל, אם המספר הסידור של החבילה הוא 100, והיא מכילה 50 בתים, מספר החבילה הבאה יהיה 150.

מבני נתונים שכל מפתח חייב להכיר

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

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

רשימה (List)

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

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

מתי נעדיף רשימה על מערך? בעיקר אם הקוד שלנו מבצע הרבה הכנסות ומחיקות, או שאיננו יודעים מראש מה יהיה גודל הרשימה. במידה והקוד מבצע הרבה גישות למיקומים ספציפיים, נעדיף להשתמש במערך. בנוסף, לעתים קרובות הקוד שלנו מחולק לאזור שבונה את המערך / רשימה ואזור שמשתמש בו. שפות תכנות רבות מאפשרות המרה קלה מרשימה למערך ולהיפך, ניתן לנצל עובדה זאת כדי לבנות תחילה רשימה ע"י הוספת האיברים, ולאחר מכן להמיר אותה למערך ולבצע פעולות עליו. לדוגמה (C#):

int[] build_array() {
    List<int> list = new List<int>();
    // fill the list with values
    return list.ToArray();
}

מילון (Dictionary)

ללא ספק הזוכה הבלתי מעורער בתואר מבנה הנתונים האהוב עליי ביותר. מילון (לעתים נקרא גם Map או Associative Array) הינו אוסף של זוגות מפתח-ערך (key-value), ולרוב מאפשר ערך יחיד לכל מפתח. יתרונותיו העיקריים הינם הכנסה ושליפה יעילים:

d = dict()
d["hello"] = "world"
d["bye"] = "bye"
print d["hello"] // prints "world"
print "bye" in d // prints True
for key, value in d.iteritems():
    print key, "=>", value

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

מילון ממומש לרוב באמצעות טבלת גיבוב (Hash Table), ולכן המפתחות שלו הם מסוג Immutable (לא ניתנים לשינוי, ראו בהמשך), למשל מספרים או מחרוזות ולא מחלקות או רשימות. בנוסף יש שפות תכנות בהן הטיפוס של המפתחות והערכים הם קבועים ומוגדרים מראש (C#, Java, C++ ועוד).

בעוד שרוב שפות התכנות העיליות מספקות מימוש של מילון כחלק מהספרייה הסטנדרטית שלהן, לא כולן כאלו (C++ לדוגמה). מקרה מעניין הוא שפת Javascript, אשר לא מכילה מימוש של מילון במדוייק, אבל הטיפוס הבסיסי בה, Object, משמש בפועל כסוג של מילון שהמפתחות שלו הן מחרוזות:

var obj = {};
obj[1] = "value";
alert(obj["1"]); // "value"

קבוצה (Set)

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

Set<String> processed_names = new HashSet<String>();

for (String name : name_array) {
    if (!processed_names.contains(name)) {
        System.out.println(name);
    }
    processed_names.add(name);
}

דוגמה נוספת בשפת python היא מחיקת כפילויות מרשימה בשורה אחת:

list_without_duplicates = list(set(list_with_duplicates))

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

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

תור (Queue)

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

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

Immutables

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

  1. חישוב hash על מבנה הנתונים ושימוש כמפתח במילון או איבר בקבוצה1.
  2. ביצוע השוואה בזמן קבוע בין שני מופעים של מבנה הנתונים ע"י שימוש ב-hash.
  3. מניעת שינוי הערכים בטעות.
  4. חיסכון במשאבים ע"י שימוש חוזר במבני נתונים נעולים.

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

בחלק משפות התכנות קיימים מבני נתונים מקבילים לאלו שסקרנו, שההבדל היחיד ביניהם הוא שלא ניתן לשנות את הערכים שלהם לאחר היצירה הראשונית. למשל בשפת python, רשימה מסוג immutable נקראת tuple, וסט מסוג immutable נקרא frozenset. שפת Javascript לדוגמה לא מכילה אף מבנה נתונים כזה, אך קיימת ספרייה בשם Immutable.js המכילה מימושים של מבני נתונים רבים שכולם לא ניתנים לשינוי.

מבני נתונים נוספים

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

  • מערך ממויין – מערך שבו אנו מקפידים לשמור על האיברים ממויינים. יתרנו הוא בחיפוש יעיל (בינארי).
  • עץ – אוסף של איברים שכל אחד מהם מצביע לשניים או יותר "בנים". בדומה לגזע עץ ממנו מתפשטים ענפים.
  • מחסנית – דומה לתור, אך האיברים נדחפים (push) ונשלפים (pop) מאותו צד.
  • ערימה – מבנה יעיל להקצאת בלוקים קטנים של זיכרון בתוך בלוק גדול יותר.
  • Multimap – מילון המכיל רשימה של ערכים לכל מפתח.
  • מילון ממויין – מילון המשמר את סדר הכנסת המפתחות אליו.
  • חוצץ (Buffer) – מקטע זיכרון.

טבלה מסכמת

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

Java Python C++ Ruby Javascript C#
מערך Array array Array Array Array Array
רשימה LinkedList list* std::list Array* Array* List
מילון HashMap dict std::map Hash Object Dictionary
קבוצה HashSet set std::set Set HashSet
תור LinkedList / PriorityQueue Queue std::queue Queue Queue
מערך Immutable ImmutableList (Guava) tuple freeze(Array) Immutable.js ImmutableArray

* רשימה בשפת python ממומשת באמצעות מערך דינאמי. בשפות Ruby ו-Javascript ניתן להשתמש במערך, למרות שהוא איננו ממומש כרשימה.

סיכום

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

 

 

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

7 טעויות נפוצות של מפתחים צעירים – ואיך להימנע מהן

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

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

טעות #1 – לא לשאול מספיק שאלות

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

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

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

טעות #2 – להמציא את הגלגל

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

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

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

טעות #3 – לכתוב יותר מדי קוד בבת אחת

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

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

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

טעות #4 – לא להעתיק מאחרים

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

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

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

var sum = 0;
for (var i = 0; i < array.length; i++) {
    sum += array[i];
}

לעומת זאת, חיפוש פשוט בגוגל יראה שניתן לממש גם בשורה אחת:

var sum = array.reduce((a, b) => a + b, 0);

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

טעות #5 – להעתיק קוד בלי להבין אותו

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

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

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

טעות #6 – לעצור כשזה עובד

רבות דובר על definition of done, או במילים אחרות: "מתי מחליטים שמשהו גמור?". מפתחים צעירים נוטים להכריז "משימה הושלמה" מיד כאשר הקוד שלהם רץ בהצלחה בפעם הראשונה, ומדלגים על אחד השלבים החשובים ביותר בכתיבת קוד – בקרת האיכות.

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

  • האם מפתחים אחרים יבינו את הקוד שלי?
  • האם אני אבין את הקוד של עצמי בעוד מספר חודשים / ימים / שעות?
  • האם מחקתי חלקים מיותרים / זמניים / הערות?
  • האם טיפלתי בכל מקרי הקצה? האם הקוד שלי חסון (robust)?
  • האם הקוד מכיל הנחות סמויות? אם כן – האם הן מתועדות?
  • האם דרך המימוש היא סבירה מבחינת יעילות?
  • האם הבדיקות האוטומטיות מכסות מספיק מהקוד?

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

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

טעות #7 – לפחד מבאגים

מזל טוב, סיימתם לכתוב קטע קוד והגיע הזמן לשחרר אותו לעולם הגדול! אבל רגע… מה אם הקוד לא טוב מספיק? מה אם הוא מכיל באגים קריטיים שיביאו לסוף העולם? ומה אם…

עצרו!

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

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

ואם התגלה באג בשטח? לא קרה כלום – תקנו אותו, כתבו בדיקה המכסה אותו, והמשיכו הלאה.

מאבטחים את הבית בפחות מ-80 שורות קוד

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

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

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

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

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

אז בואו נעשה את זה!

החומרים הדרושים

את הקוד נכתוב, כאמור, בשפת python (גרסה 2.7) ונשתמש בספריות הבאות:

  • OpenCV – ספריית ראייה ממוחשבת (ולכידת וידאו).
  • scapy – ספריית רשת. נשתמש בה לבדיקה האם מכשיר מחובר לרשת הביתית.
  • pushbullet – לשליחת התרעות באמצעות השירות Pushbullet (ראו בהמשך).
  • numpy – ספריית מתמטיקה.
  • הספריות המובנות multiprocessing ו-datetime.

את ההתראות למכשיר הטלפון אנו נשלח באמצעות השירות Pushbullet, שהוא שירות חינמי המאפשר להעביר התראות בין מכשירים שונים. יש להירשם לשירות, ולהתקין את האפליקציה על המכשיר הנייד אליו תרצו לקבל את ההתראה. כנוסף, כדי שנוכל לשלוח התראות באמצעות ה-API של השירות, יש צורך לייצר Access Token. ניתן לעשות זאת במסך Settings באתר.

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

שלב ראשון – צפיה במצלמה

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

cap = cv2.VideoCapture(0)
frame_size = (int(cap.get(3)), int(cap.get(4)))

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

כעת נרוץ בלולאה ובכל איטרציה נבקש תמונה מהמצלמה ע"י הפונקציה read של VideoCapture:

while cap.isOpened():
    success, frame = cap.read()
    assert success, "failed reading frame"
    now = datetime.datetime.now()

שימו לב שפונקציית read מחזירה שני ערכים: הצלחה/כשלון ואת התמונה עצמה. כמו כן שימו לב לשורת ה-assert, שנועדה לוודא שהצלחנו לקבל תמונה. אם לא הצלחנו, יזרק exception והתוכנית תצא. השורה האחרונה שומרת את הזמן הנוכחי במשתנה now, לו נזדקק בהמשך.

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

while cap.isOpened():
    ...

    cv2.imshow('frame', frame)
    if cv2.waitKey(1) & 0xFF == ord('q'):
        break

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

לכידת תמונה ממצלמת הרשת
לכידת תמונה ממצלמת הרשת

שלב שני – זיהוי תנועה

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

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

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

def have_motion(frame1, frame2):
    delta = cv2.absdiff(frame1, frame2)
    thresh = cv2.threshold(delta, 25, 255, cv2.THRESH_BINARY)[1]
    return numpy.sum(thresh) > 0

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

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

כעת כל שנותר הוא להשתמש בפונקצייה have_motion בלולאה הראשית:

frame_gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
frame_gray = cv2.GaussianBlur(frame_gray, (21, 21), 0)

if have_motion(prev_frame, frame_gray):
    last_motion = now
    # TODO: start recording to a video file

prev_frame = frame_gray

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

שלב שלישי – שמירה לקובץ וידאו

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

motion_filename = now.strftime("%Y_%m_%d_%H_%M_%S_MOTION.avi")
motion_file = cv2.VideoWriter(motion_filename, fourcc, 20.0, frame_size)

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

      1. שם קובץ הפלט, אותו אנו בונים בשורות הראשונה והשנייה לפי הזמן הנוכחי (מהמשתנה now).
      2. אובייקט מסוג CV_FOURCC, המציין את הקידוד בו נרצה לשמור את הקובץ. חשוב לבחור את הקידוד כך שיתמך גם ע"י מערכת ההפעלה שלנו, וגם ע"י המכשיר הנייד אליו שולחים את הקובץ. עבורי הקידוד XVID עובד מצויין, אך יתכן שתזדקקו לקצת ניסוי וטעייה עם רשימת הקידודים הנמצאת באתר fourcc.org.
        fourcc = cv2.cv.CV_FOURCC(*"XVID")
      3. מספר פריימים לשניה.
      4. tuple המכיל את רוחב וגובה הפריים, אותו יצרנו מוקדם יותר.

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

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

if motion_file is not None:
    motion_file.write(frame)

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

if motion_file is not None:
    motion_file.write(frame)
    if now - last_motion > MOTION_RECORD_TIME:
        motion_file.release()
        motion_file = None
        # TODO: send video file

כאשר את הפרמטר MOTION_RECORD_TIME נגדיר בתחילת הקובץ, למשל ל-10 שניות:

MOTION_RECORD_TIME = datetime.timedelta(seconds = 10)

כעת למעשה סיימנו לכתוב תוכנית המזהה ומקליטה תנועה לקובץ וידאו!

שלב רביעי – בדיקה האם אני בבית

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

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

 find mac address <device name>

בנוסף נצטרך למצוא את כתובת ה-IP שלנו וה-subnet mask של הרשת הביתית שלנו, ע"י הרצת הפקודה ipconfig ב-command line של Windows (הוראות עבור מערכות הפעלה אחרות). את שני הנתונים האלו נמיר לטווח כתובות ה-IP של הרשת הביתית (בפורמט CIDR) ע"י שימוש בכלי הבא. זה אולי נשמע קצת מסובך, אבל לרוב כל שנצטרך לעשות הוא להחליף את המספר האחרון בכתובת ה-IP שלנו ב-0 ולהוסיף את המחרוזת /24.

נשמור את שני פריטי המידע הנ"ל במשתנים:

DEVICE_MAC = "3d:f9:c2:d8:0f:d5"
SUBNET = "192.168.1.0/24"

כעת נשתמש בספרייה scapy כדי לבצע סריקת ARP. שאילתת ARP היא הדרך המקובלת להמרת כתובת IP ברשת המקומית לכתובת MAC. אפשר לדמיין שאילתת ARP כצעקה "מיהו בעל כתובת ה-IP הזאת?", אליה עונה בעל הכתובת בלבד: "אני הבעלים של כתובת ה-IP, וה-MAC שלי הוא…".

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

def is_device_connected(mac_addr):
    answer, _ = scapy.srp(
        scapy.Ether(dst="ff:ff:ff:ff:ff:ff") /
        scapy.ARP(pdst=SUBNET), timeout=2)
    return mac_addr in (rcv.src for _, rcv in answer)

לאחר הרצת הפונקציה scapy.srp, המשתנה answer יכיל את מערך התשובות שהתקבלו לשאילתות ה-ARP. השורה השנייה בודקת האם כתובת ה-MAC שסופקה נמצאת בתוך אחת התשובות.

שלב חמישי ואחרון – שליחת קובץ הוידאו

כעת נוודא שאנחנו לא בבית, ונשלח לעצמנו התראה עם קובץ הוידאו באמצעות השירות Pushbullet:

def push_file(filename):
    if is_device_connected(DEVICE_MAC):
        print "Device is connected, not sending"
        return
    print "Sending", filename
    pushbullet = Pushbullet("PUSHBULLET_API_KEY")
    my_device = pushbullet.get_device("My Device")
    file_data = pushbullet.upload_file(open(filename, "rb"), filename)
    pushbullet.push_file(device = my_device, **file_data)

שימו לב להחליף את המחרוזות PUSHBULLET_API_KEY ו-My Device בערכים המתאימים מתוך חשבון ה-Pushbullet שלכם.

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

כדי שדבר כזה לא יקרה (חור אבטחה!) נרצה להריץ את תהליך השליחה במקביל ללולאה הראשית. ניתן לעשות זאת ע"י שימוש ב-threads, אך ב-python מומלץ להשתמש דווקא בתהליך נפרד. נעשה זאת ע"י שימוש במחלקה Process מתוך הספריה המובנית multiprocessing:

if now - last_motion > MOTION_RECORD_TIME:
    ...
    Process(target = push_file, args = (motion_filename, )).start()

סיימנו! וכך נראית ההודעה שמתקבלת במכשיר:

ההודעה שהתקבלה במכשיר הנייד
ההודעה שהתקבלה במכשיר הנייד

מה הלאה?

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

    1. שמירת כל הוידאו לדיסק, גם אם אין תנועה. אפשר באיכות נמוכה יותר כדי לחסוך מקום בדיסק.
    2. הגבלת גודל קובץ הוידאו הנשלח, למשל לדקה אחת.
    3. הזרמת הוידאו בלייב למכשיר הנייד.
    4. תמיכה במספר מצלמות / מכשירים ניידים במקביל.
    5. זיהוי המכשיר הנייד בדרכים אחרות.
    6. זיהוי פרצופים והתראה על פרצופים חשודים בלבד.

הקוד המלא

ניתן למצוא את הקוד המלא ב-GitHub של I, Code. אשמח אם תמשיכו לפתח את הפרוייקט, למצוא לי באגים, ולשלוח pull requests!

שדרגו את האתר שלכם עם פונטים בעברית

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

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

כדי להמחיש כמה משמעותי ההבדל, הנה כמה תמונות מסך מאתר allmovies.co.il, שההבדל היחיד ביניהן הוא הפונט:

שימוש בפונט ברירת המחדל של הדפדפן
שימוש בפונט ברירת המחדל של הדפדפן (Chrome)
שימוש בפונט הנפוץ אריאל
שימוש בפונט הנפוץ "אריאל"
שימוש בפונט החינמי אלף
שימוש בפונט החינמי "אלף"

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

מה חשוב כשבוחרים פונט?

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

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

    הנה קוד המאפשר לייצר את התמונה למעלה.

  2. מגיע במספר פורמטים. קיימים מספר סוגים נפוצים לקבצי פונט, כגון TTF, WOFF, SVG ועוד. חלקם נראים טוב יותר בדפדפנים מסויימים, חלקם שוקלים פחות, וחלקם נתמכים רק בדפדפנים חדשים. השתדלו לבחור גופן המגיע בכמה שיותר פורמטים, כך שייראה במיטבו על כל הדפדפנים הנפוצים.
  3. מאוחסן ב-CDN. שימוש בפונט המאוחסן ב-CDN (רשת דיוור תוכן), עשויה לחסוך את הורדת הפונט ע"י הדפדפן במידה והורד כבר בעבר. בנוסף, שימוש ב-CDN מאפשר הורדת הפונט במקביל לתוכן אחר באתר שלכם, ובכך האצת טעינת האתר וצמצום תופעת ה-FOUT.
  4. בעל איכות גבוהה וכמה שפחות פגמים. ניתן לוודא זאת ע"י הגדלת הפונט ומעבר על האותיות אחת אחת.

איפה מוצאים פונטים בעברית?

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

אך אם אתם כמוני – ואוהבים לבנות אתרים בעברית, אל דאגה! אספתי מספר פונטים חינמיים המתאימים לשימוש ב-web.

אלף

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

Open Sans בעברית

גופן Open Sans הינו נפוץ מאוד בשפות רבות. לאחרונה עוצבה הגרסה העברית שלו ע"י ינק יונטף, והיא מסופקת ע"י Google Fonts להורדה בחינם, במשקלים רבים.

אבל… הגופן המסופק ע"י גוגל לא מוצג בדפדפן אינטרנט אקספלורר! הפתרון המועדף עליי הוא להשתמש בגרסה הבאה שנוצרה מחדש ע"י אסף כץ.

Noto בעברית

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

גופנים נוספים

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

Redux – ארכיטקטורת Flux, אבל כמו שצריך

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

ארכיטקטורת Flux, שהתפרסמה גם היא ע"י פייסבוק ביחד עם React, לוקחת את הקונספט של MVC צעד אחד קדימה, ע"י הגדרת מקומות המרכזים state גלובאלי, אלו הם ה-Stores. כדי לשמור על זרימת נתונים ברורה וצפויה, שינויים למידע ב-stores לא מתבצעים ישירות, אלא ע"י יצירת אירועים הנקראים פעולות (Actions), עליהם מאזינים ה-stores ומבצעים שינויים במידע בהתאם. ה-Actions נוצרים לרוב בעקבות פעולת משתמש, לדוגמה לחיצה על כפתור. על כל אלו מנצח ה-Dispatcher שדואג שהפעולות ישוגרו בסדר הגיוני ולא בו זמנית. רכיבי ה-React עצמם מאזינים לשינויים ב-stores, ומעדכנים את ה-state של עצמם בהתאם.

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

חשוב לציין ש-Flux עצמה היא רק design pattern, ולא תשתית קוד. למעשה הקוד היחיד המסופק ע"י פייסבוק הוא ה-Dispatcher, כל השאר הן רק מוסכמות. ולמרות ש-Flux חדשנית ומשתלבת יפה עם React, היא עדיין מרגישה מעט בוסרית ולא חלקה כמו שהיינו מצפים. לדוגמה, בכל רכיב (Component) שצריך גישה למידע ב-stores, אנחנו צריכים להירשם לקבלת עדכונים, ולעדכן את ה-state בכל שינוי:

function getTodoState() {
    return { allTodos: TodoStore.getAll() };
}

var TodoApp = React.createClass({
    getInitialState: function() {
        return getTodoState();
    },
    componentDidMount: function() {
        TodoStore.addChangeListener(this._onChange);
    },
    componentWillUnmount: function() {
        TodoStore.removeChangeListener(this._onChange);
    },
    _onChange: function() {
        this.setState(getTodoState());
    }
};

כמה boilerplate! וזה עוד לפני שהתחלנו לממש את render… הדוגמה הזאת (שהיא אגב, דוגמה רשמית של Flux) גם מעלה שאלות שהתשובות עליהן לא פשוטות בכלל:

  1. מה עם רכיבים ילדים? האם לחלחל אליהם את ה-state ידנית או שגם הם יאזינו ל-store?
  2. מה קורה אם השינוי ב-store לא היה רלוונטי לרכיב? האם להתעלם ולרנדר? אולי לבדוק את השינוי? אולי PureRenderMixin?
  3. מה קורה אם יש שני stores? צריך להירשם לשניהם? או אולי לאחד אותם? ומה אם הם תלויים אחד בשני?
  4. איך בוחרים איזה מידע ישב ב-store ואיזה ב-state של רכיבי ה-React עצמם?

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

Redux להצלה

אז למרות ש-Flux הוא לא הדבר הכי נוח בעולם, העיקרון של state יחיד גלובאלי המשיך להתפתח בקהילת הקוד הפתוח, ובמהרה החלו לצוץ חלופות רבות כגון: ReFlux, Fluxible, Flummox, Fluxette (נשבע לכם שאני לא ממציא) ו-Alt. אך נראה שהמנצחת הגדולה בהתקוטטות הזאת היא ספריית Redux מאת Dan Abramov (נשמע ישראלי, אבל הוא לא).

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

  1. ה-store הוא יחיד, והוא מפוצל לשני חלקים: אובייקט state יחיד לכל האפליקציה, ופונקצייה טהורה אחת בשם Reduce המקבלת את אובייקט ה-state הנוכחי ו-action כלשהו, ומחזירה state חדש.
  2. ה-state היחיד הוא היררכי, וניתן להרכיב (לשלב) Reducers שונים כך שכל אחד יטפל בחלק אחר של ה-state. כך ניתן לפתח בנפרד חלקים שונים של האפליקציה.
  3. רכיבי React לא צריכים להכיל state בכלל. כל המידע שלהם צריך להיות מסופק בתור props מרכיב האבא ו/או מה-state הראשי.

שימו לב שהסעיף הראשון פותר בנקל את בעיית הרינדור בשרת, מכיוון שכעת ה-state הוא יחיד, גלובאלי, ואפשר לטעון אותו בתחילת כל בקשת HTTP ולשמור אותו חזרה בסופה, למשל בתור JSON.

בנוסף לשינוי בארכיטקטורה, הספריה מספקת מספר פונקציות בסיסיות, שביחד עם כמה מוסכמות, הופכות כל רכיב React לישות המורכבת (בגדול) מ-3 חלקים:

  1. פונקציית render, כמו שאנחנו כבר מכירים, שהיא לרוב פונקצייה טהורה, כלומר דטרמיניסטית ותלוייה אך ורק בקלט שלה ולא בשום מידע חיצוני.
  2. פונקציית mapStateToProps, שכשמה כן היא, מקבלת את ה-state הגלובאלי (ולעתים גם props מרכיב האבא) ומייצרת את ה-props הסופיים של הרכיב.
  3. אובייקט או פונקציה בשם mapDispatchToProps הממפה בין props של הרכיב ל-Action Creators, שהן פונקציות המחזירות אובייקט action אותו יש להעביר ל-reducer ובכך לשנות את ה-state.

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

ולמה זה טוב יותר?

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

יתרון נוסף של Redux הוא נוחות כתיבת בדיקות. מכיוון שה-Reducers הן פונקציות טהורות, הן צפויות לחלוטין ולכן קל מאוד לכתוב להן בדיקות יחידה המקבלות state ו-action, ומוודאות שה-state החדש הוא מה שציפינו. באופן זה אנו מפרידים לחלוטין את כל בדיקות ה-business logic מבדיקות ה-UI.

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

אוקיי, אני רוצה Redux, איך מתחילים?

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

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

רוצים ללמוד עוד? בבקשה:

לקריאה נוספת

יצירת תמונה מאימוג'י בפחות מ-50 שורות קוד

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

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

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

emoticon

התוכנית תייצר את התמונה הבאה (לחצו להגדלה):

emoticon.jpg.out

החומרים הדרושים

את הקוד נכתוב בשפת python, ונשתמש בספריות pillow (עיבוד תמונה) ו-numpy (מתמטיקה), וכמו כן בספרייה המובנית sys:

from PIL import Image
import numpy as np
import sys

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

emoticons3

שלב ראשון – טעינת האייקונים

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

ICON_SIZE = 20

ולאחר מכן נטען את קובץ התמונה ע"י שימוש בפונקציה Image.open של ספריית pillow.

emo_image = Image.open("emoticons.png")

לפני שנוכל לפרק את התמונה לאייקונים, אנחנו צריכים לברר כמה אייקונים יש בכל שורה ובכל עמודה, נעשה זאת ע"י שימוש במאפיין size של התמונה, שהוא tuple המכיל את רוחב התמונה וגובה התמונה, ונחלק אותו ב-ICON_SIZE (לדוגמה אם בשורה יש 80 פיקסלים ורוחב כל אייקון הוא 20 פיקסלים, אז מספר האייקונים הוא 4):

x_size, y_size = icons_image.size
x_icons = x_size / ICON_SIZE
y_icons = y_size / ICON_SIZE

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

icons = []
for row in xrange(y_icons):
    for col in xrange(x_icons):
        icons.append(crop_icon(icons_image, row, col))

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

icons = [
    crop_icon(icons_image, row, col)
    for col in range(x_icons) for row in range(y_icons)]

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

def crop_icon(img, row, col):
    return img.crop((
        col * ICON_SIZE,
        row * ICON_SIZE,
        (col + 1) * ICON_SIZE,
        (row + 1) * ICON_SIZE))

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

emoji1
שימו לב שמתחילים לספור מ-0

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

שלב שני – טעינת התמונה המקורית

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

img_filename = sys.argv[1]
img = Image.open(img_filename).convert('RGBA')
x_size, y_size = img.size

בדוגמה זו אנו מקבלים את שם התמונה משורת הפקודה ע"י שימוש ב-sys.argv, כמובן שניתן גם להשתמש בשם קבוע:

img_filename = "my_image.png"

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

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

x_size -= (x_size % ICON_SIZE)
y_size -= (y_size % ICON_SIZE)

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

שלב שלישי – מציאת האימוג'י המתאים ביותר

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

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

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

  1. מרחק מבוסס צבעים
  2. מרחק מבוסס טקסטורה
  3. מציאת וספירה של נקודות דומות (descriptors) בשתי התמונות
  4. מרחק אוקלידי פשוט (לתמונות חד מימדיות, למשל בגווני אפור בלבד)
  5. מרחק ספציפי לתחום מסויים (למשל פרצופים)
  6. שילוב של השיטות הנ"ל

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

על היסטוגרמות צבעים

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

אדום - 10 פיקסלים
כחול - 20 פיקסלים
ירוק - 7  פיקסלים

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

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

ב-python, כדי לחשב היסטוגרמה תלת-מימדית של הצבעים בתמונה נמיר אותה תחילה למערך ע"י הפונקציה getdata, ולאחר מכן נשתמש בפונקציה histogramdd של numpy:

def img_hist(img):
    arr = np.array(img.getdata(), np.uint8)
    return np.histogramdd(arr[:,:-1], bins = 6, range = [[0, 256]] * 3, weights = arr[:,3])[0]

הפרמטרים לפונקציה histogramdd הם (לפי הסדר):

  1. מערך דו מימדי עליו נרצה לחשב היסטוגרמה. המערך צריך להיות בגודל N*D כאשר N הוא מספר הנקודות בתמונה, ו-D הוא מספר המימדים (במקרה שלנו – 3). שימו לב שאנו מבצעים חיתוך של המערך, זאת כי המערך שהתקבל מ-getdata הוא בגודל N*4 (אדום, כחול, ירוק, ואלפא – פרמטר ה"שקיפות"). את אלפא אנחנו לא רוצים בהיסטוגרמה, כי הוא לא בדיוק חלק מהצבע, אבל נשתמש בו בהמשך.
  2. bins = 6 הוא מספר התאים שיהיו בהיסטוגרמה, לכל מימד. כלומר בהיסטוגרמה שלנו יהיו 6 בשלישית תאים, שהם 216 תאים המייצגים 216 טווחי צבעים. את הפרמטר בחרתי בצורה מושכלת – ערך נמוך מדי יתן תוצאות באיכות נמוכה, מכיוון שהוא יסווג צבעים שונים יחד. ערך גבוה מדי יצריך זמן ריצה גבוה יותר, ולא ישפר משמעותית את התוצאה. ניתן לשחק עם הפרמטר הזה ולראות מה קורה.
  3. range – טווח הצבעים המלא של התוצאה. חובה להגדיר פרמטר זה כדי להבטיח שכל ההיסטוגרמות תהיינה על אותם טווחים, אחרת לא תהיה משמעות להשוואה ביניהן.
  4. weights – זוכרים את הפרמטר אלפא? זהו בית אחד לכל פיקסל הקובע את רמת השקיפות שלו. פיקסל בעל פרמטר אלפא של 0 יהיה שקוף לגמרי ולמעשה אין משמעות לצבע שלו. מנגד, פיקסל עם אלפא 255 יהיה אטום לגמרי. כדי שלא נתחשב בפיקסלים שקופים בהיסטוגרמה שלנו, נעביר את מערך האלפא בפרמטר weights, הקובע את "המשקל" של כל פיקסל בהיסטוגרמה. כך ככל שפיקסל שקוף יותר, הוא ישפיע פחות על התוצאה הסופית, ופיקסלים שקופים לגמרי לא ייספרו כלל.

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

מרחק בין היסטוגרמות

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

def hist_distance(hist1, hist2):
    return np.linalg.norm(hist1 - hist2)

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

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

כעת כשאנחנו יודעים איך למדוד את המרחק בין חלק תמונה (region) לאייקון, כל שנותר הוא לחפש את האייקון בעל המרחק הקטן ביותר:

icon = min(icons, key = lambda icon: img_distance(icon, region))

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

icon_hists = map(img_hist, icons)

ופעם אחת עבור כל חלק בתמונה:

region_hist = img_hist(region)

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

icon = min(
    enumerate(icons),
    key = lambda icon: hist_distance(icon_hists[icon[0]], region_hist))[1]

שלב רביעי ואחרון – הרכבת התמונה המלאה

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

new_img = Image.new("RGB", (x_size, y_size), "white")

וכעת עבור כל חלק בתמונה המקורית, נמצא את האייקון המתאים ונדביק אותו במקום המתאים בתמונה החדשה:

new_img = Image.new("RGB", (x_size, y_size), "white")
for row in range(y_size / ICON_SIZE):
    for col in range(x_size / ICON_SIZE):
        region_hist = img_hist(crop_icon(img, row, col))
        icon = min(
            enumerate(icons),
            key = lambda icon: hist_distance(icon_hists[icon[0]], region_hist))[1]
     new_img.paste(icon, (col * ICON_SIZE, row * ICON_SIZE))

שימו לב לשימוש בפונקציה paste של התמונה, המקבלת חלק תמונה ומיקום, ו"מדביקה" את חלק התמונה במיקום המתאים בתמונה החדשה. כדי לשמר את הרקע הלבן בתמונה החדשה, ניתן לשנות את השורה האחרונה באופן הבא:

new_img.paste(icon, (col * ICON_SIZE, row * ICON_SIZE),
              mask = icon.split()[3])

כעת כל שנשאר הוא לשמור את התמונה החדשה:

new_img.save(img_filename + '.out.png')

וניתן אף להציג אותה:

new_img.show()

I, Code emoji

מה הלאה?

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

  1. שימוש בפונקציית מרחק שונה למציאת אייקונים
  2. שימוש באייקונים בגדלים שונים / לא ריבועיים
  3. הוספת progress bar למעקב אחרי התקדמות הקוד
  4. שיפור זמן הריצה של הקוד, למשל ע"י ביצוע cache להיסטוגרמות של חלקי תמונה זהים
  5. קבלת כל הפרמטרים משורת הפקודה, או לחלופין:
  6. עטיפת הקוד באתר אינטרנט פשוט כדי שיהיה נוח לשימוש

הקוד המלא

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