爲什麼填（），複製（），反向（），並在Java集合洗牌（）來實現這樣

根據的Javadoc ... Collections.fill（）寫如下：爲什麼填（），複製（），反向（），並在Java集合洗牌（）來實現這樣

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

它容易理解爲什麼他們沒有使用listIterator for

if (size < FILL_THRESHOLD || list instanceof RandomAccess)

條件截至RandomAccess。但是在上面使用size < FILL_THRESHOLD是什麼？

我的意思是使用iterator代替size>=FILL_THRESHOLD而不是代替size < FILL_THRESHOLD有什麼顯着的性能優勢？

我看到Collections.copy（同樣的方法）也：

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;

下面同樣的方法：

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

編輯：

我的困惑是size<FILL_THRESHOLD的一部分，而不是RandomAccess

來源

2012-09-05 Priyank Doshi

您是否感到困惑，因爲存在兩種不同的閾值？ – Mirko

@Mirko：完全不是因爲這個。我可以很好地理解，這兩種方法都有不同的要求。因此，兩種不同的閾值是合理的。 –

我想這是因爲通用的清單並不意味着是一個ArrayList。不能保證在常數O（1）時間內設置隨機索引。同時構建一個迭代器並對其進行處理有其開銷。

最後，對於小列表，您可以犧牲這樣的事實：使用迭代器可以降低訪問連續元素的複雜度，從而節省創建迭代器本身的開銷。

這是因爲list.set(i, obj)可能會更貴，然後itr.set(obj)，但在後者，你將有隱含的管理迭代器的開銷。由於複雜性可能是線性的，所以對於較大的列表使用list.set(i, obj)可能是有效的問題。

來源

2012-09-05 03:40:32 Jack

我想他們在基準測試LinkedList（JDK中的其他List實現）如何運行之後，得出了這些閾值的值。 – Thilo

_「不能保證訪問隨機索引是在常量O（1）時間內完成的，」這是真的，但[RandomAccess標記接口]（http://docs.oracle.com/javase/7/ docs/api/java/util/RandomAccess.html）在'List'實現中指示_「[該實現]支持快速（通常爲恆定時間）的隨機訪問。」＃ –

@Matt Ball：是的，但我們在這裏說關於它不是RandomAccess的情況。對於RandomAccess，從不使用迭代器。 – Thilo

爪哇1.2，它介紹了收集框架和Java 1.3中使用的簡單的方法用的ListIterator：

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

這些閾值被一起用Java 1.4 RandomAccess標記接口導入（全部基於遺留代碼來自Oracle網站的JDK）。

我認爲這是一個優化的較舊的垃圾收集算法 - 這些較老的算法有heavy penalties for creating a new object（如ListIterator）。因此，對非O（1）列表使用setter是有意義的。

而諷刺的是，的Java 1.4.1引入了一個新的垃圾收集器是由對象創建了短暫的對象便宜得多，如迭代器。

來源

2012-09-05 05:50:45

爲什麼填（），複製（），反向（），並在Java集合洗牌（）來實現這樣

回答

相關問題