streamalism.org

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

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

נשווה גם את הביצועים הללו באמצעות JMH (רתמת Java Microbenchmark) כדי לקבוע איזו שיטה עובדת בצורה הטובה ביותר.

2. התקנה

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

String [] seedArray (int length) {String [] strings = new String [length]; ערך אקראי = אקראי חדש (); עבור (int i = 0; i <length; i ++) {strings [i] = String.valueOf (value.nextInt ()); } להחזיר מחרוזות; }

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

@State (Scope.Benchmark) מחלקת סטטי ציבורית SearchData {ספירת int intals = 1000; מחרוזת סטטית [] מיתרים = seedArray (1000); } 

3. חיפוש בסיסי

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

נתחיל משלוש שיטות המיישמות כל אלגוריתם:

searchList בוליאני (מחרוזת [] מחרוזות, מחרוזת searchString) {החזר Arrays.asList (SearchData.strings) .contains (searchString); } searchSet בוליאני (מחרוזת [] מחרוזות, מחרוזת searchString) {Set stringSet = new HashSet (Arrays.asList (SearchData.strings)); להחזיר stringSet.contains (searchString); } בוליאני searchLoop (String [] strings, String searchString) {for (String string: SearchData.strings) {if (string.equals (searchString)) return true; } להחזיר שקר; }

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

@BenchmarkMode (Mode.AverageTime) @Warmup (חזרות = 5) @OutputTimeUnit (TimeUnit.MICROSECONDS) 

והריץ כל בדיקה בלולאה:

@Benchmark search public void searchArrayLoop () {for (int i = 0; i <SearchData.count; i ++) {searchLoop (SearchData.strings, "T"); }} @Benchmark search public void searchArrayAllocNewList () {for (int i = 0; i <SearchData.count; i ++) {searchList (SearchData.strings, "T"); }} @Benchmark public search searchArrayAllocNewSet () {for (int i = 0; i <SearchData.count; i ++) {searchSet (SearchData.strings, "S"); }} 

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

SearchArrayTest.searchArrayAllocNewList avgt 20 937.851 ± 14.226 us / op SearchArrayTest.searchArrayAllocNewSet avgt 20 14309.122 ± 193.844 us / op SearchArrayTest.searchArrayLoop avgt 20 758.060 ± 9.433 us / op 

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

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

4. חיפוש יעיל יותר

מה קורה כשאנחנו יוצרים מקרים בודדים של רשימה ו מַעֲרֶכֶת ואז לעשות בהם שימוש חוזר לכל חיפוש?

בואו ננסה:

search void searchArrayReuseList () {List asList = Arrays.asList (SearchData.strings); עבור (int i = 0; i <SearchData.count; i ++) {asList.contains ("T"); }} search void publicArrayReuseSet () {Set asSet = new HashSet (Arrays.asList (SearchData.strings)); עבור (int i = 0; i <SearchData.count; i ++) {asSet.contains ("T"); }} 

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

אנו רואים תוצאות שונות מאוד:

SearchArrayTest.searchArrayLoop avgt 20 758.060 ± 9.433 us / op SearchArrayTest.searchArrayReuseList avgt 20 837.265 ± 11.283 us / op SearchArrayTest.searchArrayReuseSet avgt 20 14.030 ± 0.197 us / op 

תוך כדי חיפוש ב- רשימה הוא מהיר יותר מבעבר, מַעֲרֶכֶת יורד לפחות מאחוז מהזמן הנדרש לולאה!

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

חיפוש בטבלת hash, המבנה העומד בבסיס a HashSet, מורכבות הזמן היא 0 (1) ואילו מערך העומד בבסיס ה- רשימת מערך הוא 0 (n).

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

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

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

@Benchmark search public voidArrayBinarySearch () {Arrays.sort (SearchData.strings); עבור (int i = 0; i <SearchData.count; i ++) {Arrays.binarySearch (SearchData.strings, "T"); }} 

SearchArrayTest.searchArrayBinarySearch avgt 20 26.527 ± 0.376 us / op 

חיפוש בינארי מהיר מאוד, אם כי פחות יעיל מה- HashSet: הביצועים הגרועים ביותר עבור חיפוש בינארי הם 0 (log n), שמציב את הביצועים שלו בין זה של חיפוש מערך לטבלת hash.

6. מסקנה

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

בהתבסס על התוצאות שלנו, א HashSet עובד הכי טוב לחיפוש ברשימת ערכים. עם זאת, עלינו ליצור אותם מראש ולאחסן אותם ב- מַעֲרֶכֶת.

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