הסר את כל המופעים של ערך ספציפי מרשימה

1. הקדמה

ב- Java, פשוט להסיר ערך ספציפי מ- רשימה באמצעות List.remove (). למרות זאת, להסיר ביעילות את כל המופעים של ערך הרבה יותר קשה.

במדריך זה נראה פתרונות מרובים לבעיה זו המתארים את היתרונות והחסרונות.

לשם הקריאות אנו משתמשים במנהג אישי רשימה (int ...) שיטה במבחנים, המחזירה רשימת מערך המכיל את האלמנטים שעברנו.

2. שימוש בא בזמן לוּלָאָה

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

בטל removeAll (רשימת רשימה, אלמנט int) {while (list.contains (element)) {list.remove (element); }}

עם זאת, זה לא עובד כצפוי:

// רשימת רשימה נתונה = רשימה (1, 2, 3); int valueToRemove = 1; // כאשר assertThatThrownBy (() -> removeAll (רשימה, valueToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);

הבעיה היא בשורה השלישית: אנו מתקשרים List.remove (int), המתייחס לטיעון שלו כאל אינדקס, ולא לערך שאנו רוצים להסיר.

במבחן למעלה אנו תמיד מתקשרים list.remove (1), אבל אינדקס האלמנט שאנחנו רוצים להסיר הוא 0. יִעוּד List.remove () מעביר את כל האלמנטים לאחר ההסרה למדדים קטנים יותר.

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

כשנותר רק הראשון, האינדקס 1 יהיה לא חוקי. לפיכך אנו מקבלים יוצא מן הכלל.

שים לב, כי אנו נתקלים בבעיה זו רק אם אנו מתקשרים List.remove () עם פרימיטיבי בתים, קצר, char אוֹ int הטיעון, מכיוון שהדבר הראשון שהמהדר עושה כאשר הוא מנסה למצוא את השיטה העומס יתר על המידה, הוא מתרחב.

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

בטל removeAll (רשימת רשימה, אלמנט שלם) {while (list.contains (element)) {list.remove (element); }}

עכשיו הקוד עובד כצפוי:

// רשימת רשימה נתונה = רשימה (1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

מאז List.contains () ו List.remove () שניהם צריכים למצוא את ההתרחשות הראשונה של האלמנט, קוד זה גורם לחציית אלמנטים מיותרת.

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

בטל removeAll (רשימת רשימה, אלמנט שלם) {אינדקס int; ואילו ((index = list.indexOf (element))> = 0) {list.remove (index); }}

אנו יכולים לאמת שזה עובד:

// רשימת רשימה נתונה = רשימה (1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

בעוד שפתרונות אלה מייצרים קוד קצר ונקי, עדיין יש להם ביצועים גרועיםכי אנחנו לא עוקבים אחר ההתקדמות, List.remove () צריך למצוא את המופע הראשון של הערך שסופק כדי למחוק אותו.

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

3. הסרה עד רשימה שינויים

List.remove (רכיב E) יש תכונה שעדיין לא הזכרנו: אותה מחזירה א בוליאני ערך, כלומר נָכוֹן אם ה רשימה השתנה בגלל הפעולה, ולכן הוא הכיל את האלמנט.

ציין זאת List.remove (אינדקס int) מחזיר בטל, מכיוון שאם האינדקס שסופק תקף, ה- רשימה תמיד מסיר אותו. אחרת, זה זורק IndexOutOfBoundsException.

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

בטל removeAll (רשימת רשימה, אלמנט int) {תוך (list.remove (אלמנט)); }

זה עובד כצפוי:

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

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

3. שימוש ב- ל לוּלָאָה

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

בטל removeAll (רשימת רשימה, אלמנט int) {עבור (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); }}}

זה עובד כצפוי:

// רשימת רשימה נתונה = רשימה (1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

עם זאת, אם ננסה עם קלט אחר, הוא מספק פלט שגוי:

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (1, 2, 3));

בואו ננתח כיצד הקוד עובד, שלב אחר שלב:

  • i = 0
    • אֵלֵמֶנט ו list.get (i) שניהם שווים ל- 1 בשורה 3, כך שג'אווה נכנס לגוף ה- אם הַצהָרָה,
    • אנו מסירים את האלמנט באינדקס 0,
    • כך רשימה מכיל כעת 1, 2 ו 3
  • i = 1
    • list.get (i) החזרות 2 כי כאשר אנו מסירים אלמנט מ- רשימה, הוא מעביר את כל האלמנטים המתקדמים למדדים קטנים יותר

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

הקטנתו כאשר אנו מסירים את האלמנט:

בטל removeAll (רשימת רשימה, אלמנט int) {עבור (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); אני--; }}}

הגדלתו רק כאשר איננו מסירים את האלמנט:

בטל removeAll (רשימת רשימה, אלמנט int) {עבור (int i = 0; i <list.size ();) {if (Objects.equals (element, list.get (i))) {list.remove (i) ; } אחר {i ++; }}}

שים לב, שבאחרון הסרנו את ההצהרה i ++ בשורה 2.

שני הפתרונות פועלים כצפוי:

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

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

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

4. באמצעות א לכל אחד לוּלָאָה

מאז Java 5 אנו יכולים להשתמש ב- לכל אחד לולאה לחזור דרך א רשימה. בואו נשתמש בו להסרת אלמנטים:

void removeAll (רשימת רשימה, אלמנט int) {עבור (מספר שלם: רשימה) {if (Objects.equals (number, element)) {list.remove (number); }}}

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

כמו כן, בדרך זו אנו קוראים List.remove (רכיב E), שמצפה לערך שאנו רוצים להסיר, ולא לאינדקס.

עד כמה שזה נראה נקי, למרבה הצער, זה לא עובד:

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר assertThatThrownBy (() -> removeWithForEachLoop (רשימה, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);

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

הלקח הוא: אנחנו לא צריכים לשנות א רשימהבזמן שאנחנו ניגשים לאלמנטים שלו ב- לכל אחד לוּלָאָה.

5. שימוש ב- איטרטור

אנחנו יכולים להשתמש ב- איטרטור ישירות לחצות ולשנות את רשימה עם זה:

בטל removeAll (רשימת רשימה, אלמנט int) {עבור (Iterator i = list.iterator (); i.hasNext ();) {מספר שלם = i.next (); אם (Objects.equals (מספר, אלמנט)) {i.remove (); }}}

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

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

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

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

6. איסוף

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

רשימה removeAll (רשימת רשימה, אלמנט int) {רשימה שנותרה Elements = ArrayList חדש (); עבור (מספר שלם: רשימה) {אם (! Objects.equals (מספר, אלמנט)) {restElements.add (מספר); }} להחזיר את Elements שנותרו; }

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

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר תוצאת רשימה = removeAll (list, valueToRemove); // ואז assertThat (תוצאה) .isEqualTo (רשימה (2, 3));

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

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

יישום זה מתנהג באופן שונה מבחינות מסוימות מאשר הקודמות:

  • זה לא משנה את המקור רשימה אבל מחזיר חדש אחד
  • השיטה מחליטה מה הוחזר רשימההיישום הוא, זה עשוי להיות שונה מהמקור

כמו כן, אנו יכולים לשנות את היישום שלנו ל- לקבל את ההתנהגות הישנה; אנו מנקים את המקור רשימה והוסף אליו את האלמנטים שנאספו:

בטל removeAll (רשימת רשימה, אלמנט int) {רשימה שנותרהמרכיבים = ArrayList חדש (); עבור (מספר שלם: רשימה) {אם (! Objects.equals (מספר, אלמנט)) {restElements.add (מספר); }} list.clear (); list.addAll (restElements); }

זה עובד באותה צורה כמו הקודמים:

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

מכיוון שאנחנו לא משנים את רשימה כל הזמן, אנחנו לא צריכים לגשת לאלמנטים לפי מיקום או להזיז אותם. כמו כן, ישנם רק שני הקצאות מחדש של מערך אפשרי: כאשר אנו מתקשרים List.clear () ו List.addAll ().

7. שימוש ב- API של Stream

Java 8 הציגה ביטויי lambda ו- API של זרם. בעזרת התכונות החזקות הללו, אנו יכולים לפתור את הבעיה שלנו באמצעות קוד נקי מאוד:

List removeAll (רשימת רשימה, אלמנט int) {return list.stream () .filter (e ->! Objects.equals (e, element)) .collect (Collectors.toList ()); }

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

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

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר תוצאת רשימה = removeAll (list, valueToRemove); // ואז assertThat (תוצאה) .isEqualTo (רשימה (2, 3));

שים לב, שנוכל להמיר אותו לעבודה כמו שאר הפתרונות באותה גישה שעשינו עם היישום 'איסוף' המקורי.

8. שימוש להסיר אם

עם lambdas וממשקים פונקציונליים, Java 8 הציגה גם כמה סיומות API. לדוגמא, ה List.removeIf () שיטה, המיישמת את מה שראינו בחלק האחרון.

זה מצפה א לְבַסֵס, שצריך לחזור נָכוֹן כשאנחנו רוצים להסיר את האלמנט, בניגוד לדוגמא הקודמת, לשם היינו צריכים לחזור נָכוֹן כשרצינו לשמור על האלמנט:

בטל removeAll (רשימת רשימה, אלמנט int) {list.removeIf (n -> Objects.equals (n, element)); }

זה עובד כמו שאר הפתרונות שלמעלה:

// רשימת רשימה נתונה = רשימה (1, 1, 2, 3); int valueToRemove = 1; // כאשר removeAll (רשימה, valueToRemove); // ואז assertThat (רשימה) .isEqualTo (רשימה (2, 3));

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

9. מסקנה

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

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


$config[zx-auto] not found$config[zx-overlay] not found