Inversarea unei liste în Java – la locul și în afara locului

În acest scurt tutorial, veți învăța cum să inversați o listă în loc și în afara locului în Java.

Inversări la locul și în afara locului

Când efectuați operațiuni pe liste – vă recomandăm să luați în considerare dacă operațiunile sunt efectuate la locul lor (modificările sunt puse în aplicare pe obiectul original) sau dacă nu sunt la locul lor (modificările sunt puse în aplicare pe o copie și originalul obiectul este neschimbat).

Unele limbi și biblioteci preferă comportamente implicite diferite. În Java, majoritatea operațiunilor privind listele inversate vor fi la loc.

Dacă acesta este comportamentul tău dorit - grozav! Dacă nu, veți dori să creați o copie a listei înainte de a inversa copia:

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

Notă: clone() metodă nu creați o copie profundă. Crearea unei liste folosind new ArrayList(list) nu creați o copie profundă. Crearea de copii adânci este descurajată și surprinzător de dificil de făcut într-un mod generic (și nu are sens în unele cazuri, în funcție de tipul (tipurile) de date din listă). Acest lucru nu vă va împiedica să puteți inversa list și nu au elementele de listCopy fiind însă inversată.

Collections.reverse()

Collections.reverse() metoda este metoda standard pentru inversarea unei colecții și acționează ca „lipsă” List.reverse() metodă. Acesta inversează lista în loc:

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); 

Listele de guava.reverse(lista)

Dacă utilizați deja Google Guava în proiectul dvs., puteți, de asemenea, să utilizați Lists clasa, care oferă reverse() metoda, care nu sortează lista originală în loc, ci creează o copie și inversează copia:

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

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

Dacă nu îl aveți deja, puteți adăuga Google Guava la proiectul dvs. folosind Maven, incluzând dependența acestuia în pom.xml fișier:

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

Sau prin Gradle:

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

Notă: Dacă nu aveți deja Google Guava sau nu intenționați să îl utilizați pentru alte părți ale proiectului dvs. - nu îl importați doar pentru această operațiune și rămâneți la Collections.reverse() metodă. Guava este o dependență mare și este o exagerare majoră să o folosiți numai pentru această operațiune.

List.add() și List.remove()

Dacă doriți să efectuați operații suplimentare pe lângă doar inversarea listei - puteți să iterați lista originală, să eliminați elementele de la sfârșit, să le treceți printr-o metodă arbitrară și să le adăugați înapoi la începutul listei:

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

Deci, care este cel mai rapid? Acest lucru depinde și dacă doriți să efectuați operația la locul sau în afara locului.

Benchmark de inversare in loc

Să analizăm ambele abordări pe toate cele trei metode, începând cu out-of-place:

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);

Rezultă:

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

Ce se întâmplă când creștem numărul de elemente de la 100 la 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 păstrează marca de 4 ms! Abordarea manuală are cea mai proastă complexitate în timp și a crescut liniar. Collections.reverse() suferă mai puțin de la extindere, dar implementarea Guava suferă cel mai puțin. Cu toate acestea, rețineți că nu copiam manual lista pentru abordarea Guava. Se va schimba reperul atunci când renunțăm la ideea de a avea o listă „originală” și „inversată”?

Benchmark de inversare în afara locului

Cu 1000 de elemente și fiecare operează pe o copie neinversată a listei (care a fost exclusă din măsurătorile de timp), când eliminăm copia manuală din fiecare metodă și reluăm codul:

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

guava încă reușește să le depășească constant pe ambele Collections.reverse() și abordarea manuală.

Concluzie

În acest scurt ghid, ați învățat cum să inversați o listă în Java, în loc și în afara locului, păstrând lista originală din operațiune. Noi am folosit Collections.reverse() metoda, Google Guava Lists.reverse() metodă și o abordare manuală.