טרנספורמציות של סדרות

03/12/2018

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

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

numbers = (0..Float::INFINITY)

זאת סידרת המספרים 0,1,2,3,4,5,6 וכן הלאה עד אין סוף. אנחנו יודעים שאם נכפיל כל איבר בסידרה ב-2 נקבל את הסידרה 0,2,4,6,8,10,12 כלומר כל המספרים הזוגיים - ואנחנו יכולים להשתמש ב map כדי לעשות את זה ב Ruby:

even = (0..Float::INFINITY).lazy.map {|i| i * 2}

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

puts (0..Float::INFINITY).lazy.map {|i| i * 2}.first(10)

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

boy
girl
helllo
good
boxer

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

["boy", {1=>["b", "o", "y"]}]
["girl", {1=>["g", "i", "r", "l"]}]
["helllo", {1=>["h", "e", "o"], 3=>["l", "l", "l"]}]
["good", {1=>["g", "d"], 2=>["o", "o"]}]
["boxer", {1=>["b", "o", "x", "e", "r"]}]

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

["helllo", {1=>["h", "e", "o"], 3=>["l", "l", "l"]}]
["good", {1=>["g", "d"], 2=>["o", "o"]}]
["boxer", {1=>["b", "o", "x", "e", "r"]}]
["boy", {1=>["b", "o", "y"]}]
["girl", {1=>["g", "i", "r", "l"]}]

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

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

class String
  def count
    Hash.new(0).tap { |h| self.each_char { |word| h[word] += 1 } }
  end

  def icount
    counts = self.count
    each_char.group_by {|c| counts[c]}
  end
end

words = [
  'boy',
  'girl',
  'helllo',
  'good',
  'boxer',
]

puts words
  .map {|w| [w, w.icount]}
  .sort {|a, b| a[1].keys.max - b[1].keys.max}
  .reverse
  .map {|p| p[0]}
  .first

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