Een lijst omkeren in Java - ter plaatse en niet op zijn plaats

In deze korte zelfstudie leert u hoe u een lijst op zijn plaats en niet op zijn plaats in Java kunt omkeren.

Ter plaatse en buiten de plaats omkeren

Wanneer u bewerkingen op lijsten uitvoert, wilt u misschien overwegen of de bewerkingen ter plaatse worden uitgevoerd (wijzigingen worden doorgevoerd op het oorspronkelijke object), of dat ze niet op hun plaats zijn (wijzigingen worden doorgevoerd op een kopie en het origineel object is ongewijzigd).

Sommige talen en bibliotheken geven de voorkeur aan ander standaardgedrag. In Java zijn de meeste bewerkingen op omkeerlijsten: in situ.

Als dit je gewenste gedrag is - geweldig! Als dat niet het geval is, moet u een kopie van de lijst maken voordat u de kopie ongedaan maakt:

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

Opmerking: De clone() methode niet maak een diepe kopie. Een lijst maken met new ArrayList(list) niet maak een diepe kopie. Het maken van diepe kopieën wordt ontmoedigd en verrassend moeilijk om op een generieke manier te doen (en heeft in sommige gevallen geen zin, afhankelijk van het (de) gegevenstype(n) in de lijst). Dit zal je er niet van weerhouden om terug te keren list en niet hebben de elementen van listCopy wordt wel teruggedraaid.

Verzamelingen.reverse()

De Collections.reverse() methode is de standaardmethode voor het terugdraaien van een verzameling en fungeert als de "ontbrekende" List.reverse() methode. Het keert de lijst op zijn plaats om:

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(lijst)

Als u Google Guava al in uw project gebruikt, kunt u ook gebruikmaken van de Lists klasse, die de reverse() methode, die de originele lijst niet op zijn plaats sorteert, maar een kopie maakt en de kopie ongedaan maakt:

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

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

Als je het nog niet hebt, kun je Google Guava aan je project toevoegen met Maven, door de afhankelijkheid ervan op te nemen in je pom.xml file:

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

Of via Gradle:

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

Opmerking: Als u Google Guava nog niet heeft, of niet van plan bent om het voor andere delen van uw project te gebruiken, importeer het dan niet alleen voor deze bewerking en houd u aan de Collections.reverse() methode. Guava is een grote afhankelijkheid en het is een grote overkill om het alleen voor deze bewerking te gebruiken.

Lijst.add() en Lijst.remove()

Als u extra bewerkingen wilt uitvoeren naast het omkeren van de lijst, kunt u door de originele lijst bladeren, de elementen aan het einde verwijderen, ze door een willekeurige methode laten gaan en ze weer aan het begin van de lijst toevoegen:

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

criterium

Dus, wat is de snelste? Dit hangt er ook van af of u de handeling ter plaatse of buiten de plaats wilt uitvoeren.

In-place omkeringsbenchmark

Laten we beide benaderingen op alle drie de methoden benchmarken, te beginnen met 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);

Dit resulteert in:

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

Wat gebeurt er als we het aantal elementen verhogen van 100 naar 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 behoudt de markering van 4 ms! De handmatige aanpak heeft de grootste tijdscomplexiteit en is lineair gestegen. Collections.reverse() minder last van opschaling, maar de implementatie van Guava het minst. Houd er echter rekening mee dat we de lijst voor de Guava-aanpak niet handmatig kopiëren. Zal de benchmark veranderen als we het idee van een "originele" en "omgekeerde" lijst laten varen?

Benchmark voor out-of-place omkering

Met 1000 elementen, en elk werkend op een niet-omgekeerde kopie van de lijst (die was uitgesloten van de tijdmetingen), wanneer we de handmatige kopie van elke methode verwijderen en de code opnieuw uitvoeren:

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 nog slaagt erin om consistent beter te presteren dan beide Collections.reverse() en de handmatige aanpak.

Conclusie

In deze korte handleiding hebt u geleerd hoe u een lijst in Java, in-place en out-of-place, omkeert, waarbij de originele lijst van de bewerking behouden blijft. We hebben de gebruikt Collections.reverse() methode, Google Guava's Lists.reverse() methode en een handmatige aanpak.