Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Бишоп Д. -> "Эффективная робота Java 2" -> 237

Эффективная робота Java 2 - Бишоп Д.

Бишоп Д. Эффективная робота Java 2 — Спб.: Питер, 2002. — 592 c.
ISBN 966-552-107-1
Скачать (прямая ссылка): effektivnayarabotajava2002.djvu
Предыдущая << 1 .. 231 232 233 234 235 236 < 237 > 238 239 240 241 242 243 .. 259 >> Следующая

Сравнение алгоритмов сортировки
Рассмотрим сортировку методом отбора (она изучалась в разделе 6.4). Внешний цикл доходит до индекса п—1 и предусматривает п— I обменов. Внутренний цикл проходит от крайнего левого значения до л—1 и после каждого повторения цикла уменьшается на один пункт. Следовательно, количество сравнений равно:
Для простоты мы игнорируем коэффициенты в формуле, вычисляющей количество обменов, и принимаем, что оно приблизительно равно п2. Если мы добавим количество обменов к количеству сравнений, то весь процесс также можно приблизительно принять, как насчитывающий л2 выполненных операций.
С другой стороны, сортировка Quicksort использует алгоритм разделения, который предусматривает приблизительно logi повторений (проходов цикла). При каждом повторении выполняется п сравнений и приблизительно л/6 обменов. Поэтому считается, что алгоритм Quicksort работает со скоростью, пропорциональной fllog2fl. Но как реально сравнить эффективность его работы с эффективностью сортировки, предусматривающей отбор? В табл. 15.2 приведены значения, вычисленные по обеим формулам для различных значений п. Различие феноменальное! Предположим, что одно повторение происходит за единицу времени, равную 1 микросекунде (10 ^с)_ Для сортировки миллиона элементов алгоритму Quicksort потребуется 20 секунд, тогда как алгоритму, предусматривающему отбор, — 11,5 дней! Интересно, что при такой длительности цикла различие между двумя методами сортировки не будет реально ощутимо до тех пор, пока количество элементов не превысит 1000. К этому моменту алгоритму, предусматривающему отбор, потребуется целая секунда, тогда как алгоритм Quicksort выполнит работу за 0,01 секунды. В интерактивной среде различие может даже остаться незамеченным.
Таблица 15.2. Сравнение скорости работы алгоритма Quicksort и алгоритма, предусматривающего отбор
(я -1) + (п -2) + (п -3)+...+ t = п(п —1)/2
= (л2 — п)/2
10 50 100 1000 10 000 100 000 1 000 ООО
100 2500 10 000 1 ООО 000 100 000 000
10 ОСЮ 000 ООО 1 000 000 000 000
30
300
700
10 000 130 000
1 600 000
20 000 000
Ускорен ноя сортировка Quicksort и эффективность работы
545
Так почему же мы постоянно не используем алгоритмі Quicksort^ Дало вьтом, чтр эффективность зависит еще и от объема памяти, ведь ІНУа-методам требуетёй,место в памяти и для инструкций, и для данных. Что касается места в памяти для инструкций, здесь особого выбора при сравнении алгоритмов нет, поскольку оба они имеют примерно одинаковое количество операторов, а вот требуемый для данных объем памяти отличается значительно. Сортировка с отбором объявляет четыре локальные переменные, которые затем использует в своей работе. Сортировка Quicksort объявляет восемь локальных переменных и параметров для каждого рекурсивного вызова. Поскольку рекурсивные вызовы помещаются в стек, то в случае сортировки миллиона элементов, Quicksort поместит в стек 160 переменных и параметров.
Увы} но даже не это является причиной относительно редкого использования Quicksort. Существует некоторая настороженность, с которой средние программисты воспринимают Quicksort, очевидно, вследствие недостаточного знания механизма рекурсии. Конечно, Quicksort не обязательно должен программироваться рекурсивно, но его нерекурсивная версия выглядит еще менее элегантной.
Сравнение алгоритмов поиска
Можно легко обнаружить, что два рассмотренных нами алгоритма поиска имеют эффективность, пропорциональную п (для линейного) и log2« (для двоичного). Здесь различие в скорости даже более радикальное, чем при сравнении алгоритмов сорти- . ровки (см. таблицу 15.3). Если применить эти цифры к реальной задаче, то поиск нужного вам номера в телефонном справочнике, насчитывающем миллион записей, при применении двоичного поиска займет только 20 повторений цикла. Понятно, что эгго несравнимо с кропотливой работой линейного поиска, который запись за записью будет проверять весь справочник.
Тоблицо 15.3, Сравнение скорости роботы линейного и двоичного алгоритмов поиска
10 О ^ ю 3
50 50 6
100 100 7
1 000 100 10
10 000 10 ООО 13
100 000 100 000 16
1 000 000 1 000 000 20
Другие алгоритмы сортировки
Алгоритмы и анализ их эффективности — большой раздел компьютерных наук, изучение которого занимает большую часть учебного процесса второго курса соответствующих колледжей. В дополнение к двум алгоритмам сортировки, упомянутым здесь, вы будете изучать и другие, такие как пузырьковый метод (очень медленный), метод сортировки слиянием и вариант древовидной сортировки (очень быстрый), а также метод сортировки “помещением в определенную нишу’\ который чрезвычайно быстр, но содержит мною операторов и переменных. Вы научитесь выбирать алгоритмы для решгатая тшнхретнои задачи и учитывать то, насколько быстро и эффективно они могут работать. Это увлекательная теми, к которой мы, объективно говоря, только прикоснулись.
Предыдущая << 1 .. 231 232 233 234 235 236 < 237 > 238 239 240 241 242 243 .. 259 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.