השוואת זמן בין Arrays.sort (Object) ו- Arrays.sort (int)

1. סקירה כללית

במדריך המהיר הזה, נשווה בין השניים Arrays.sort (אובייקט []) ו Arrays.sort (int []) פעולות מיון.

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

2. Arrays.sort (אובייקט [])

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

Arrays.sort (אובייקט []) מקבל סוגי התייחסות.

לדוגמא, יש לנו מערך של מספר שלם חפצים:

מספר שלם [] מספרים = {5, 22, 10, 0};

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

Arrays.sort (מספרים);

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

[0, 5, 10, 22]

Arrays.sort (אובייקט []) מבוסס על האלגוריתם של TimSort, נותן לנו מורכבות זמן של O (n יומן (n)). בקיצור, TimSort עושה שימוש במיון ההכנסה ובאלגוריתמי MergeSort. עם זאת, הוא עדיין איטי יותר בהשוואה לאלגוריתמי מיון אחרים כמו כמה מיישומי QuickSort.

3. Arrays.sort (int [])

מצד שני, Arrays.sort (int []) עובד עם פרימיטיבי int מערכים.

באופן דומה, אנו יכולים להגדיר int [] מגוון פרימיטיבים:

int [] פרימיטיבים = {5, 22, 10, 0};

ולמיין אותו עם יישום אחר של Arrays.sort (int []). הפעם, קבלת מגוון פרימיטיבים:

Arrays.sort (פרימיטיבי);

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

[0, 5, 10, 22]

מתחת למכסה המנוע, הוא משתמש באלגוריתם Quicksort כפול-ציר. היישום הפנימי שלה מ- JDK 10 הוא בדרך כלל מהיר יותר מה- Quicksort המסורתי בעל ציר אחד.

אלגוריתם זה מציע O (n יומן (n)) מְמוּצָע מורכבות זמן. זהו זמן מיון ממוצע נהדר עבור אוספים רבים. יתר על כן, יש לו את היתרון שהוא לגמרי במקום, כך שהוא לא דורש שום אחסון נוסף.

אם כי, במקרה הגרוע, מורכבות הזמן שלו היא O (n2).

4. השוואת זמן

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

4.1. ניתוח איכותי

Arrays.sort (אובייקט []) בדרך כלל איטי יותר בהשוואה ל- Arrays.sort (int []) מכמה סיבות שונות.

הראשון הוא האלגוריתמים השונים. QuickSort לרוב מהיר יותר מ- Timsort.

שנית היא כיצד כל שיטה משווה את הערכים.

לִרְאוֹת, מאז Arrays.sort (אובייקט []) צריך להשוות אובייקט אחד מול אחר, הוא צריך לקרוא לכל אלמנט בהשוואה ל שיטה. לכל הפחות, זה דורש בדיקת שיטה ודחיפת שיחה אל הערימה בנוסף לכל פעולת ההשוואה שבאמת תהיה.

מצד שני, Arrays.sort (int []) יכול פשוט להשתמש במפעילי יחס פרימיטיביים כמו < ו >, שהם הוראות קידוד יחיד.

4.2. פרמטרים של JMH

לבסוף, בואו נגלה איזו שיטת מיון פועלת מהר יותר עם נתונים בפועל. לשם כך, נשתמש בכלי JMH (Java Microbenchmark Harness) כדי לכתוב את מבחני הביצועים שלנו.

אז אנחנו רק הולכים לעשות כאן אמת מידה מאוד פשוטה. זה לא מקיף אבל ייתן לנו מושג כיצד אנו יכולים להתקרב משווה Arrays.sort (int []) ו Arrays.sort (מספר שלם[]) שיטות מיון.

בשיעור הבדיקה שלנו נשתמש בהערות תצורה:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MILLISECONDS) @Measurement (batchSize = 100000, iterations = 10) @Warmup (batchSize = 100000, iterations = 10) ArraySortBenchmark בכיתה ציבורית {}

כאן אנו רוצים למדוד את הזמן הממוצע לפעולה אחת (Mode.AverageTime) ולהציג את התוצאות שלנו באלפיות השנייה (TimeUnit.MILLISECONDS). יתר על כן, עם batchSize פרמטר, אנו אומרים ל- JMH לבצע 100,000 איטרציות כדי לוודא שהתוצאות שלנו כוללות דיוק גבוה.

4.3. מבחני מידוד

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

@State (Scope.Thread) מחלקה סטטית ציבורית אתחול {שלם [] מספרים = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922999, 1215, 75160 -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; int [] ראשוניים = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 209485659, -1061486548, 562424208, -1233745158, 41308167}; }

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

כעת אנו מוכנים להוסיף את המיקרו-מידוד הראשון עבור Arrays.sort (מספר שלם []):

@Benchmark שלם ציבורי [] benchmarkArraysIntegerSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.numbers); מצב החזרה. מספרים; }

הבא, בשביל Arrays.sort (int []):

@Benchmark public int [] benchmarkArraysIntSort (ArraySortBenchmark.Initialize state) {Arrays.sort (state.primitives); מדינת החזרה. פרימיטיבים; }

4.4. תוצאות מבחן

לבסוף, אנו מבצעים את הבדיקות ומשווים את התוצאות:

שוויון שגיאה במצב ציון Cnt יחידות מידוד ArraysIntSort avgt 10 1.095 ± 0.022 ms / op benchmark ArraysIntegerSort avgt 10 3.858 ± 0.060 ms / op

מהתוצאות אנו יכולים לראות זאת Arrays.sort (int []) השיטה מבוצעת טוב יותר מאשר ל Arrays.sort (אובייקט [])במבחן שלנו, ככל הנראה מהסיבות הקודמות שזיהינו.

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

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

4.5. למה טימסורט אז?

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

לִרְאוֹת, QuickSort לא יַצִיבאז אנחנו לא יכולים להשתמש בזה למיון חפצים. בעיקרון, אם שניים ints זהים, זה לא משנה שהסדר היחסי שלהם נשאר זהה מאז אחד 2 אינו שונה מאחר 2. עם אובייקטים, אנו יכולים למיין לפי מאפיין אחד ואז אחר, מה שהופך את סדר ההתחלה לחשוב.

5. מסקנה

במאמר זה, השווינו שתי שיטות מיון זמינות ב- Java: Arrays.sort (int []) ו Arrays.sort (מספר שלם[]). בנוסף, דנו באלגוריתמי המיון המשמשים ביישומיהם.

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

כרגיל, הקוד השלם למאמר זה זמין באתר GitHub.


$config[zx-auto] not found$config[zx-overlay] not found