一、導火索
在看Zookeeper sourcecode的時候,發現server端的NIO*Factory 在channel上擷取完SelectionKey清單後,進行了一個shuffle的操作保證公平性,code as followed:
ArrayList<SelectionKey> selectedList = new ArrayList<SelectionKey>(selected);
Collections.shuffle(selectedList);
for (SelectionKey k : selectedList) {
....
}
說實話,對于我這樣的資深工程師來說以前從沒用過這個方法,來看看它是幹什麼的
/**
* Randomly permutes the specified list using a default source of
* randomness. All permutations occur with approximately equal
* likelihood.
(大緻就是說它可以随機的交換list的元素,所有交換的可能性大緻是相等的)
* If the specified list does not
* implement the {@link RandomAccess} interface and is large, this
* implementation dumps the specified list into an array before shuffling
* it, and dumps the shuffled array back into the list. This avoids the
* quadratic behavior that would result from shuffling a "sequential
* access" list in place.
*/
Note that,如果list沒有實作RandomAccess interface 或者list比較大,那麼它會将list convert to 一個array然後進行shuffle,最後在dump回list裡,為什麼要這麼搞呢,因為這樣可以避免二次行為 (相信很多人實際操作中第一想法會直接loop list元素,然後随機交換元素,這就是base knowledge不足啊)
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {//list比較小或者實作了RandomAccess接口,則直接搞就行了.
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray();
// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));
// Dump array back into list
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
why?
看看RandomAccess,我挑幾句注釋來說明
/**
* Generic list algorithms are encouraged to check whether the given list is an <tt>instanceof</tt> this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list,
* and to alter their behavior if necessary to guarantee acceptable
* performance.
*
* <p>It is recognized that the distinction between random and sequential
* access is often fuzzy. For example, some <tt>List</tt> implementations
* provide asymptotically linear access times if they get huge, but constant
* access times in practice. Such a <tt>List</tt> implementation
* should generally implement this interface. As a rule of thumb, a
* <tt>List</tt> implementation should implement this interface if,
* for typical instances of the class, this loop:
* <pre>
* for (int i=0, n=list.size(); i < n; i++)
* list.get(i);
* </pre>
* runs faster than this loop:
* <pre>
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
* </pre>
*/
JDK建議我們如果是random access list,則用for(int i=0;i<list.size();i++){} 如果是sequence access list則用Iterator。因為最佳的方式就是用list instanceof RandomAccess來決定具體的算法.
其實資料比較大的時候,二者的效率還是有一定差距的.
JDK的source code還是值得去細細品味的