streamalism.org

1. הקדמה

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

HashSet הוא אוסף לאחסון אלמנטים ייחודיים. למידע נוסף על HashSet, בדוק קישור זה.

רשימת מערך הוא יישום פופולרי של java.util.List מִמְשָׁק.

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

2. HashSet.contains ()

באופן פנימי, HashSet היישום מבוסס על א מפת גיבוב למשל. ה מכיל () שיחות שיטה HashMap.containsKey (אובייקט).

הנה, זה בודק אם ה- לְהִתְנַגֵד נמצא במפה הפנימית או לא. המפה הפנימית מאחסנת נתונים בתוך הצמתים, המכונים דליים. כל דלי תואם לקוד hash שנוצר עם hashCode () שיטה. כך מכיל () ממש משתמש hashCode () שיטה למצוא את של אובייקט מקום.

עכשיו בואו נקבע את מורכבות זמן החיפוש. לפני שתמשיך קדימה, ודא שאתה מכיר את סימון ה- Big-O.

בממוצע, ה מכיל () שֶׁל HashSet רץ פנימה O (1) זְמַן. מקבל את של אובייקט מיקום הדלי הוא פעולה קבועה בזמן. אם ניקח בחשבון התנגשויות אפשריות, זמן החיפוש עשוי לעלות עד יומן (n) מכיוון שמבנה הדלי הפנימי הוא א TreeMap.

זהו שיפור מ- Java 7 שהשתמש ב- רשימה מקושרת למבנה הדלי הפנימי. באופן כללי, התנגשויות בקוד hash הן נדירות. אז נוכל לשקול את מורכבות בדיקת האלמנטים כ- O (1).

3. ArrayList.cמתחיל ()

כְּלַפֵּי פְּנִים, רשימת מערך משתמש ב- indexOf (אובייקט) שיטה לבדוק אם האובייקט נמצא ברשימה. ה indexOf (אובייקט) שיטה מאחרת את כל המערך ומשווה כל אלמנט עם שווה (אובייקט) שיטה.

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

4. בדיקת מידוד

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

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

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterations = 5) אוסף בכיתה ציבורית CollectionsBenchmark {@State (Scope.Thread) מחלקה סטטית ציבורית MyState {פרטית סט עובדSet = חדש HashSet (); רשימת עובדים רשימת פרטיות = ArrayList חדש (); איטרציות ארוכות פרטיות = 1000; עובד שכיר פרטי = עובד חדש (100 ליטר, "הארי"); @Setup (Level.Trial) setUp () ריק חלל ציבורי (למשך (ארוך i = 0; i <חזרות; i ++) {עובדSet.add (עובד חדש (i, "ג'ון")); workerList.add (עובד חדש (i, "ג'ון")); } employeeList.add (עובד); employeeSet.add (עובד); }}}

כאן, אנו יוצרים ומאתחלים HashSet ו רשימת מערך שֶׁל עוֹבֵד חפצים:

שכבה ציבורית עובד {פרטי מזהה ארוך; שם מחרוזת פרטי; // קובעי קונסטרוקטור וגטר הולכים לכאן}

אנו מוסיפים את עובד = עובד חדש (100 ליטר, "הארי") למשל כאלמנטים האחרונים בשני האוספים. אז אנחנו בודקים את עוֹבֵד זמן חיפוש האובייקט למקרה הגרוע ביותר האפשרי.

@ OutputTimeUnit (TimeUnit.NANOSECONDS) מציין שאנחנו רוצים את התוצאות בשניות ננו. מספר ברירת המחדל @חימום איטרציות הן 5 במקרה שלנו. ה @BenchmarkMode נקבע ל Mode.AverageTime, כלומר אנו מעוניינים לחשב זמן ריצה ממוצע. לביצוע הראשון, שמנו איטרציות = 1000 פריטים באוספים שלנו.

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

@Benchmark test בוליאני ציבורי ArrayList (מדינת MyState) {return state.employeeList.contains (state.employee); }

כאן אנו בודקים האם ה- רשימת עובדים מכיל עוֹבֵד לְהִתְנַגֵד.

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

@Benchmark מבוליאני ציבורי testHashSet (MyState state) {return state.employeeSet.contains (state.employee); }

לבסוף, אנו יכולים להריץ את הבדיקה:

ראשי ריק סטטי ציבורי (String [] args) זורק Exception {Options options = new OptionsBuilder () .include (CollectionsBenchmark.class.getSimpleName ()) .forks (1) .build (); רץ חדש (אפשרויות) .run (); }

להלן התוצאות:

מצב מידוד Cnt ציון שגיאה יחידות אוספים Benchmark.testArrayList avgt 20 4035.646 ± 598.541 ns / op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns / op

אנו יכולים לראות בבירור כי testArrayList לשיטה יש 4035.646 ns ציון חיפוש ממוצע, בעוד ש- testHashSet מבצע מהר יותר עם 9.456 ns בממוצע.

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

מצב מידוד Cnt ציון שגיאה יחידות אוספים Benchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns / op CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns / op

גם כאן, ה מכיל () ב HashSet יש יתרון ביצועים עצום על פני רשימת מערך.

5. מסקנה

כתיבה מהירה זו מסבירה את ביצועי ה- מכיל () שיטת ה- HashSet ו רשימת מערך אוספים. בעזרת ה- benchmarking של JMH הצגנו את הביצועים של מכיל () לכל סוג אוסף.

לסיכום, אנו יכולים ללמוד זאת ה מכיל () השיטה עובדת מהר יותר ב HashSet בהשוואה ל- רשימת מערך.

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