Lista megfordítása Java nyelven – Helyben és Out-Of-Place

Ebből a rövid oktatóanyagból megtudhatja, hogyan lehet egy listát helyben és helytelenül felcserélni Java nyelven.

Tolatás a helyén és a helyén kívül

Listákon végrehajtott műveletek során érdemes megfontolni, hogy a műveleteket a helyükön hajtják-e végre (a változtatások az eredeti objektumon lépnek életbe), vagy nem a helyükön (a módosítások a másolaton és az eredetiben vannak végrehajtva) tárgy változatlan).

Egyes nyelvek és könyvtárak más alapértelmezett viselkedést részesítenek előnyben. Java-ban a legtöbb művelet a fordított listákon lesz a helyén.

Ha ez a kívánt viselkedés – nagyszerű! Ha nem, akkor a másolat visszafordítása előtt készítsen másolatot a listáról:

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

Jegyzet: A clone() módszer nem hozzon létre egy mély másolatot. Lista készítése a segítségével new ArrayList(list) nem hozzon létre egy mély másolatot. Mélymásolatok készítése nem ajánlott, és meglepően nehéz általános módon (és bizonyos esetekben nincs értelme, a listában szereplő adattípus(ok)tól függően). Ez nem akadályozza meg, hogy vissza tudjon fordulni list és a nem elemei vannak listCopy viszont fordítva.

Collections.reverse()

A Collections.reverse() A metódus a szabványos módszer a gyűjtemény visszafordításához, és úgy működik, mint a „hiányzó” List.reverse() módszer. Helyben megfordítja a listát:

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 listái.fordított(lista)

Ha már használja a Google Guavát a projektben, akkor azt is kihasználhatja Lists osztály, amely a reverse() módszer, amely nem a helyére rendezi az eredeti listát, hanem létrehoz egy másolatot, és megfordítja a másolatot:

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

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

Ha még nem rendelkezik vele, hozzáadhatja a Google Guavát a projektjéhez a Maven segítségével, ha felveszi a függőségét a pom.xml file:

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

Vagy a Gradle-n keresztül:

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

Jegyzet: Ha még nem rendelkezik Google Guava programmal, vagy nem kívánja használni projektje más részeihez – ne csak ehhez a művelethez importálja, hanem ragaszkodjon a Collections.reverse() módszer. A guava nagy függőséget jelent, és túlzás, ha csak ehhez a művelethez használja.

List.add() és List.remove()

Ha a lista megfordításán kívül további műveleteket is szeretne végrehajtani – ismételheti az eredeti listát, eltávolíthatja az elemeket a végéről, átvezetheti őket egy tetszőleges metóduson, és visszahelyezheti őket a lista elejére:

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

Szóval melyik a leggyorsabb? Ez attól is függ, hogy a műveletet a helyén vagy a helyén kívül kívánja végrehajtani.

Helyi megfordítási referenciaérték

Vizsgáljuk meg mindkét megközelítést mindhárom módszerrel, kezdve a nem helyénvalóval:

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

Ennek eredményeként:

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

Mi történik, ha az elemek számát 100-ról 1000-re növeljük?

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

A guava megtartja a 4 ms jelet! A manuális megközelítésnek van a legrosszabb időbeni összetettsége, és lineárisan emelkedett. Collections.reverse() kevésbé szenvednek a méretezéstől, de a Guava megvalósítása szenved a legkevésbé. Ne feledje azonban, hogy nem másoljuk manuálisan a listát a Guava megközelítéshez. Megváltozik-e a viszonyítási alap, ha elvetjük az „eredeti” és a „fordított” listát?

Helyen kívüli megfordítási referenciaérték

1000 elemmel, és mindegyik a lista nem fordított másolatán működik (amit kizártunk az időmérésekből), amikor minden metódusból eltávolítjuk a kézi másolatot, és újra futtatjuk a kódot:

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

Gujávafa még mindig sikerül folyamatosan felülmúlnia mindkettőt Collections.reverse() és a kézi megközelítés.

Következtetés

Ebből a rövid útmutatóból megtanulta, hogyan lehet megfordítani egy listát Java nyelven, helyben és helytelenül, megőrizve az eredeti listát a műveletből. Használtuk a Collections.reverse() módszer, a Google Guava Lists.reverse() módszer és manuális megközelítés.