streamalism.org

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

HashSet הוא אוסף לאחסון אלמנטים ייחודיים.

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

2. HashSet.removeAll ()

ה להסיר את כל השיטה מסירה את כל האלמנטים הכלולים ב- אוסף:

Set set = HashSet חדש (); set.add (1); set.add (2); set.add (3); set.add (4); אוסף אוספים = ArrayList חדש (); collection.add (1); collection.add (3); set.removeAll (אוסף); מספר שלם [] actualElements = מספר שלם חדש [set.size ()]; מספר שלם [] expectElements = מספר שלם חדש [] {2, 4}; assertArrayEquals (expectedElements, set.toArray (actualElements)); 

כתוצאה מכך, האלמנטים 1 ו- 3 יוסרו מהסט.

3. יישום פנימי ומורכבות זמן

RemoveAll () השיטה קובעת איזה מהם קטן יותר - הסט או האוסף. זה נעשה על ידי הפעלת ה- גודל() שיטה על הסט ואוסף.

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

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

עכשיו במקרה זה, אם האוסף הוא רשימת מערך, מורכבות הזמן של מכיל () השיטה היא O (M). כך מורכבות הזמן הכוללת להסרת כל האלמנטים הקיימים ב רשימת מערך מהסט הוא O (נ * M).

אם האוסף שוב HashSet, מורכבות הזמן של מכיל () השיטה היא O (1). כך מורכבות הזמן הכוללת להסרת כל האלמנטים הקיימים ב HashSet מהסט הוא O (נ).

4. ביצועים

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

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

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterations = 5) מחלקה ציבורית HashSetBenchmark {@State (Scope.Thread) מחלקה סטטית ציבורית MyState {פרטית סט עובדSet1 = HashSet חדש (); רשימת עובדים רשימת עובדים פרטית = ArrayList חדש (); ערכה פרטית EmploySet2 = HashSet חדש (); רשימת עובדים רשימת עובדים פרטית = ArrayList חדש (); קבוצה פרטית עובדSet3 = HashSet חדש (); קבוצה פרטית עובדSet4 = HashSet חדש (); set1 פרטי פרטי ארוך = 60000; רשימה ארוכה פרטית 1 גודל = 50000; set2Size פרטי ארוך = 50000; רשימה ארוכה פרטית 2Size = 60000; set3Size פרטי ארוך = 50000; set4Size פרטי ארוך = 60000; @Setup (Level.Trial) setUp public public ריק () {// ערכות אוכלוסין}}}

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

@Benchmark ציבורי בוליאני given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance (מצב MyState) {return state.employeeSet1.removeAll (state.employeeList1); } @Benchmark ציבורי בוליאני given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance (מצב MyState) {return state.employeeSet2.removeAll (state.employeeList2); } @Benchmark ציבורי בוליאני given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance (מצב MyState) {return state.employeeSet3.removeAll (state.employeeSet4); }

והנה התוצאות:

יחידות מידה של שוויון ציון יחידות שגיאה HashSetBenchmark.testHashSetSizeGreaterThanCollection avgt 20 2700457.099 ± 475673.379 ns / op HashSetBenchmark.testHashSetSmallerThanCollection avgt 20 31522676649.950 ± 3556834894.168 nash.shash

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

5. מסקנה

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

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