Информатика --- наука экспериментальная?

0

0

Стандартная библиотека 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>>.

Выходит информатика --- наука экспериментальная, профайлер силнее Кнута :)

Ссылка

←	Битые диски в linuxcenter.ru

LOL :)))

→

а ты думал...

тезис Чарча слыхал? его никто не доказал, но никто и не опровергнул, а информатика как наука тока на нем и основона - весь бардак от туда пошёл.

Pi ★★★★★
(12.10.05 23:28:59 MSD)

Ответ на: комментарий от Pi 12.10.05 23:28:59 MSD

Не Чарча, а Черча. Доказать его впринципе невозможно да и не надо ето. Как, например, не надо физику доказывать, что окружающая реальность, данная в ощущениях, объективно существует и вся физика вообще имеет смысл. Это как и тезис Черча-Тьюрига вопросы глубоко философско-болтологического плана.

GameMagister
(12.10.05 23:59:40 MSD)

Ответ на: комментарий от GameMagister 12.10.05 23:59:40 MSD

Хочется всё же вернутся к примеру. Он то как раз имеет не философско-болтологический характер. Речь идет о конкретных цифрах.

Я вот например доверяю ребятам писавшим Collections.java, как программистам, т.к. уверен что в данной области они разбираются получше меня. И вот такие умные ребята не нашли ничего лучшего, как подбирать константы, для того чтобы алгоритмы работали эффективно, методом тыка.

Расматриваемая задача между прочим не выглядит гиперсложной. Товарищ Кнут и иже с ним годятся только на сферических коней в ваккуме? Обычные вот инженеры когда мост проектируют, могут строго доказать что он не упадет (если его конечно путем по проекту построят). При проектировании программ подобного не наблюдается :(