Đảo ngược một danh sách trong Java - Tại chỗ và Ngoài vị trí

Trong hướng dẫn ngắn này, bạn sẽ học cách đảo ngược danh sách tại chỗ và không đúng vị trí trong Java.

Đảo ngược tại chỗ và ngoài vị trí

Khi thực hiện các thao tác trên danh sách - bạn có thể muốn xem xét liệu các thao tác có được thực hiện tại chỗ (các thay đổi được thực hiện trên đối tượng ban đầu) hay chúng không đúng vị trí (các thay đổi được thực hiện trên bản sao và bản gốc vật không đổi).

Một số ngôn ngữ và thư viện thích các hành vi mặc định khác nhau. Trong Java, hầu hết các thao tác trên việc đảo ngược danh sách sẽ tại chỗ.

Nếu đây là hành vi mong muốn của bạn - thật tuyệt! Nếu không, bạn sẽ muốn tạo một bản sao của danh sách trước khi đảo ngược bản sao:

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

Lưu ý: Sản phẩm clone() phương pháp không tạo một bản sao sâu. Tạo danh sách bằng cách sử dụng new ArrayList(list) không tạo một bản sao sâu. Tạo bản sao sâu không được khuyến khích và rất khó thực hiện theo cách chung chung (và không có ý nghĩa trong một số trường hợp, tùy thuộc vào (các) loại dữ liệu trong danh sách). Điều này sẽ không ngăn bạn có thể đảo ngược list và không có các yếu tố của listCopy đang bị đảo ngược, mặc dù.

Collections.reverse ()

Sản phẩm Collections.reverse() phương pháp này là phương pháp tiêu chuẩn để đảo ngược một tập hợp và đóng vai trò là phương pháp "bị thiếu" List.reverse() phương pháp. Nó đảo ngược danh sách tại chỗ:

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 (danh sách)

Nếu bạn đang sử dụng Google Guava đã có trong dự án của mình, bạn cũng có thể tận dụng Lists lớp học, cung cấp reverse() , phương thức này không sắp xếp danh sách gốc tại chỗ, nhưng tạo một bản sao và đảo ngược bản sao:

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

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

Nếu bạn chưa có, bạn có thể thêm Google Guava vào dự án của mình bằng cách sử dụng Maven, bằng cách bao gồm sự phụ thuộc của nó vào pom.xml tập tin:

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

Hoặc qua Gradle:

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

Lưu ý: Nếu bạn chưa có Google Guava hoặc không có ý định sử dụng nó cho các phần khác trong dự án của mình - đừng nhập nó chỉ cho thao tác này và hãy tuân theo Collections.reverse() phương pháp. Ổi là một phụ thuộc lớn, và đó là một loại quá mức cần thiết chính chỉ sử dụng nó cho hoạt động này.

List.add () và List.remove ()

Nếu bạn muốn thực hiện các thao tác bổ sung ngoài việc đảo ngược danh sách - bạn có thể lặp lại danh sách ban đầu, xóa các phần tử ở cuối, chuyển chúng qua một phương thức tùy ý và thêm chúng trở lại ở đầu danh sách:

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

điểm chuẩn

Vì vậy, đó là nhanh nhất? Điều này cũng phụ thuộc vào việc bạn muốn thực hiện thao tác tại chỗ hay không.

Điểm chuẩn đảo ngược tại chỗ

Hãy đánh giá cả hai phương pháp tiếp cận trên cả ba phương pháp, bắt đầu với những điểm không phù hợp:

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

Kết quả này trong:

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

Điều gì xảy ra khi chúng ta tăng số phần tử từ 100 lên 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, ...

Ổi vẫn giữ được mốc 4ms! Phương pháp thủ công có độ phức tạp về thời gian tồi tệ nhất và nó tăng tuyến tính. Collections.reverse() ít bị ảnh hưởng hơn từ việc mở rộng quy mô, nhưng việc triển khai Guava ít bị ảnh hưởng nhất. Mặc dù vậy, hãy nhớ rằng chúng tôi không sao chép danh sách theo cách tiếp cận Guava theo cách thủ công. Liệu điểm chuẩn có thay đổi khi chúng ta từ bỏ ý tưởng có danh sách “ban đầu” và “đảo ngược” không?

Điểm chuẩn đảo ngược không đúng vị trí

Với 1000 phần tử và mỗi phần tử hoạt động trên một bản sao không đảo ngược của danh sách (đã bị loại trừ khỏi các phép đo thời gian), khi chúng tôi xóa bản sao thủ công khỏi mỗi phương pháp và chạy lại mã:

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

Trái ổi vẫn còn quản lý để luôn làm tốt hơn cả hai Collections.reverse() và cách tiếp cận thủ công.

Kết luận

Trong hướng dẫn ngắn này, bạn đã học cách đảo ngược một danh sách trong Java, tại chỗ và ngoài vị trí, bảo toàn danh sách ban đầu khỏi thao tác. Chúng tôi đã sử dụng Collections.reverse() phương pháp, Google Guava's Lists.reverse() phương pháp và cách tiếp cận thủ công.