Показаны сообщения с ярлыком алгоритмы. Показать все сообщения
Показаны сообщения с ярлыком алгоритмы. Показать все сообщения

понедельник, 4 июля 2011 г.

Порядки роста на примерах

В теории все знают, какие бывают функции порядка роста, основные из них: c, nx, x^a, a^x, x!, lg(x), x*lg(x). Но вот в собственном исходнике определить верхнюю границу тормознутости алгоритма иногда не так просто. Поэтому приведу примеры на некоторые из них. Примеры привожу на java, т.к. на ней проще воспринимаются императивные конструкции.

С -- константное время, характерно для неповторяющихся операций.

nx -- линейная зависимость; пример -- одиночный цикл. Встречается при обработке векторов.

x^a -- степенная зависимость.
Пример для a=3, x=2.
int x = 2;
for (int i = 0; i < x; i++)
  for (int j = 0; j < x; j++)
     for (int k = 0; k < x; k++)
         System.out.print("@");
Степенной порядок роста легко обнаружить по нескольким вложенным циклам, максимальный размер каждого из которых не превышает х. Встречается в простых алгоритмах сортировки, обработки матриц и т.д.

a^x -- экспоненциальная зависимость.
Пример для а=2, х=3:
public static void expFunc(int a, int n) {
    System.out.print("!");

    for (int i = 1; i <= a; i++) {
        if (n > 1) {
            expFunc(a, n-1);
        }
    }
}

public static void main(String[] args) {
    System.out.print("!");
    expFunc(2,3);
}
Признаком экспоненциального роста является количество вложенных циклов, зависящее от переменной х; количество итераций внутри цикла не должно превышать константу а. Встречается при обработке всех подмножеств, некоторого множества, состоящего из х элементов.

x! -- факториал. Пример: найти все перестановки множества элементов {1,2,3}.
public static int X[] = new int[100];
public static int N = 3;

public static void Swap(int a, int b) {
    int t = X[a];
    X[a] = X[b];
    X[b] = t;
}

public static void printX() {
    for (int i = 0; i < N; i++) {
        System.out.print(X[i]);
        System.out.print(" ");
    }
    System.out.println("");
}

public static void Generate(int k) {
    if (k == N) {
        printX();
    } else {
        for (int j = k; j < N; j++) {
            Swap(k, j);
            Generate(k + 1);
            Swap(k, j);
        }
    }
}

public static void main(String[] args) {
    int i;
    for (i = 0; i < N; i++) {
        X[i] = i + 1;
    }
    Generate(0);
}
Встречается, обычно, именно при генерировании всех перестановок. Такая зависимость похожа на экспоненциальную в том, что количество вложенных циклов зависит от переменной х, но количество итераций на каждом уровне вложенности уменьшается на 1, что приводит нас к формуле факториала: x! = x*(x-1)*(x-2)*...*2*1

log(n) -- логарифмическая зависимость. Характеризуется скоростью роста большей, чем у константы, но меньшей, чем у линейной зависимости. Т.е., если дан массив размера N, то при алгоритме с логарифмическим порядком роста обработаны будут не все элементы массива, а только часть из них. Признаком такой зависимости является уменьшение объема задачи на некоторый множитель на каждом шаге итерации.

Пример: задача с фальшивой монетой. Дано N монет, одна из которых (фальшивая) -- легче других. Необходимо найти фальшивую монету при помощи весов рычажных весов.
Алгоритм решения задачи прост: все монеты делятся на две одинаковые кучи, взвешиваются, выбирается та, что легче. Затем эта куча делится на две меньшие кучи  т.д. до тех пор, пока не будет найдена фальшивая монета. В случае, если количество монет нечетное, то одну монету временно изымают. Если кучи равны по весу, то изъятая монета и есть фальшивая.

В приведенном примере задача каждый раз уменьшается вдвое; но даже с самого начала необходимо перебрать не все элементы, а максимум -- N/2 +1.

x*lg(x) -- порядок роста выше чем у линейной зависимости, но ниже, чем у квадратичной (x^2). Встречается в алгоритмах декомпозиции ("разделяй и властвуй"), например, при сортировке слиянием и в quicksort-е.

Использованная литература: "Алгоритмы. Введение в разработку ", А.Левитин, Москва, 2006, с.94-95.

Предлагаю добавить в комментах свои примеры на различные порядки роста.

суббота, 23 апреля 2011 г.

Тест производительности (updation 2)




Решил протестировать производительность различных языков программирования на факториале от 50000, и вот что у меня получилось.

Scheme (racket 5.1) – 8s
Clojure 1.2 – 23s
Java 1.7 – 17s
Sbcl 1.0.43 – 7s
Ruby 1.9.2 -- 10s.
Parallel Clojure -- 3s.

Функция на Clojure выглядит следующим образом.

(defn fact!
  ([num]
    (fact! num 1))
  ([num result]
    (if (zero? num)
      result
      (recur (dec num) (* result num)))))

Ответ на функцию (fact! 50000) не привожу, потому что он занимает в OpenOffice 52 страницы шрифтом Liberation Serif 12.

Вывод из этого эксперимента следующий: самый быстрый язык для вычислений с большими числами в одном потоке – это Common Lisp (sbcl). С/C++ в расчет не берем, т. к. в его стандарте вообще нет средств для работы с числами такого размера. Java более чем в два раза медленнее; реализация алгоритма факториала не через рекурсию, а с помощью цикла. Это связано с тем, что в Java нет оптимизации хвостовой рекурсии, и рекурсивная реализация на Java просто вылетает с ошибкой StackOverflow. Хотя все реализации осуществляют именно итеративный процесс.
Clojure на 35% медленее Java, но тоже, в принципе, достаточно быстр.
Racket, запущенный без дебужных опций, оказался тоже достаточно шустрым и справился с заданием всего за 8 секунд, заняв почетное второе место. На третьем месте -- Ruby 1.9.2.

По предложению Vinzent'а,  решил протестировать еще и параллельную реализацию на Clojure. Учитывая, что "параллельность" в Clojure из коробки, сделать это оказалось очень просто. Vinzent прислал очень идиоматичный исходник, за что большое ему спасибо. Привожу его (исходник) ниже.

Результат вычислений был выше всяких похвал. Clojure справился с факториалом 50000 всего за 3 секунды!

(defn chunks [x n]
  (take n
    (partition 2 1
           (iterate
              (partial + (/ x n)) 1))))

(defn pfact [chunks]
  (reduce * (pmap
         (fn [[from to]]
           (reduce * (range from to)))
         chunks)))

(time (pfact (chunks 50000 10)))

воскресенье, 23 января 2011 г.

Поиск файлов на Clojure


Решил на днях написать на Clojure утилиту поиска файлов по шаблону – аналог утилиты find. Это один из классических учебных примеров, который пишут при изучении нового языка. Основная процедура по поиску файлов выглядит так.

(defn find-files [matcher-func directory]
   (if (or (nil? directory) (nil? matcher-func))
     nil
     (let [current (File. directory)
            cur-list (seq (.list current))
            dirs (filter #(and (not (= % ".")) (not (= % "..")))
                    (filter #(.isDirectory (File. (concat-dirs directory %))) cur-list))
            files (filter #(.isFile (File. (concat-dirs directory %))) cur-list)
            found (vec (map #(concat-dirs directory %)
                              (filter #(matcher-func %) files)))]
    (loop [d dirs
               f found]
      (if (or (nil? d) (empty? d))
        f
        (recur (next d)
                   (join f (find-files matcher-func
                                              (concat-dirs directory (first d))))))))))

В current создается объект File с указанной директорией; cur-list содержит список всех файлов и поддиректорий в указанной директории; dirs содержит только поддиректории; files – только файлы указанной директории; found – только файлы, совпавшие с указанным регулярным выражением. В цикле loop для каждой поддиректории запускается эта же функция find-files, а результат накапливается в переменной f. Когда цикл закончится, функция вернет вектор всех найденных файлов.
Здесь не показаны функции concat-dirs (соединение базовой директории с поддиректорией или файлом при помощи File.separator), matcher-func (функция содержит откомпилированный Pattern для сравнения с именем файла) и join, которая объединяет элементы двух векторов в один.
Впринципе, функция работает хорошо и находит файлы довольно шустро. Но Clojure знаменит тем, что в нем concurrency работает «из коробки», поэтому хотелось бы как-нибудь ее распараллелить.
Например, можно было бы поиск файлов в каждой директории выполнять в отдельном параллельном потоке. Но что будет, если директорией значительно больше, чем ядер процессора? Значительное время уйдет на коммуникацию между потоками и на переключение между ними. Поэтому я решил в отдельный поток пускать только процесс сравнения файлов с заданным шаблоном. Изменить в исходники пришлось совсем немного.

(defn find-files [matcher-func directory]
   (if (or (nil? directory) (nil? matcher-func))
     nil
     (let [current (File. directory)
            cur-list (seq (.list current))
            dirs (filter #(and (not (= % ".")) (not (= % "..")))
                   (filter #(.isDirectory (File. (concat-dirs directory %))) cur-list))
            files (filter #(.isFile (File. (concat-dirs directory %))) cur-list)
            found (future (vec (map #(concat-dirs directory %)
                                          (filter #(matcher-func %) files))))]
    (loop [d dirs
               f []]
      (if (or (nil? d) (empty? d))
        (join f @found)
        (recur (next d)
                   (join f (find-files matcher-func
                                             (concat-dirs directory (first d))))))))))

Как видите, главное изменение в том, что теперь в переменной found содержится не мгновенно вычисленный список совпавших с шаблоном файлов, а объект «future», который вычисляет этот список в отдельном потоке. В тот момент, когда нужно получить вычисленное значение, обращаться нужно к переменной так: @found. При таком обращении к переменной found, Clojure заблокирует текущий поток до вычисления future. Впрочем, на большом количестве директорий и файлов, вряд ли когда-либо приходится включать блокировку; в большинстве случаев этот параллельный поток по поиску файлов завершается раньше основного.
Весь исходник программы можно посмотреть здесь: https://gist.github.com/792198 .
Интересно было сравнить производительность моей программы с существующими. Для сравнения я использовал поиск на большом количестве файлов и директорий при помощи следующих утилит: Nautilus 2.32.0, find 4.4.2, find-file-st – первая, однопоточная версия программы на clojure; find-file-mt – вторая, многопоточная версия. Сравнение проводил на ноутбуке Acer Aspire 5745G, Ubuntu 10.10 (32-битная). Искал по паттерну «A.*» среди залежей своих книжек, сгруппированных по темам.

Получилось вот что:


Nautilus Find-file-st Find-file-mt Find
2min 20sec 34sec 18sec 2sec




Любопытно отметить следующее. Утилита find является однопоточной (по крайней мере мне не удалось найти упоминание создания потоков в ее исходниках), но явно очень круто оптимизированной. Никаких других объяснений ее волшебной скорости я не нашел.
Nautilus же поиск выполняет во многопоточном режиме, при том судя по всему на каждую директорию он создает отдельный поток (проверял в htop-е). В результате отвратительной реализации поиска, Nautilus значительно отстает по скорости не только от find, но даже от однопоточной версии моей программы, работающей, кстати, под jvm.
В общем, разрабатывать конкурентные программы на clojure удобно и быстро.