שטויות הזויות – או למה לימנים אסור להשתמש בקוד פתוח

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

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

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

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

Ars Technica כתבו על הנזקים שחוסמי הפרסומות גורמים

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

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

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

HipHop לPHP, המחשבות שלי בנושא

צריך היה להיות ממתכנת מנותק מאוד בשביל לא לקרוא על הHipHop, כלי ששיחררה Facebook שלוקח קוד PHP בגירסה 5.2 פחות כמה פיצ'רים, וממיר אותו לקוד C++ שאפשר לקמפל באמצעות g++ לקוד מכונה שרץ באופן טבעי על השרת. Facebook טוענים שHipHop מסוגל להביא לביצועים טובים בכ50%, שהוא כשלעצמו מספר מרשים מאוד מחד, ומפתה מאוד בחשיבה על צריכת הCPU שיורדת משמעותית מאידך.

מה זה למעשה?

• HipHop ממיר קוד PHP לקוד C++ שיכול להתקמפל לקוד מכונה טבעי. HipHop תומך ברוב מוחץ של האפשרויות בPHP 5.2 מלבד פונקציות כמו eval() למשל.
• הכלי מתיימר ליצור את קוד הC++ היעיל ביותר האפשרי, הוא יבדוק מגמות כלליות ודברים שעשיתם בקוד הPHP שלכם ולפיו יכין את קוד הC++ המותאם ביותר.
• לאחר שקומפל, HipHop מהווה בעצמו את שרת הרשת. הוא איננו צריך תוכנות שרת כמו Apache ואחרות.
• כרגע, HipHop לא תומך בכלל בווינדוס. מפתחי PHP, אם עוד לא עברתם, זה הזמן לנסות את לינוקס.
• כרגע אתר Facebook כולו משתמש בכלי הזה לייעול הקוד ולהתמודדות עם עומס המשתמשים.

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

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

HipHop הוא בהחלט כלי מרשים, אבל לפני שרצים להשתמש בו חייבים לקחת בחשבון את ה"עלות-תועלת" פה. האם האתר שלך באמת צריך ייעול דרסטי בשימוש בכוחות החישוב שלו? או שמה שהוא עושה בעיקר זה להציג דפים שלא מתעדכנים לעיתים קרובות מאוד (כמו בפייסבוק) ומתמקד בעיקר בשליפת נתונים ממסד והצגתם, נניח בלוג, פורום וכו' וכו'. ללמוד להשתמש בכלי כזה, ולהתחיל להתעסק עם C++ והדיבגר של g++ יכול להיות סיוט לא קטן למתכנת ווב. תחשבו על זה.

עוד מילה על CppCMS

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

למה שימוש בAdBlock זה לא ממש מוסרי

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

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

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

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

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

מבני נתונים בתכנות – חלק א', מערך ורשימה מקושרת

הקדמה

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

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

מערך -Array

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

אז מהוא למעשה מערך? ברשותכם אשתמש בתמונה להמחשה הלקוחה מהmanual הרשמי לJAVA:

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

מיון מערך

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

מחיקת ערכים וחיפוש

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

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

מערכים רב ממדיים

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

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

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

רשימה מקושרת -Linked List

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

פה אני אסקור את מבנה הנתונים שפותר כמה מהבעיות האלו, הרשימה המקושרת, Linked List. הרשימה המקושרת היא ככל הנראה מבנה הנתונים השני בשכיחותו אחרי המערך. הרשימה המקושרת היא מבנה נתונים מבוסס מצביעים, או כפי שבשפות ללא מצביעים (C# או JAVA למשל) אוהבים לקרוא לזה, הפניות. כל עצם ברשימה כולל שני נתונים, את הinfo, כלומר המידע שיש לאותו איבר, שיכול להיות מכל סוג, מספר שלם, מחרוזת או עצם שיצרתם בעצמכם, והנתון השני הוא המצביע או ההפניה לבאיבר הבא בתור. כל איבר כזה ברשימה מכונה בדר"כ Node, כאשר למעשה הרשימה עצמה מהווה בסה"כ מצביע לNode הראשון ברשימה, ומשם זה כבר ממשיך לבד. הרשימה מסתיימת בכך שההפניה לאיבר הבא בעצם האחרון בעצם מפנה לnull. התרשים הבא מסביר את הכוונה היטב:

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

סוגי רשימות נוספים

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

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

הוספה והסרה של איברים ברשימה

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

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

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

מיון וחיפוש

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

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

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

לסיכום יתרונות וחסרונות רשימה מקושרת

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

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

סוף חלק א'

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

גוגל נגד IE6, למה זה טוב ובעיקר למה זה רע

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

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

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

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

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

למה לינוקס היא המערכת היחידה שאיתה אפשר להתמודד מול iPad

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

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

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

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

אבל… מה עם אנדרואיד?

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

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

אנחנו אוהבים את החופש שלנו – למה המכירות של ספרי O'Reilly השתפרו ב104%

לפני 18 חודשים החליטה חברת ההוצאה לאור הגדולה בעולם לספרי טכנולוגיה, O'Reilly להפסיק את השימוש בDRM בספרים האלקטרוניים שלה. מאז ההחלטה הזאת השתפרו המכירות של הספרים האלקטרוניים בO'Reilly ב104%! נתון מפתיע מאוד, במיוחד לאור טענות המגננה של המצדדים בDRM באותה תקופה ש"מדובר בספרי טכנולוגיה והמשתמשים בהם הם טכנולגים, להם יותר מלמשתמש הרגיל יהיה קל להפיץ עותקים של הספרים ברשת להורדות פירטיות.". למען האמת, אני מניח שזו הייתה יכולה להיות ההנחה המיידית של כל אחד כשהיה שומע על זה.

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

האם גוגל צריכה לפחד מ2011? או 2017?

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

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

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

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

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

איך גוגל היכתה את מוזילה עם התמיכה בHTML5 ביוטיוב

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

התמיכה בHTML5 ביוטיוב נעשית עם קודק הוידאו H.264/AVC, הקודק נתמך בכרום ובספארי ובIE עם chrome frame, אך לא בפיירפוקס, שכן מוזילה החליטה ללכת על התקן הפתוח OGG.

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

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

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