К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 46
Текст из файла (страница 46)
Сортировка и поиск". Прошло полвека. Процессорные мощности за это время необычайно возросли, но ситуация с сортировкой навряд ли значительно улучшилось. Так, на АМП АгЫоп 1050 МГц упорядочивание миллиона чисел одним из лучших алгоритмов сортировки — цц|ск зон — занимает 3,6 с, а десяти миллионов — уже свыше половины минуты (рис. 2.52).
Сортировка сотен миллионов чисел вообше требует астрономического количества времени. И это при том, что сортировка — одна из наиболее распространенных операций, встречающихся буквально повсюду. Рис. 2.52. Время сортировки различного количества чисел алгоритмами Еыск зог1 и Гюеаг зогт Конечно, потребность в сортировке сотен миллионов чисел есть разве что у ученых, моделируюших движения звезд в галактиках или расшифровываюших геном, но ведь и в бизнес-приложениях таблицы данных с сотнями тысяч записей — не редкость! Причем, к производительности интерактивных приложений предъявляются весьма жесткие требования — крайне желатель- Оперативная память но, чтобы обновление ячеек таблицы происходило параллельно с работой пользователя, т.
е. осуществлялось налету. Алгоритму быстрой сортировки требуется 0(п'1я и) операций в среднем и 0(пг) в худшем случае. Это действительно очень быстрый алгоритм, который вряд ли можно значительно улучшить. Действительно, нельзя. Но надо! Вспомните "Понедельник начинается в субботу" братьев Стругацких: "Мы сами знаем, что она [задача1 не имеет решения, — сказал Хунта, немедленно ошетинившись. — Мы хотим знать, как ее решать". Ведь существует же весьма простой и эффективный алгоритм сортировки, требуюший в худшем случае порядка 0(п) операций.
Нет, это не шутка и не первоапрельский розыгрыш! Такой алгоритм действительно есть. Так, на компьютере АМ0 Аг!з(оп 1050 он упорядочивает десять миллионов чисел всего за 0,3 с, что в сато раз быстрее алгоритма г!и!ск хоп! Впервые с этим алгоритмом мне пришлось столкнуться на олимпиаде по информатике, предлагающей в одной из задач отсортировать семь чисел, используя не более трех сравнений. Решив, что по такому поводу не грех "малость повыпендриваться", я быстро написал программку, которая выполняла сортировку, не используя вообще аи одного сравнения. К сожалению, по непонятным для меня причинам решение зачтено не было„и только спустя пару лет, изучив сушествуюшие алгоритмы сортировки, я смог оценить нетривиальность полученного результата.
Собственно, вся идея заключалась в том, что раз неравенство к + 1 > к > > к — 1 справелливо для любых к, то можно сопоставить каждому числу й„ соответствуюшую ему точку координатной прямой, и в итоге мы получим "естественным образом" отсортированную последовательность точек. Непонятно? Давайте разберем это на конкретном примере. Пусть у нас имеются числа 9, 6, 3 и 7. Берем первое из них — 9 — отступаем вправо на девять условных единиц от начала координатной прямой и делам в этом месте зарубку. Затем берем следующее число — б и повторяем с ним ту же самую операцию... В конечном счете у нас должно получиться приблизительно следующее (рис.
2.53). А теперь давайте, двигаясь по координатной прямой слева направо просто выкинем все неотмеченные точки (или, иначе говоря, вылелим отмеченные). У нас получится последовательность чисел, упорядоченная по возрастанию! Соответственно, если двигаться по прямой справа налево, мы упорядочим числа по убыванию. И вот тут мы подходим к самому интересному! Независимо от расположения сортируемых чисел, количество операций, необходимых для их упорядочивания, всегда равно: Х + ЧА(. 19, где Н вЂ” количество сортируемых чисел, а ЧАЬ г( — наибольшее количество значений, которые могут прини- гзг Глава Я мать эти числа. Поскольку ЧА),Х вЂ” константа, из формулы оценки сложности алгоритма ее можно исключить и тогда она (формула сложности) будет выглядеть так: 0()х)).
%ОМ У вас уже чешутся руки создать свою первую реализацию? Что ж, это нетрудно. Заменим числовую ось одномерным массивом и вперед (листинг 2.43). Рис. 2.53. Сортировка методом отображения збетзпе ТОГ 1 збеггпе МОООТ О 1пс а: 1пг згс[Н); апв соогб1паое 11пе)УВ). Щ; вевзес)соогб1пахе 1гпе, НОООТ, УЯЬ М*з1геог)гпв)) // ставим на прямой зарубки в нузвых местах Тог )а = О; а < я; аа+) соогб1пате 11пе(згс)а))=ООТ; // просматриваем прямую справа налево в поисках зарубок // все "зарубленнме" точки копируем в исхолньй массив Тот)а = О; а < и ум.; ат+) гв )соогб1паге 11пе)а]) ( *згс = а; згсн;) Ага! Вы уже заметили один недостаток этой реализации алгоритма? Действительно, побочным эффектом такой сортировки становится отсечение всех "дублей", т.
е. совпадаюших чисел. Возьмем, например, такую последовательност)и 3, 9, 6, 6, 3, 2, 9. После сортировки мы получим: 2, 3„6, 9. Знаете, а с одной стороны это очень даже хорошо! Ведь зачастую "дубли" совершенно не нужны и только снижают своим "хламом" производительность. Оперативная память 233 Хорошо„а как быть, если уничтожение дублей в таком-то конкретном случае окажется неприемлемо? Нет ничего проще — достаточно лишь слегка модифицировать наш алгоритм, не просто ставя зарубку на координатной прямой, а еще и подсчитывая их количество в соответствуюшей ячейке массива.
Усовершенствованный вариант реализации может выглядеть, например, так, как показано в листинге 2.44. гпт* 11пеаг вогт(тпт *р, гпт и] ( гпг то апт а, Ь; гпт сопле = О; гпт *соагпгпате 11пе; // массив для сортировки // выделяем память соогагпате 11пе = иа11ос(тАЬ МАХ*еггеот Сгпт]]; 1г ((соогегпаге 11пе] /* недостаточна паыяти */ гегпгп О( // гп1Г векаег(сооге1пасе 11пе, О, тдь мдх*а1геог ганг]]; // сортировка Гог(а = О; а < и; а++] соогсгпате 11пе[р[а]]++; // формирование ответа Гог(а = О; а < тдь МАХ~ ат+] гог(ь О( ь < соогсцпаге 1гпе[а]( ь+ь] р[сонпстт]=а( // освобркпаем память Ггее(соогагпасе 11пе]; гегогп р1 (Полный исходный текст программы читатель найдет в файле ~згс~Я2].п(ешогу~воггй(пеаг.с, который находится на прилагаемом компактдиске.) Давайте сравним его с алгоритмом г]шс][ зог( при различных значе- Глава 2 гз4 ниях М и посмотрим, насколько он окажется эффективен.
Эксперименты, проведенные автором, показали, что даже такая примитивная реализация линейной сортировки намного превосходит алгоритм йшсй зоп и при малом, и при большом количестве сортируемых значений (рис. 2.54). Рис. 2.54. Превосходство линейной сортировки над Оысх воп. Смотрите, линейная сортировка двух миллионов чисел (вполне реальное количество, правда) выполняется в двести пятьдесят рвз быстрее! Причем, этот результат можно существенно улучшить, если прибегнуть к уСЛУГВМ РВЗРЯЖСННЪ|Х МВССИВОВ, а НС ТУПО СКВНИрОВатЬ МВССИВ чтттоа! актау целиком! Но не все же время говорить о хорошем! Давайте поговорим и о печальном.
Увы, за быстродействие в данном случае приходится платить оперативной памятью. Алгоритм линейной сортировки "пожирает" ее прямо-таки в чудовищных количествах. Вот приблизительные оценки. Очевидно, количество ячеек массива ссстшпасе ыпе равно количеству значений, которые могут принимать сортируемые данные. Для 8-битных типов сьвт это составляет 2В = 256 ячеек, для )б- и 32-битных тят — 2)Ь = 65 536 и Оперативная память 235 212 = 4 294 967 296 соответственно. С другой стороны, каждая ячейка массива ссссегсасе 1зсе должна вмещать в себя максимально возможное количество дублей, что в худшем случае составляет число Х. Таким образом, в большинстве ситуаций под нее следует отводить не менее 16, а лучше все 32 бита.
Учитывая это, составляем следующую нехитрую табличку (табл. 2.5). Таблица 2.5. Количество памяти, потребляемой алгоритмом линейной сортировки при упорядочивании данных различного типа Кол-во требуемой памяти Тип данных при сохранении дублей без сохранения дублей 1 Кбайт 512 байт 256 Кбайт 128 Кбайт 16 Гбайт 8 Гбайт 32 байта 16 байт 8 Кбайт 4 Кбайт 1 Гбайт 256 Кбайт скат сь (без учета знака) зсш 6 зсе т ь (без учета знака) гсезг зсезг (без учета знака) Ничего себе потребности! Для сортировки 32-разядных элементов с сохранением "дублей" потребуется 8 Гбайт оперативной памяти! Конечно, 99,999% ячеек памяти будут пустовать и потому подкачка страниц с диска не сильно ухудшит производительность, но вся проблема как раз и заключается в том, что нам просто не дадут этих 8 Гбайт.
Операционные системы 9У!пиотта 9х/)МТ ограничивают адресное пространство процессора всего 4 Гбайт, причем больше двух из них расходуется на "служебные нужны" и максимально доступный объем "кучи" составляет 1 — 1,5 Гбайт. Правда, можно поровну распределить массив сс в сс г между восемью процессами (ведь возможность читать и писать в "чужое" адресное пространство у нас есть — см. описания функций аеаегтоссззиетсту и ит сьг *зн у в Р!агГопп ВРК). Конечно, это очень "кривое" и уродливое решение, но зато крайне производительное. Пусть за счет накладных расходов на вызов АР1-функций алгоритм линейной сортировки превзойдет алгоритм г)ц)с)г зон не в сто, а в шестьдесят-девяносто раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
