• בלוג
  • מה דעתכם, רובי או ++C?

מה דעתכם, רובי או ++C?

27/02/2017
C++

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

1. מה בונים

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

$ ruby pair_with_sum.rb 60 10 20 30 40 50 60 70 80
Found! 20 + 40 = 60

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

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

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

2. קוד רובי

הקוד בשפת רובי נראה כך:

def pair_with_sum(values, sum)
  pair_index = {}

  values.each_with_index do |item, index|
    pair = sum - item

    if pair_index.key?(item)
      return [index, pair_index[item]]      
    end

    pair_index[pair] = index
  end

  return
end

sum, *values = ARGV.map(&:to_i)

i1, i2 = pair_with_sum(values, sum)

unless i1.nil?
  puts "Found! #{values[i1]} + #{values[i2]} = #{sum}"
end

3. קוד ++C

אותה התוכנית ב C++ נראית כך:

#include <utility>
#include <experimental/optional>
#include <unordered_map>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
using namespace std::experimental;

template <typename T>
optional<pair<size_t, size_t>> pair_with_sum(vector<T> values, T sum)
{
  unordered_map<T, size_t> pair_index;
  for (auto index=0; index < values.size(); index++)
  {
    auto item = values[index];
    auto pair = sum - item;

    auto got  = pair_index.find(item);
    if (got != pair_index.end())
    {
      return make_pair<size_t, size_t>(index, (size_t)got->second);
    }

    pair_index[pair] = index;
  }
  return {};
}

int main(int argc, const char *argv[])
{
  vector<int> values(argc-2);
  transform(argv+2, argv+argc-1, values.begin(), [](auto arg) { return stoi(arg); });
  int sum = stoi(argv[1]);

  auto res = pair_with_sum(values, sum);
  if (res)
  {
    auto n1 = values[res->first];
    auto n2 = values[res->second];
    cout << "Found! " << n1 << " + " << n2 << " = " << sum << endl;
  }

  return 0;
}

4. הבדלים בולטים

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

קוד רובי מגדיר מילון באופן הבא:

pair_index = {}

אבל ב C++ בשביל אותו המילון נצטרך את השורה:

unordered_map<T, size_t> pair_index;

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

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

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

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

אז מה דעתכם? רובי או C++?