Стандартная библиотека java
java/util/Collections.java
Сначала коммент (который как известно рулит)
/*
* Tuning parameters for algorithms - Many of the List algorithms have
* two implementations, one of which is appropriate for RandomAccess
* lists, the other for "sequential." Often, the random access variant
* yields better performance on small sequential access lists. The
* tuning parameters below determine the cutoff point for what constitutes
* a "small" sequential access list for each algorithm. The values below
* were >>>empirically determined<<< to work well for LinkedList. Hopefully
* they should be reasonable for other sequential access List
* implementations. Those doing performance work on this code would
* do well to validate the values of these parameters from time to time.
* (The first word of each tuning parameter name is the algorithm to which
* it applies.)
*/
Далее следуют собственно <<empirically determined>> константы, которые надо понимать ограничивают область применения (эффективную) тех или иных алгоритмов в зависимости от количества элементов коллекции:
private static final int BINARYSEARCH_THRESHOLD = 5000;
private static final int REVERSE_THRESHOLD = 18;
private static final int SHUFFLE_THRESHOLD = 5;
private static final int FILL_THRESHOLD = 25;
private static final int ROTATE_THRESHOLD = 100;
private static final int COPY_THRESHOLD = 10;
private static final int REPLACEALL_THRESHOLD = 11;
private static final int INDEXOFSUBLIST_THRESHOLD = 35;
Применяется это дело так (пример взят тамже):
public static int binarySearch(List list, Object key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return indexedBinarySearch(list, key);
else
return iteratorBinarySearch(list, key);
}
Всё это конечно замечательно, но почему private static final int BINARYSEARCH_THRESHOLD = 5000, а не 4000, а может 6000.
А, понятно <<empirically determined>>.
Выходит информатика --- наука экспериментальная, профайлер силнее Кнута :)