Odwracanie listy w Javie — w miejscu i poza miejscem

W tym krótkim samouczku dowiesz się, jak odwrócić listę na miejscu i nie na miejscu w Javie.

Odwracanie na miejscu i poza miejscem

Podczas wykonywania operacji na listach — warto rozważyć, czy operacje są wykonywane na miejscu (zmiany są wprowadzane na oryginalnym obiekcie), czy też nie są na miejscu (zmiany są wprowadzane na kopii, a oryginał obiekt jest niezmieniony).

Niektóre języki i biblioteki preferują różne domyślne zachowania. W Javie większość operacji na listach odwracania będzie: w miejscu.

Jeśli to jest Twoje pożądane zachowanie – świetnie! Jeśli nie, utwórz kopię listy przed cofnięciem kopii:

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

Uwaga: Połączenia clone() metoda nie utwórz głęboką kopię. Tworzenie listy za pomocą new ArrayList(list) nie utwórz głęboką kopię. Tworzenie głębokich kopii jest odradzane i zaskakująco trudne do wykonania w sposób ogólny (i w niektórych przypadkach nie ma sensu, w zależności od typu danych na liście). To nie powstrzyma cię przed możliwością odwrócenia list i nie mieć elementy listCopy jednak odwrócona.

Kolekcje.reverse()

Połączenia Collections.reverse() metoda jest standardową metodą odwracania kolekcji i działa jako „brakująca” List.reverse() metoda. Odwraca listę na miejscu:

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

Guawa Lists.reverse(lista)

Jeśli korzystasz już z Google Guava w swoim projekcie, możesz również wykorzystać Lists klasy, która oferuje reverse() metoda, która nie sortuje oryginalnej listy w miejscu, ale tworzy kopię i odwraca kopię:

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

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

Jeśli jeszcze go nie masz, możesz dodać Google Guava do swojego projektu za pomocą Mavena, dołączając jego zależność do swojego pom.xml file:

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

Lub przez Gradle:

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

Uwaga: Jeśli nie masz jeszcze Google Guava lub nie zamierzasz używać go w innych częściach swojego projektu – nie importuj go tylko do tej operacji i trzymaj się Collections.reverse() metoda. Guava jest dużą zależnością i jest to poważna przesada, używaj jej tylko do tej operacji.

List.add() i List.remove()

Jeśli chcesz wykonać dodatkowe operacje oprócz odwrócenia listy – możesz iterować po oryginalnej liście, usunąć elementy z końca, przekazać je dowolną metodą i dodać je z powrotem na początku listy:

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

Więc który jest najszybszy? Zależy to również od tego, czy chcesz wykonać operację w miejscu, czy poza nim.

Test odwrócenia w miejscu

Porównajmy oba podejścia we wszystkich trzech metodach, zaczynając od nie na miejscu:

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

To skutkuje:

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

Co się stanie, gdy zwiększymy liczbę elementów ze 100 do 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 zachowuje znak 4 ms! Podejście ręczne ma największą złożoność czasową i rosło liniowo. Collections.reverse() mniej cierpią na skalowanie, ale implementacja Guava ucierpi najmniej. Pamiętaj jednak, że nie kopiujemy ręcznie listy dla podejścia Guava. Czy benchmark zmieni się, gdy porzucimy pomysł posiadania „oryginalnej” i „odwróconej” listy?

Test odwrócenia poza miejscem

Przy 1000 elementach, a każdy działający na nieodwróconej kopii listy (która została wykluczona z pomiarów czasu), gdy usuniemy ręczną kopię z każdej metody i ponownie uruchomimy kod:

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

Guawa nadal udaje się konsekwentnie przewyższać oba Collections.reverse() i podejście ręczne.

Wnioski

W tym krótkim przewodniku dowiedziałeś się, jak odwrócić listę w Javie, w miejscu i poza miejscem, zachowując oryginalną listę przed operacją. Użyliśmy Collections.reverse() metoda, Google Guava Lists.reverse() metoda i podejście ręczne.