היפוך רשימה בג'אווה - במקום ומחוץ

במדריך הקצר הזה, תלמד כיצד להפוך רשימה במקום ולא במקום ב-Java.

היפוך במקום ומחוץ למקום

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

שפות וספריות מסוימות מעדיפות התנהגויות ברירת מחדל שונות. ב-Java, רוב הפעולות ברשימות היפוך יהיו במקום.

אם זו ההתנהגות הרצויה שלך - מעולה! אם לא, תרצה ליצור עותק של הרשימה לפני שתהפוך את העותק:

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

הערה: אל האני clone() שיטה לא ליצור עותק עמוק. יצירת רשימה באמצעות new ArrayList(list) לא ליצור עותק עמוק. יצירת עותקים עמוקים אינה מעודדת, ולמרבה הפלא קשה לעשות זאת בצורה גנרית (ולא הגיוני במקרים מסוימים, תלוי בסוגי הנתונים ברשימה). זה לא ימנע ממך להיות מסוגל לחזור לאחור list ו לֹא יש את האלמנטים של listCopy אבל להיות הפוך.

Collections.reverse()

אל האני Collections.reverse() השיטה היא השיטה הסטנדרטית להיפוך אוסף, ופועלת כ"חסר" List.reverse() שיטה. זה הופך את הרשימה במקום:

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Collections.reverse(list);

System.out.println(list);     
System.out.println(listCopy); 

Lists.reverse(list) של גויאבה

אם אתה משתמש ב-Google Guava כבר בפרויקט שלך, אתה יכול גם למנף את Lists כיתה, אשר מציעה את reverse() שיטה, שאינה ממיינת את הרשימה המקורית במקום, אלא יוצרת עותק והופכת את העותק:

List list = new ArrayList(Arrays.asList(1, 2, 3));
List reversedList = Lists.reverse(list);

System.out.println(list);         
System.out.println(reversedList); 

אם עדיין אין לך את זה, אתה יכול להוסיף את Google Guava לפרויקט שלך באמצעות Maven, על ידי הכללת התלות שלו ב- pom.xml קובץ:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
</dependency>

או דרך Gradle:

implementation group: 'com.google.guava', name: 'guava'

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

List.add() ו-List.remove()

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

public static int process(int input) {
    return input;
}

List list = new ArrayList(Arrays.asList(1, 2, 3));

for (int i = 0, j = list.size()-1; i <= j; i++) {
    int lastValue = process(list.remove(j));
    list.add(i, lastValue);
}

System.out.println(list);  

בנצ 'מרק

אז מה הכי מהיר? זה תלוי גם אם ברצונך לבצע את הפעולה במקום או מחוץ למקום.

Benchmark היפוך במקום

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

List list = new Random().ints(100, 1, 11)
                .boxed()
                .collect(Collectors.toList());

int runs = 1000;

long start1 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListCollections(list);
}
long end1 = System.currentTimeMillis();
System.out.println(String.format("Collections.reverse() took: %s miliseconds", end1-start1));

long start2 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListGuava(list);
}
long end2 = System.currentTimeMillis();
System.out.println(String.format("Guava's Lists.reverse() took: %s miliseconds", end2-start2));

long start3 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListManually(list);
}
long end3 = System.currentTimeMillis();
System.out.println(String.format("Manually took: %s miliseconds", end3-start3));

System.out.println("Original list: " + list);

זו התוצאה:

Collections.reverse() took: 3 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 13 miliseconds
Original list: [6, 7, 9, 7, 2, 5, 4, 1, 3, 2, 2, 6, ...

מה קורה כשאנחנו מגדילים את מספר האלמנטים מ-100 ל-1000?

Collections.reverse() took: 9 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 133 miliseconds
Original list: [10, 2, 2, 6, 2, 4, 7, 3, 9, 2, 7, 5, ...

גויאבה שומרת על תו 4ms! לגישה הידנית יש את מורכבות הזמן הגרועה ביותר, והיא עלתה באופן ליניארי. Collections.reverse() סובלים פחות מהגדלה, אבל היישום של Guava סובל הכי פחות. עם זאת, זכור שאיננו מעתיקים ידנית את הרשימה עבור גישת הגויאבה. האם המדד ישתנה כאשר נוותר על הרעיון של רשימה "מקורית" ו"הפוכה"?

Benchmark היפוך מחוץ למקום

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

Collections.reverse() took: 7 miliseconds
Guava's Lists.reverse() took: 3 miliseconds
Manually took: 131 miliseconds
Original list: [6, 8, 10, 7, 3, 8, 7, 1, 1, 9, 5, ...

גויאבה עוד מצליח להתעלות בעקביות על שניהם Collections.reverse() והגישה הידנית.

סיכום

במדריך הקצר הזה, למדת כיצד להפוך רשימה ב-Java, במקום ובחוץ, תוך שמירה על הרשימה המקורית מהפעולה. השתמשנו ב Collections.reverse() שיטה, של גוגל גויאבה Lists.reverse() שיטה וגישה ידנית.