Tại sao điền(), sao chép(), reverse() và shuffle() của bộ sưu tập trong java được thực hiện theo cách này

Question

Theo javadoc ... Collections.fill() được viết như sau:

public static <T> void fill(List<? super T> list, T obj) { 
     int size = list.size(); 

     if (size < FILL_THRESHOLD || list instanceof RandomAccess) { 
      for (int i=0; i<size; i++) 
       list.set(i, obj); 
     } else { 
      ListIterator<? super T> itr = list.listIterator(); 
      for (int i=0; i<size; i++) { 
       itr.next(); 
       itr.set(obj); 
      } 
     } 
    } 

Dễ hiểu tại sao họ không sử dụng listIterator cho

if (size < FILL_THRESHOLD || list instanceof RandomAccess) 

điều kiện là của RandomAccess. Nhưng whats việc sử dụng size < FILL_THRESHOLD ở trên?

Ý tôi là có lợi ích hiệu suất đáng kể nào khi sử dụng iterator cho size>=FILL_THRESHOLD chứ không phải cho size < FILL_THRESHOLD?

Tôi thấy phương pháp tương tự cho Collections.copy() cũng:

public static <T> void copy(List<? super T> dest, List<? extends T> src) { 
     int srcSize = src.size(); 
     if (srcSize > dest.size()) 
      throw new IndexOutOfBoundsException("Source does not fit in dest"); 

     if (srcSize < COPY_THRESHOLD || 
      (src instanceof RandomAccess && dest instanceof RandomAccess)) { 
      for (int i=0; i<srcSize; i++) 
       dest.set(i, src.get(i)); 
     } else { 
      ListIterator<? super T> di=dest.listIterator(); 
     ListIterator<? extends T> si=src.listIterator(); 
      for (int i=0; i<srcSize; i++) { 
       di.next(); 
       di.set(si.next()); 
      } 
     } 
    } 

FYI:

private static final int FILL_THRESHOLD   = 25; 

private static final int COPY_THRESHOLD   = 10; 

Cùng tiếp cận cho dưới đây:

public static void reverse(List<?> list) 
public static void shuffle(List<?> list, Random rnd) 

EDIT:

Sự nhầm lẫn của tôi là dành cho phần size<FILL_THRESHOLD, không phải cho RandomAccess

Answer 1

Tôi đoán đây là vì danh sách chung không có nghĩa là ArrayList. Không có gì đảm bảo rằng việc thiết lập chỉ mục ngẫu nhiên được thực hiện trong thời gian O (1) liên tục. Đồng thời xây dựng một iterator và làm việc trên nó có chi phí của nó.

Để kết luận cho các danh sách nhỏ, bạn có thể hy sinh thực tế rằng việc sử dụng trình lặp sẽ mang lại độ phức tạp thấp hơn để truy cập các phần tử liên tiếp, bằng cách tiết kiệm phí tạo bản thân trình lặp.

Điều này bởi vì list.set(i, obj) có thể đắt hơn sau đó itr.set(obj) nhưng trong trường hợp thứ hai, bạn sẽ có chi phí tiềm ẩn của việc quản lý trình lặp. Vì sự phức tạp có thể là tuyến tính O (n), sử dụng list.set(i, obj) cho các danh sách lớn hơn có thể là một vấn đề có hiệu quả.

Answer 2

Java 1.2, trong đó giới thiệu khuôn khổ bộ sưu tập, và Java 1.3 sử dụng cách tiếp cận đơn giản với một ListIterator:

public static void fill(List list, Object o) { 
    for (ListIterator i = list.listIterator(); i.hasNext();) { 
     i.next(); 
     i.set(o); 
    } 
} 

Các ngưỡng đã được giới thiệu cùng với giao diện RandomAccess marker trong Java 1.4 (tất cả dựa trên mã di sản cho JDK từ trang web của Oracle).

Tôi nghĩ rằng đây là một thuật toán thu thập rác tối ưu hóa cũ hơn - những thuật toán cũ hơn này đã thay đổi heavy penalties for creating a new object (chẳng hạn như Trình kiểm tra ListIterator). Do đó, sử dụng các bộ định tuyến cho các danh sách không phải là O (1).

Thay vì trớ trêu thay, Java 1.4.1 đã giới thiệu một bộ thu gom rác mới giúp tạo đối tượng rẻ hơn nhiều đối với các đối tượng sống ngắn chẳng hạn như trình lặp.