ביצועים ושפות מודרניות

20/11/2022

אלגוריתם Fisher-Yates לערבוב מערך מציע לבצע את הצעדים הבאים:

  1. בחרו אינדקס אקראי במערך.
  2. מחקו את האיבר באינדקס שבחרתם וכתבו אותו בסוף הרשימה.
  3. המשיכו עד שמחקתם את כל האיברים.

זה אלגוריתם אלגנטי וקל למימוש בכל שפה, לדוגמה ב JavaScript:

function shuffle(arr) {
  let end = arr.length;
  while (end >= 0) {
    const nextIndex = Math.floor(Math.random() * end);
    arr.push(arr[nextIndex]);
    arr.splice(nextIndex, 1);
    end -= 1;
  }
  return arr;
}

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

function shuffle(arr) {
  for (let i=arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * i);
    const item = arr[i];
    arr[i] = arr[j];
    arr[j] = item;
  }

  return arr;
}

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