איך למיין מהר יותר בפרל?

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

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

מיון קבצים על פי שמותיהם

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

#!/usr/bin/perl
use strict;
use warnings;

my @files = glob "*.xml";

my @sorted_files = sort @files;

מיון קבצים על פי אורך השם

my @sorted_length = sort { length($a) <=> length($b) } @files;

ברשימה של 3000 קבצים המיון לקח פי 3 זמן ממיון ASCII על פי שמות, אך זה עדיין די מהיר.

מיון קבצים על פי גודל הקובץ

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

my @sort_size = sort { -s $a <=> -s $b } @files;

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

הגישה לדיסק היא הרבה יותר איטית מהגישה לזכרון וזה מסביר את האיטיות.

השאלה היא, האם אנחנו יכולים לשפר את זה?.

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

יש כל מיני אלגוריתמים למיון בעולם (Quicksort - מיון מהיר, Bubblesort - מיון בועות, Mergesort - ציון מיזוג, etc.) חלקם עשויים להיות מהירים יותר, חלקם איטיים יותר, בתלות בקלט, כלומר בנתונים שהם צריכים למיין. פרל השתמשה פעם ב- quicksort, אבל עברה ל-Mergesort כיום, אם אתם ממש רצים לקבוע את אלגוריתם המיון, ניתן לעשות זאת באמצעות הפרגמה sort .

בכל מקרה, לא משנה איזה אלגוריתם תבחרו, בממוצע יהיו לכם לפחות N*log(N) השוואות. כלומר עבור N = 1000 קבצים פרל תצטרך לגשת לדיסק 2 * 1000 * 3 = 6000 פעמים. (פעמיים עבור כל השוואה.) עבור כל קובץ פרל בודקת את גודל הקובץ 6 פעמים! זהו בזבוז אנרגיה אדיר.

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

איחזור מראש של גודל הקובץ

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

my @unsorted_pairs = map  { [$_, -s $_] } @files;
my @sorted_pairs   = sort { $a->[1] <=> $b->[1] } @unsorted_pairs;
my @quickly_sorted_files = map  { $_->[0] } @sorted_pairs;

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

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

בשלב השני אנחנו ממיינים את המערך של מצביעי המערכים הקטנים. בהשוואה בין כל שני מערכים קטנים אנחנו לוקחים את אלמנט [1] של כל אחד מהם ומשווים בין הערכים האלו. התוצאה היא מערך חדש של מצביעים על מערכים קטנים.

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

- טרנספורמציית שוורץ Schwartzian transform

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

my @quickly_sorted_files =
    map  { $_->[0] }
    sort { $a->[1] <=> $b->[1] }
    map  { [$_, -s $_] }
    @files;

צורת כתיבה זו נקראת Schwartzian transform טרנספורמציית שוורץ והיא נקראה כך על שם Randal L. Schwartz.

כשרואים אותה בקוד, קל מאוד לזהות אותה על פי המבנה map-sort-map.

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

my @sorted =
    map  { $_->[0] }
    sort { $a->[1] <=> $b->[1] }
    map  { [$_, f($_)] }
    @unsorted;

השימוש באלגוריתם זה למיון 3000 קבצי ה-XML הוא כעת "רק" פי 10 איטי יותר ממיון ASCII, כלומר פי 8 יותר מהיר מהקוד שאיתו התחלנו.

מסקנה

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

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

כדי לדעת מה נכון במקרה שלכם, השתמשו במודול Devel::NYTProf כדי ליצור פרופיל ריצה</של הקוד שלכםyour code.

(תודה ל- Smylers שעבר על המאמר.)