מיון

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

עמוד העזר עבור sort מגדיר את האופרטור, את חוזה המשווה, ואת מכניקת ה־$a/$b. פרק זה מניח שאתה מכיר אותם ומתמקד במהירות.

המשווה הוא העלות

sort עצמו הוא mergesort יציב - מהיר, ולא משהו שתוכל לשפר מתוך Perl. מה שאתה שולט בו הוא כמה עבודה מתרחשת בתוך כל השוואה. שתי עובדות קובעות את התקציב:

• המשווה רץ O(n log n) פעמים. עבור רשימה בת 100,000 איברים זה הרבה מעל מיליון קריאות.

• ב־pperl, בלוק המשווה הוא callback, ו־callback־ים רצים על המפרש. ה־JIT מהדר לולאות, לא גופי משווה של sort (ראה הידור JIT), כך שאינך יכול להסתמך על ה־JIT שיחלץ משווה יקר כפי שהוא חולץ לולאה מספרית. עלות המשווה משולמת במלואה, בכל קריאה.

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

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

הטרנספורם השוורצי

כאשר מפתח המיון יקר לגזירה מכל איבר - חילוץ תת־מחרוזת, חיפוש שדה, אורך, חישוב - המיון הנאיבי מחשב אותו מחדש בכל השוואה:

# Slow: the key (-M $_) is computed twice per comparison, O(n log n) times.
my @sorted = sort { -M $a <=> -M $b } @files;

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

my @sorted =
    map  { $_->[1] }                      # 3. strip the key, keep the element
    sort { $a->[0] <=> $b->[0] }          # 2. sort on the precomputed key
    map  { [ -M $_, $_ ] }                # 1. compute the key once per element
    @files;

קרא זאת מלמטה למעלה: ה־map התחתון בונה זוג [key, element] עבור כל איבר (n חישובי מפתח), ה־sort משווה רק את ה־$_->[0] הזול שחושב מראש (ללא חישוב מפתח במשווה), וה־map העליון זורק את המפתח. המפתח היקר מחושב n פעמים במקום O(n log n) פעמים.

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

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

הטרנספורם של Guttman-Rosler

הטרנספורם השוורצי ממיין arrayref־ים, מה שעולה הקצאת arrayref ודה־הפניה לכל השוואה. כאשר ניתן לקודד את המפתח כתחילית מחרוזת ברוחב קבוע, הטרנספורם של Guttman-Rosler (GRT) הולך רחוק יותר: הוא אורז את המפתח ואת האיבר למחרוזת אחת, ממיין את המחרוזות הללו עם sort המחרוזתי ברירת המחדל (ללא בלוק משווה כלל), ואז מקלף את התחילית.

my @sorted =
    map  { substr($_, 8) }                          # 3. strip the 8-char key prefix
    sort                                            # 2. plain string sort, no comparator
    map  { pack('N', $_->{priority}) . $_->{name} } # 1. fixed-width key + payload
    @records;

לרווח שני חלקים. ראשית, המפתח מחושב מראש פעם אחת, כמו בשוורצי. שנית - וזהו היתרון הייחודי של GRT - ל־sort אין בלוק משווה, כך שאין כלל callback לכל השוואה. sort מחרוזתי ברירת המחדל משווה את המחרוזות הארוזות ישירות, מה שמונע את עלות ה־callback כליל. הסרת ה־callback של המשווה חשובה יותר ב־pperl דווקא משום שאותו callback היה רץ על המפרש.

העלות של GRT היא שהמפתח חייב להיות ניתן לקידוד כך שהשוואת מחרוזת בייט־אחר־בייט תפיק את הסדר הרצוי לך:

• שלמים חייבים להיות ארוזים big-endian (pack 'N' / pack 'Q>') כך שסדר הבייטים יתאים לסדר המספרי, ולהיות מוסטים כדי להיות אי־שליליים (להשוואת מחרוזת אין סיבית סימן).

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

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

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

משווים זולים יותר ללא טרנספורם

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

• השווה מספרים עם <=>, מחרוזות עם cmp. שימוש ב־cmp על מספרים ממיר את שני הצדדים למחרוזת בכל השוואה; שימוש ב־<=> על מחרוזות הוא מלכודת המרה למספר. התאם את האופרטור לנתונים.

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

  sort { $a->{rank} <=> $b->{rank}        # cheap, decides most pairs
      || $a->{name} cmp $b->{name} }      # only when ranks tie
         @rows;
  

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

סדר ההחלטה

1. פרופֵל. אם מדידה אינה ממקמת את הזמן במיון, הנח לו.

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

3. אם המיון עדיין חם והמפתח הוא שלם חסר־סימן או מחרוזת, שקול את הטרנספורם של Guttman-Rosler כדי לבטל את ה־callback של המשווה כליל.

4. מדוד מחדש לאחר כל שינוי.

ראו גם

• sort - עזר האופרטור: חוזה המשווה, $a/$b, יציבות.

• map - מחצית הטרנספורם של הצורות השוורצית וגם של Guttman-Rosler.

• reverse - מיונים יורדים ללא היפוך המשווה.

• מדידה - ודא שהמשווה הוא העלות לפני שמתמירים אותו.

• הידור JIT - מדוע בלוק משווה של sort אינו עובר הידור JIT, כך שעלותו משולמת במלואה.