מכפלה קרטזית בכמה שפות.

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

על מכפלה קרטזית

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

התרגיל היה בScala אך בעקבות דיון בקבוצת הוואטסאפ DDOS הגעתי להצעות בכמה שפות,
אשתף:

Scala

קוד סקלה ליצירת מכפלה קרטזית


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


Python


הקוד בפייתון ללא ספק ארוך יותר וקריא פחות, ראשית יוצרים מערך של מערכים, המכיל את המערך המקורי משוכפל שוב ושוב, ואב יוצרים מערך של מערכים המכיל את המערך המקורי כולו, משוכפל שוב ושוב, ואז משדכים אותך עם ZIP ואז עם MAP משדכים כל איבר לזוג זוג של אברים… ולבסוף עם SUM משטחים הכל למערך חדש.
כמה דברים מפריעים לי בקוד הזה, ראשית הוא ארוך ולא ממש אינטואיטיבי, שנית, בשורה 5 אנו נאלצים להמיר את הZIP לליסט, ובכך "להפעיל" את הZIP על כל האברים.
בלי זה נקבל שגיאה. אך זה מונע ייצור "עצל" של הזוגות ויהווה בעיה עבור מערך ארוך מאד.
ואחרון חביב, אני בעצם לא רוצה Set אלא List אבל נאלץ להשתמש בו כדי למנוע כפילות… אם בהמשך ארצה להשתמש בו כמערך, אצטרך להמיר לList. אולי מראש כדאי אפילו לעשות כן בעת ההחזרה מהפונקציה, ומ"מ זה מוסיף תקורה.


JavaScript

הקוד באדיבות אלעד הלר

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



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

אבל במסגרת תחרות זו "עם ידיים קשורות מאחורי הגב" לדעתי JS ניצחה…

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


תוספת על פי תגובות ידידיי הי"ו:
החכימני ידידי ר' דוד כץ, שיש לכך בפייתון פונקציה מובנית בספריה Itertools:

https://docs.python.org/3/library/itertools.html#itertools.product
אם נביא אותה בחשבון, פייתון כמובן מנצחת… אך מצד שני, "מה החכמה" כאן, הרי אחרי שכתבתי פונקציה, תמיד לקרוא לה זה מילה אחת… וכאן מאחורי הקלעים יש קוד הכולל לולאות… ובפועל הוא אפילו ארוך יותר ובC.
המקור כאן
About author
eliezer
בלוג תכנות כאן: code-review.blog

תגובות

יפה,

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

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

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

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

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

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

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

המספרים של פרוג:

337,452

משתמשים נכנסו לפרוג בחודש האחרון

583

משתמשים מבקרים ברגע זה באתר

4,986

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

לוח נדל"ן | למכירה והשכרה

לוח מודעות | קניה מכירה

לוח דרושים

Article information

נכתב ע"י
eliezer
צפיות
365
תגובות
6
Last update

More in הדרכות בנושאי מחשב ותוכנה

למעלה