streamalism.org

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

מאמר זה ימחיש כיצד ניתן להחיל מיון מַעֲרָך, רשימה, מַעֲרֶכֶת ו מַפָּה בג'אווה 7 ובג'אווה 8.

2. מיון עם מַעֲרָך

נתחיל על ידי מיון מערכים שלמים באמצעות Arrays.sort () שיטה.

נגדיר את הדברים הבאים int מערכים ב @לפני שיטת jUnit:

@ לפני initVariables () בטל פומבי () {toSort = new int [] {5, 1, 89, 255, 7, 88, 200, 123, 66}; sortedInts = int int [] {1, 5, 7, 66, 88, 89, 123, 200, 255}; sortedRangeInts = int int [] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ...}

2.1. מיון מערך שלם

הבה נשתמש בפשטות Array.sort () ממשק API:

@ מבט פומבי בטל givenIntArray_whenUsingSort_thenSortedArray () {Arrays.sort (toSort); assertTrue (Arrays.equals (toSort, sortedInts)); }

המערך הלא ממוין ממוין כעת לחלוטין:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

כאמור ב- JavaDoc הרשמי, Arrays.sort משתמש ב- Quicksort עם ציר כפול פרימיטיבים. הוא מציע ביצועי O (n יומן (n)) והוא בדרך כלל מהיר יותר מיישומי Quicksort מסורתיים (ציר אחד). עם זאת, היא משתמשת ביישום יציב, מסתגל, איטרטיבי, של אלגוריתם mergesort עבור מַעֲרָך של אובייקטים.

2.2. מיון חלק ממערך

Arrays.sort יש עוד אחד סוג ממשקי API - עליהם נדבר כאן:

Arrays.sort (int [] a, int fromIndex, int toIndex)

זה ימיין רק חלק מהמערך, בין שני המדדים.

בואו נסתכל על דוגמה מהירה:

@ מבחן הריק ציבורי givenIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (Arrays.equals (toSort, sortedRangeInts)); }

המיון יתבצע רק על אלמנטים הבאים של מערך המשנה (toIndex יהיה בלעדי):

[255, 7, 88, 200]

מערך המשנה הממוין וכתוצאה מכך כולל המערך הראשי יהיה:

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3. ג'אווה 8 Arrays.sort לעומת Arrays.parallelSort

Java 8 מגיע עם ממשק API חדש - parallelSort - עם חתימה דומה ל- Arrays.sort () ממשק API:

@Test הציבור בטל givenIntArray_whenUsingParallelSort_thenArraySorted () {Arrays.parallelSort (toSort); assertTrue (Arrays.equals (toSort, sortedInts)); }

מאחורי הקלעים של parallelSort (), הוא מפרק את המערך למערכי משנה שונים (לפי גרעיניות באלגוריתם של parallelSort). כל תת-מערך ממוינת לפי Arrays.sort () בחוטים שונים כך ש סוג ניתן לבצע באופן מקביל וממוזגים לבסוף כמערך ממוין.

שים לב שהמאגר המשותף של ForJoin משמש לביצוע משימות מקבילות אלה ואז למיזוג התוצאות.

התוצאה של Arrays.parallelSort הולך להיות זהה ל Array.sort כמובן, זה רק עניין של מינוף רב-הברגה.

לבסוף, ישנן גרסאות דומות של API Arrays.sort ב Arrays.parallelSort גם כן:

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

3. מיון א רשימה

בוא נשתמש כעת ב Collections.sort () ממשק API java.utils.Collections - למיין א רשימה שלמים שלמים:

@Test ציבורי בטל givenList_whenUsingSort_thenSortedList () {רשימה toSortList = Ints.asList (toSort); Collections.sort (toSortList); assertTrue (Arrays.equals (toSortList.toArray (), ArrayUtils.toObject (sortedInts))); }

ה רשימה לפני המיון יכלול האלמנטים הבאים:

[5, 1, 89, 255, 7, 88, 200, 123, 66]

ובאופן טבעי, לאחר המיון:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

כאמור ב- Oracle JavaDoc עבור אוספים, הוא משתמש במיזוג מיזוגים שונה ומציע מובטח יומן n (n) ביצועים.

4. מיון א מַעֲרֶכֶת

הבא, בואו נשתמש Collections.sort () למיין א LinkedHashSet.

אנו משתמשים ב- LinkedHashSet כי זה שומר על צו הכניסה.

שימו לב כיצד, על מנת להשתמש ב- סוג ממשק API אוספים – אנו עוטפים לראשונה את הסט ברשימה:

@Test ציבורי בטל givenSet_whenUsingSort_thenSortedSet () {Set integersSet = new LinkedHashSet (Ints.asList (toSort)); הגדר descSortedIntegersSet = חדש LinkedHashSet (Arrays.asList (מספר שלם חדש [] {255, 200, 123, 89, 88, 66, 7, 5, 1})); רשימת רשימה = ArrayList חדש (מספרים שלמים); Collections.sort (Comparator.reverseOrder ()); integersSet = חדש LinkedHashSet (רשימה); assertTrue (Arrays.equals (integersSet.toArray (), descSortedIntegersSet.toArray ())); }

ה Comparator.reverseOrder () השיטה הופכת את הסדר שמטיל הסדר הטבעי.

5. מיון מַפָּה

בחלק זה נתחיל להסתכל על מיון מפה - הן לפי מקשים והן לפי ערכים.

בואו נגדיר תחילה את המפה שנמיין:

@ לפני initVariables בטל פומבי () {.... מפת HashMap = HashMap חדש (); map.put (55, "ג'ון"); map.put (22, "אפל"); map.put (66, "ארל"); map.put (77, "פנינה"); map.put (12, "ג'ורג '"); map.put (6, "רוקי"); ....}

5.1. מִיוּן מַפָּה מאת מפתחות

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

@Test הציבור בטל givenMap_whenSortingByKeys_thenSortedMap () {Integer [] sortedKeys = Integer [[{6, 12, 22, 55, 66, 77}; רשימה ערכים = ArrayList חדש (map.entrySet ()); Collections.sort (ערכים, משווה חדש() {@Override int int השווה (כניסה o1, כניסה o2) {החזר o1.getKey (). CompareTo (o2.getKey ()); }}); מפה sortedMap = חדש LinkedHashMap (); עבור (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.keySet (). toArray (), sortedKeys)); }

שים לב כיצד השתמשנו ב- LinkedHashMap תוך העתקת הממוינים ערכים מבוסס על מפתחות (כי HashSet אינו מתחייב לסדר המפתחות).

ה מַפָּה לפני המיון:

[מפתח: 66, ערך: ארל] [מפתח: 22, ערך: אפל] [מפתח: 6, ערך: רוקי] [מפתח: 55, ערך: ג'ון] [מפתח: 12, ערך: ג'ורג '] [מפתח: 77, ערך: פנינה]

ה מַפָּה לאחר המיון לפי מפתחות:

[מפתח: 6, ערך: רוקי] [מפתח: 12, ערך: ג'ורג '] [מפתח: 22, ערך: Apple] [מפתח: 55, ערך: ג'ון] [מפתח: 66, ערך: Earl] [מפתח: 77, ערך: פנינה] 

5.2. מִיוּן מַפָּה לפי ערכים

כאן נשווה ערכים של מפת גיבוב רשומות למיון על בסיס ערכים של מפת גיבוב:

@ מבחן בטל ציבורי givenMap_whenSortingByValues_thenSortedMap () {String [] sortedValues ​​= String new [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; רשימה ערכים = ArrayList חדש (map.entrySet ()); Collections.sort (ערכים, משווה חדש() {@Override public int השווה (כניסה o1, כניסה o2) {החזר o1.getValue (). CompareTo (o2.getValue ()); }}); מפה sortedMap = חדש LinkedHashMap (); עבור (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.values ​​(). toArray (), sortedValues)); }

ה מַפָּה לפני המיון:

[מפתח: 66, ערך: ארל] [מפתח: 22, ערך: אפל] [מפתח: 6, ערך: רוקי] [מפתח: 55, ערך: ג'ון] [מפתח: 12, ערך: ג'ורג '] [מפתח: 77, ערך: פנינה]

ה מַפָּה לאחר המיון לפי ערכים:

[מפתח: 22, ערך: אפל] [מפתח: 66, ערך: ארל] [מפתח: 12, ערך: ג'ורג '] [מפתח: 55, ערך: ג'ון] [מפתח: 77, ערך: פנינה] [מפתח: 6, ערך: רוקי]

6. מיון אובייקטים מותאמים אישית

בואו נעבוד עכשיו עם אובייקט מותאם אישית:

יישומי שכבה ציבורית מכירים דומים {שם מחרוזת פרטי; גיל פרטי פרטי; משכורת כפולה פרטית; עובד ציבורי (שם מחרוזת, גיל שכיר, משכורת כפולה) {...} // גטרים סטנדרטיים, סטרים וטוסטרינג}

נשתמש בדברים הבאים עוֹבֵד מערך לדוגמא למיון בסעיפים הבאים:

@ לפני initVariables בטל בציבור () {.... עובדים = עובד חדש [] {עובד חדש ("ג'ון", 23, 5000), עובד חדש ("סטיב", 26, 6000), עובד חדש ("פרנק", 33, 7000), עובד חדש ("ארל", 43, 10000), עובד חדש ("ג'סיקה", 23, 4000), עובד חדש ("פנינה", 33, 6000)}; workersSorted = עובד חדש [] {עובד חדש ("ארל", 43, 10000), עובד חדש ("פרנק", 33, 70000), עובד חדש ("ג'סיקה", 23, 4000), עובד חדש ("ג'ון", 23, 5000), עובד חדש ("פנינה", 33, 4000), עובד חדש ("סטיב", 26, 6000)}; workersSortedByAge = עובד חדש [] {עובד חדש ("ג'ון", 23, 5000), עובד חדש ("ג'סיקה", 23, 4000), עובד חדש ("סטיב", 26, 6000), עובד חדש ("פרנק", 33, 70000), עובד חדש ("פנינה", 33, 4000), עובד חדש ("ארל", 43, 10000)}; }

אנו יכולים למיין מערכים או אוספים של אובייקטים מותאמים אישית:

1. בסדר הטבעי (באמצעות ניתן להשוות ממשק) או
2. בצו המסופק על ידי א משווהמִמְשָׁק

6.1. Uלשיר להשוות

הסדר הטבעי ב- java פירושו סדר בו יש למיין סדר פרימיטיבי או אובייקט במערך או אוסף נתון.

שניהם java.util. מערכים ו java.util.Collections שיהיה לך סוג() שיטה, ו מומלץ מאוד שסדרים טבעיים יהיו עקביים עם הסמנטיקה של שווים.

בדוגמה זו נשקול עובדים עם אותו הדבר שֵׁם כשווה:

@Test הציבור בטל givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (עובדים); assertTrue (Arrays.equals (עובדים, עובדים ממוינים)); }

ניתן להגדיר את הסדר הטבעי לאלמנטים על ידי יישום a ניתן להשוות ממשק שיש לו בהשוואה ל() שיטה להשוואת האובייקט הנוכחי והאובייקט שהועבר כוויכוח.

כדי להבין זאת בבירור, בואו נראה דוגמה עוֹבֵד מחלקה אשר מיישמת ניתן להשוות מִמְשָׁק:

מחלקה ציבורית מיישמת עובדים דומה {... @Override בוליאני ציבורי שווה (Object obj) {return ((עובד) obj) .getName (). שווה (getName ()); } @Override int int publicTo (אובייקט o) {עובד e = (עובד) o; להחזיר getName (). CompareTo (e.getName ()); }}

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

עכשיו מתי Arrays.sort (עובדים); נקרא בקוד שלעיל, אנו יודעים כעת מה ההיגיון והסדר שמתבצע במיון העובדים לפי הגיל:

[("ארל", 43, 10000), ("פרנק", 33, 70000), ("ג'סיקה", 23, 4000), ("ג'ון", 23, 5000), ("פנינה", 33, 4000) , ("סטיב", 26, 6000)]

אנו יכולים לראות שהמערך ממוין לפי שם העובד - שהופך כעת לסדר טבעי עבור עוֹבֵד מעמד.

6.2. באמצעות משווה

עכשיו, בואו למיין את האלמנטים באמצעות a משווה יישום ממשק - שם אנו מעבירים את המחלקה הפנימית האנונימית במהירות Arrays.sort () ממשק API:

בטל ציבורי @Test givenIntegerArray_whenUsingSort_thenSortedArray () {Integer [] integers = ArrayUtils.toObject (toSort); Arrays.sort (מספרים שלמים, משווה חדש () {@Override int int public השווה (מספר שלם a, מספר שלם ב) {החזר Integer.compare (a, b);}}); assertTrue (Arrays.equals (מספרים שלמים, ArrayUtils.toObject (sortedInts))); }

עכשיו מאפשר למיין עובדים על סמך שכר - והעביר יישום משווה אחר:

Arrays.sort (עובדים, משווה חדש () {@Override public int השווה (עובד o1, עובד o2) {החזר Double.compare (o1.getSalary (), o2.getSalary ());}});

מערכי העובדים הממוינים על בסיס שכר יהיה:

[(ג'סיקה, 23,4000.0), (ג'ון, 23,5000.0), (פרל, 33,6000.0), (סטיב, 26,6000.0), (פרנק, 33,7000.0), (ארל, 43,10000.0)] 

שים לב שנוכל להשתמש Collections.sort () בצורה דומה למיון רשימה ו מַעֲרֶכֶת של אובייקטים בסדר טבעי או בהתאמה אישית כמתואר לעיל למערכים.

7. מיון עם למבדות

התחל עם Java 8, נוכל להשתמש ב- Lambdas ליישום ה- משווה ממשק פונקציונלי.

אתה יכול להסתכל על Lambdas ב- Java 8 כדי לכתוב את התחביר.

בואו נחליף את המשווה הישן:

Comparator c = Comparator new () {@Override int int public השווה (מספר שלם a, מספר שלם ב) {החזר Integer.compare (a, b); }}

עם היישום המקביל, תוך שימוש בביטוי למבה:

משווה c = (a, b) -> Integer.compare (a, b);

לסיום, בואו נכתוב את המבחן:

@Test הציבור בטל givenArray_whenUsingSortWithLambdas_thenSortedArray () {Integer [] integersToSort = ArrayUtils.toObject (toSort); Arrays.sort (מספרים שלמים ToSort, (a, b) -> {return Integer.compare (a, b);}); assertTrue (Arrays.equals (integersToSort, ArrayUtils.toObject (sortedInts))); }

כפי שאתה יכול לראות, היגיון הרבה יותר נקי ותמציתי כאן.

8. שימוש Comparator. השוואה ו Comparator. ואז השוואה

Java 8 מגיע עם שני ממשקי API חדשים שימושיים למיון - משווה () ו thenComparing () בתוך ה משווה מִמְשָׁק.

אלה די שימושיים לשרשור של תנאים מרובים של משווה.

בואו ניקח בחשבון תרחיש שאולי נרצה להשוות עוֹבֵד על ידי גיל ואז עד שֵׁם:

@Test הציבור בטל givenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {רשימה workersList = Arrays.asList (עובדים); workers.sort (Comparator.comparing (עובד :: getAge)); assertTrue (Arrays.toString (workers.toArray ()) .equals (sortedArrayString)); }

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

הנה מערך העובדים לאחר המיון:

[(ג'ון, 23,5000.0), (ג'סיקה, 23,4000.0), (סטיב, 26,6000.0), (פרנק, 33,7000.0), (פרל, 33,6000.0), (ארל, 43,10000.0)]

כאן העובדים ממוינים על פי גיל.

אנחנו יכולים לראות ג'ון ו ג'סיקה הם בני אותו גיל - מה שאומר שלוגיקת ההזמנה צריכה לקחת בחשבון את שמותיהם - שאיתם נוכל להשיג thenComparing ():

... עובדים.סורט (Comparator.comparing (עובד :: getAge) .thenComparing (עובד :: getName)); ... 

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

[(ג'סיקה, 23,4000.0), (ג'ון, 23,5000.0), (סטיב, 26,6000.0), (פרנק, 33,7000.0), (פרל, 33,6000.0), (ארל, 43,10000.0)]

לכן משווה () ו thenComparing () בהחלט להפוך את תרחישי המיון המורכבים לנקיים יותר ליישום.

9. מסקנה

במאמר זה ראינו כיצד אנו יכולים להחיל מיון מַעֲרָך, רשימה, מַעֲרֶכֶת, ו מַפָּה.

ראינו גם הקדמה קצרה על האופן שבו תכונות של Java 8 יכולות להיות שימושיות במיון כמו שימוש במאמבות, משווה () ו thenComparing () ו parallelSort ().

כל הדוגמאות המשמשות במאמר זמינות באתר GitHub.