Αντιστροφή λίστας σε Java – In-Place και Out-Of-Place

Σε αυτό το σύντομο σεμινάριο, θα μάθετε πώς να αντιστρέφετε μια λίστα επιτόπου και εκτός τόπου στην 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); 

Guava's 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'

Σημείωση: Εάν δεν διαθέτετε ήδη το Google 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);  

αναφοράς

Λοιπόν, ποιο είναι το πιο γρήγορο; Αυτό εξαρτάται επίσης από το εάν θέλετε να εκτελέσετε τη λειτουργία επί τόπου ή εκτός τόπου.

Σημείο αναφοράς αντιστροφής επί τόπου

Ας μετρήσουμε και τις δύο προσεγγίσεις και στις τρεις μεθόδους, ξεκινώντας από το εκτός τόπου:

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, ...

Το Guava διατηρεί το σημάδι των 4ms! Η χειροκίνητη προσέγγιση έχει τη χειρότερη χρονική πολυπλοκότητα και αυξήθηκε γραμμικά. Collections.reverse() υποφέρουν λιγότερο από την κλιμάκωση, αλλά η εφαρμογή της Guava υποφέρει λιγότερο. Ωστόσο, έχετε υπόψη σας ότι δεν αντιγράφουμε με μη αυτόματο τρόπο τη λίστα για την προσέγγιση Guava. Θα αλλάξει το σημείο αναφοράς όταν απορρίψουμε την ιδέα να έχουμε μια «πρωτότυπη» και «αντίστροφη» λίστα;

Σημείο αναφοράς αντιστροφής εκτός τόπου

Με 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() μέθοδος, του Google Guava Lists.reverse() μέθοδο και μια χειροκίνητη προσέγγιση.