Obračanje seznama v Javi – na mestu in zunaj mesta

V tej kratki vadnici se boste naučili obrniti seznam na mestu in zunaj njega v Javi.

Obračanje na mestu in zunaj mesta

Ko izvajate operacije na seznamih – morda boste želeli razmisliti, ali se operacije izvajajo na mestu (spremembe so izvedene na izvirnem objektu) ali pa niso na mestu (spremembe so izvedene na kopiji in izvirnik predmet je nespremenjen).

Nekateri jeziki in knjižnice imajo raje drugačna privzeta vedenja. V Javi bo večina operacij obračanja seznamov na mestu.

Če je to vaše želeno vedenje – super! Če ne, boste želeli ustvariti kopijo seznama, preden obrnete kopijo:

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

Opomba: O clone() Metoda ne ustvarite globoko kopijo. Ustvarjanje seznama z uporabo new ArrayList(list) ne ustvarite globoko kopijo. Ustvarjanje globokih kopij je odsvetovano in presenetljivo težko izvedljivo na splošen način (in v nekaterih primerih ni smiselno, odvisno od tipov podatkov na seznamu). To vas ne bo ustavilo pri vzvratni vožnji list in ne imajo elemente listCopy pa je obrnjeno.

Collections.reverse()

O Collections.reverse() metoda je standardna metoda za razveljavitev zbirke in deluje kot "manjkajoča" List.reverse() metoda. Seznam obrne na mestu:

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)

Če v svojem projektu že uporabljate Google Guava, lahko izkoristite tudi Lists razreda, ki ponuja reverse() metoda, ki izvirnega seznama ne razvrsti na mestu, ampak ustvari kopijo in obrne kopijo:

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

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

Če ga še nimate, lahko svojemu projektu dodate Google Guavo z Mavenom, tako da vključite njegovo odvisnost v pom.xml datoteka:

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

Ali preko Gradla:

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

Opomba: Če še nimate Google Guave ali je ne nameravate uporabljati za druge dele svojega projekta – je ne uvozite samo za to operacijo in se držite Collections.reverse() metoda. Guava je v veliki meri odvisna, zato je uporaba le za to operacijo prevelika.

List.add() in List.remove()

Če želite izvesti dodatne operacije poleg samo obračanja seznama – lahko ponavljate po prvotnem seznamu, odstranite elemente s konca, jih podate skozi poljubno metodo in jih dodate nazaj na začetek seznama:

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

merilo

Torej, kateri je najhitrejši? To je odvisno tudi od tega, ali želite operacijo izvesti na mestu ali zunaj njega.

Primerjalno merilo razveljavitve na mestu

Primerjajmo oba pristopa z vsemi tremi metodami, začenši z nenamesto:

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

Rezultat tega je:

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

Kaj se zgodi, ko povečamo število elementov s 100 na 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 ohranja oznako 4ms! Ročni pristop ima najslabšo časovno zahtevnost, ki je naraščala linearno. Collections.reverse() manj trpijo zaradi povečanja, najmanj pa trpi Guavina izvedba. Vendar ne pozabite, da seznama za pristop Guava ne kopiramo ročno. Ali se bo merilo uspešnosti spremenilo, ko bomo opustili idejo o "izvirnem" in "obrnjenem" seznamu?

Referenčno merilo razveljavitve zunaj mesta

S 1000 elementi in vsak deluje na neobrnjeni kopiji seznama (ki je bil izključen iz časovnih meritev), ko odstranimo ročno kopijo iz vsake metode in znova zaženemo kodo:

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 Še vedno uspe dosledno prekašati oba Collections.reverse() in ročni pristop.

zaključek

V tem kratkem vodniku ste se naučili, kako obrniti seznam v Javi, na mestu in zunaj njega, pri čemer ohranite prvotni seznam iz operacije. Uporabili smo Collections.reverse() metoda, Google Guava's Lists.reverse() metoda in ročni pristop.