streamalism.org

1. הקדמה

במדריך זה, נסתכל על java.util. מערכים, מחלקת כלי עזר שהייתה חלק מג'אווה מאז Java 1.2.

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

2. יצירה

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

2.1. העתק של ו copyOfRange

להשתמש copyOfRange, אנו זקוקים למערך המקורי שלנו ולאינדקס ההתחלה (כולל) ואינדקס הסיום (בלעדי) אותו אנו רוצים להעתיק:

String [] intro = new String [] {"once", "upon", "a", "time"}; מחרוזת [] abridgement = Arrays.copyOfRange (storyIntro, 0, 3); assertArrayEquals (מחרוזת חדשה [] {"פעם אחת", "על", "a"}, קיצור); assertFalse (Arrays.equals (מבוא, קיצור));

ושימוש העתק של, היינו לוקחים הקדמה וגודל מערך יעד ונחזיר מערך חדש באורך זה:

מחרוזת [] מתוקנת = Arrays.copyOf (מבוא, 3); מחרוזת [] מורחבת = Arrays.copyOf (מבוא, 5); assertArrayEquals (Arrays.copyOfRange (intro, 0, 3), מתוקן); assertNull (מורחב [4]);

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

2.2. למלא

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

מחרוזת [] גמגום = מחרוזת חדשה [3]; Arrays.fill (מגמגם, "פעם אחת"); assertTrue (Stream.of (stutter) .allMatch (el -> "once". שווים (el));

לבדוק setAll כדי ליצור מערך שבו האלמנטים שונים.

שימו לב שעלינו לייצר את המערך בעצמנו מראש - בניגוד למשהו כמו מחרוזת [] מילוי = Arrays.fill ("פעם אחת"), 3);- מאחר שתכונה זו הוצגה לפני שהכללים הגנריים היו זמינים בשפה.

3. השוואה

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

3.1. שווים ו deepEquals

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

assertTrue (Arrays.equals (מחרוזת חדשה [] {"פעם אחת", "על", "a", "זמן"}, מבוא)); assertFalse (Arrays.equals (מחרוזת חדשה [] {"פעם אחת", "על", "a", null}, מבוא));

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

אובייקט [] סיפור = אובייקט חדש [] {מבוא, מחרוזת חדשה [] {"פרק ראשון", "פרק שני"}, סוף}; אובייקט [] copy = אובייקט חדש [] {intro, מחרוזת חדשה [] {"פרק ראשון", "פרק שני"}, סוף}; assertTrue (Arrays.deepEquals (סיפור, העתק)); assertFalse (Arrays.equals (סיפור, העתק));

שימו לב איך עמוקקוואלס עובר אבל שווים נכשל.

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

כמו כן, זה הופך את זה למסוכן להתקשר למערך עם התייחסות עצמית!

3.2. hashCode ו deepHashCode

ההטמעה של hashCode ייתן לנו את החלק השני של שווים/hashCode חוזה שמומלץ לאובייקטים של Java. אנו משתמשים hashCode לחישוב מספר שלם על בסיס תוכן המערך:

אובייקט [] looping = אובייקט חדש [] {intro, intro}; int hashBefore = Arrays.hashCode (לולאה); int deepHashBefore = Arrays.deepHashCode (לולאה);

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

מבוא [3] = null; int hashAfter = Arrays.hashCode (לולאה); 

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

int deepHashAfter = Arrays.deepHashCode (לולאה);

כעת אנו יכולים לראות את ההבדל בשתי השיטות:

assertEquals (hashAfter, hashBefore); assertNotEquals (deepHashAfter, deepHashBefore); 

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

4. מיון וחיפוש

לאחר מכן, בואו נסתכל על מערכי מיון וחיפוש.

4.1. סוג

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

מחרוזת [] ממוינת = Arrays.copyOf (מבוא, 4); Arrays.sort (ממוינים); assertArrayEquals (מחרוזת חדשה [] {"a", "פעם אחת", "זמן", "על"}, ממוינת);

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

סוג ישתמש באלגוריתם שונה עבור סוגי אלמנטים שונים. סוגים פרימיטיביים משתמשים בקורט-ציר כפול-ציר וסוגי אובייקט משתמשים ב- Timsort. לשניהם המקרה הממוצע של O (n יומן (n)) למערך הממוין באופן אקראי.

נכון ל- Java 8, parallelSort זמין למיזוג מיונים מקביל. הוא מציע שיטת מיון במקביל תוך שימוש בכמה Arrays.sort משימות.

4.2. חיפוש בינארי

החיפוש במערך לא ממוין הוא לינארי, אך אם יש לנו מערך ממוין, נוכל לעשות זאת O (יומן n), וזה מה שאנחנו יכולים לעשות איתו חיפוש בינארי:

int exact = Arrays.binarySearch (ממוין, "זמן"); int caseInsensitive = Arrays.binarySearch (ממוינת, "TiMe", String :: CompareToIgnoreCase); assertEquals ("זמן", מסודר [מדויק]); assertEquals (2, מדויק); assertEquals (מדויק, caseSensitive);

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

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

5. סטרימינג

כפי שראינו קודם, מערכים עודכן ב- Java 8 כדי לכלול שיטות המשתמשות ב- API של Stream כגון parallelSort (מוזכר לעיל), זרם ו setAll.

5.1. זרם

זרם נותן לנו גישה מלאה ל- API של Stream עבור המערך שלנו:

Assert.assertEquals (Arrays.stream (intro) .count (), 4); exception.expect (ArrayIndexOutOfBoundsException.class); Arrays.stream (intro, 2, 1) .count ();

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

6. טרנספורמציה

סוף כל סוף, toString,asList, ו setAll תן לנו כמה דרכים שונות לשנות מערכים.

6.1. toString ו deepToString

דרך נהדרת שנוכל להשיג גרסה קריאה של המערך המקורי שלנו היא toString:

assertEquals ("[once, upon, a, time]", Arrays.toString (storyIntro)); 

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

assertEquals ("[[פעם אחת, פעם, זמן], [פרק ראשון, פרק שני], [סוף,]]", Arrays.deepToString (סיפור));

6.2. asList

הכי נוח מכל מערכים שיטות לשימושנו היא asList. יש לנו דרך קלה להפוך מערך לרשימה:

רשימת משפטים = Arrays.asList (storyIntro); assertTrue (rets.contains ("על")); assertTrue (rets.contains ("זמן")); assertEquals (rets.size (), 4);

למרות זאת, השבים רשימה יהיה באורך קבוע כך שלא נוכל להוסיף או להסיר אלמנטים.

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

6.3. setAll

עם setAll, אנו יכולים להגדיר את כל האלמנטים של מערך עם ממשק פונקציונלי. יישום הגנרטור לוקח את מדד המיקום כפרמטר:

מחרוזת [] longAgo = מחרוזת חדשה [4]; Arrays.setAll (longAgo, i -> this.getWord (i)); assertArrayEquals (longAgo, מחרוזת חדשה [] {"a", "long", "time", "ago"});

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

7. קידומת מקבילה

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

7.1. parallelPrefix

אם המפעיל מבצע תוספת כמו במדגם הבא, [1, 2, 3, 4] יביא ל [1, 3, 6, 10]:

int [] arr = int int [] {1, 2, 3, 4}; Arrays.parallelPrefix (arr, (שמאל, ימין) -> שמאל + ימין); assertThat (arr, is (int int [] {1, 3, 6, 10}));

כמו כן, אנו יכולים לציין תת-משנה לפעולה:

int [] arri = int int [] {1, 2, 3, 4, 5}; Arrays.parallelPrefix (arri, 1, 4, (שמאל, ימין) -> שמאל + ימין); assertThat (arri, is (int int [] {1, 2, 5, 9, 5}));

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

לפונקציה שאינה אסוציאטיבית:

int nonassociativeFunc (int שמאל, int ימין) {חזרה שמאלה + ימין * שמאל; }

באמצעות parallelPrefix יניב תוצאות לא עקביות:

@ מבחן ציבורי בטל כאשר PrefixNonAssociative_thenError () {בוליאני עקבי = נכון; אקראי r = אקראי חדש (); עבור (int k = 0; k <100_000; k ++) {int [] arrA = r.ints (100, 1, 5) .toArray (); int [] arrB = Arrays.copyOf (arrA, arrA.length); Arrays.parallelPrefix (arrA, זה :: nonassociativeFunc); עבור (int i = 1; i <arrB.length; i ++) {arrB [i] = nonassociativeFunc (arrB [i - 1], arrB [i]); } עקבי = Arrays.equals (arrA, arrB); אם הפסקה (! עקבית); } assertFalse (עקבי); }

7.2. ביצועים

חישוב קידומת מקביל בדרך כלל יעיל יותר מאשר לולאות רציפות, במיוחד עבור מערכים גדולים. כאשר אנו מריצים מיקרו-ביצועים על מכונת אינטל Xeon (6 ליבות) עם JMH, אנו יכולים לראות שיפור ביצועים נהדר:

יחידות מידה שוויון ציון יחידות מידה largeArrayLoopSum thrpt 5 9.428 ± 0.075 ops / s largeArrayParallelPrefixSum thrpt 5 15.235 ± 0.075 ops / s מצב מידוד Cnt ציון שגיאה Units largeArrayLoopSum avgt 5 105.825 ± 0.846 ops / s largeArrayParallgtPrefixS

הנה קוד המידה:

@Benchmark ציבורי בטל largeArrayLoopSum (BigArray bigArray, Blackhole blackhole) {עבור (int i = 0; אני שמאלה + ימין); blackhole.consume (bigArray.data); }

7. מסקנה

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

מחלקה זו הורחבה במהדורות האחרונות של Java עם הכללת שיטות ייצור וצריכת זרמים ב- Java 8 ושיטות אי התאמה ב- Java 9.

המקור למאמר זה, כמו תמיד, הסתיים ב- Github.