Совет 31. Помните о существовании разных средств сортировки

Совет 31. Помните о существовании разных средств сортировки

Когда речь заходит об упорядочении объектов, многим программистам приходит в голову всего один алгоритм: sort (некоторые вспоминают о qsort, но после прочтения совета 46 они раскаиваются и возвращаются к мыслям о sort).

Действительно, sort — превосходный алгоритм, однако полноценная сортировка требуется далеко не всегда. Например, если у вас имеется вектор объектов Widget и вы хотите отобрать 20 «лучших» объектов с максимальным рангом, можно ограничиться сортировкой, позволяющей выявить 20 нужных объектов и оставить остальные объекты несортированными. Задача называется частичной сортировкой, и для ее решения существует специальный алгоритм partial_sort:

bool qualityCompare(const Widgets lhs, const Widgets rhs) {

// Вернуть признак сравнения атрибутов quality

// объектов lhs и rhs

}

partial_sort(widgets.begin(), // Разместить 20 элементов

widgets.begin()+20, // с максимальным рангом

widgets.end(), // в начале вектора widgets

qualityCompare);

// Использование widgets

После вызова partial_sort первые 20 элементов widgets находятся в начале контейнера и располагаются по порядку, то есть widgets [0] содержит Widget с наибольшим рангом, затем следует widgets[l] и т. д.

Если вы хотите выделить 20 объектов Widget и передать их 20 клиентам, но при этом вас не интересует, какой объект будет передан тому или иному клиенту, даже алгоритм partial_sort превышает реальные потребности. В описанной ситуации требуется выделить 20 «лучших» объектов Widget в произвольном порядке. В STL имеется алгоритм, который решает именно эту задачу, однако его имя выглядит несколько неожиданно — он называется nth_element.

Алгоритм nth_element сортирует интервал таким образом, что в заданной вами позиции п оказывается именно тот элемент, который оказался бы в ней при полной сортировке контейнера. Кроме того, при выходе из nth_element ни один из элементов в позициях до п не находится в порядке сортировки после элемента, находящегося в позиции п, а ни один из элементов в позициях после п не предшествует элементу, находящемуся в позиции п. Если такая формулировка кажется слишком сложной, это объясняется лишь тем, что мне приходилось тщательно подбирать слова. Вскоре я объясню причины, но сначала мы рассмотрим пример использования nth_element для перемещения 20 «лучших» объектов Widget в начало контейнера widgets:

nth_element(widgets.begin().//Переместить 20 «лучших» элементов

widgets.beginC)+20,//в начало widgets

widgets. end(),//в произвольном порядке

qualityCompare);

Как видите, вызов nth_element практически не отличается от вызова partial_sort. Единственное различие заключается в том, что partial_sort сортирует элементы в позициях 1-20, a nth_element этого не делает. Впрочем, оба алгоритма перемещают 20 объектов Widget с максимальными значениями ранга в начало вектора.

Возникает важный вопрос — что делают эти алгоритмы для элементов с одинаковыми значениями атрибута? Предположим, вектор содержит 12 элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20 «лучших» объектов Widget будет состоять из 12 объектов с рангом 1 и 8 из 15 объектов с рангом 2. Но как алгоритмы partial_sort и nth_element определяют, какие из 15 объектов следует отобрать в «верхнюю двадцатку»? И как алгоритм sort выбирает относительный порядок размещения элементов при совпадении рангов?

Алгоритмы partial sort и nth_element упорядочивают эквивалентные элементы по своему усмотрению, и сделать с этим ничего нельзя (понятие эквивалентности рассматривается в совете 19). Когда в приведенном примере возникает задача заполнения объектами Widget с рангом 2 восьми последних позиций в «верхней двадцатке», алгоритм выберет такие объекты, какие сочтет нужным. Впрочем, такое поведение вполне разумно. Если вы запрашиваете 20 «лучших» объектов Widget, а некоторых объекты равны, то в результате возвращенные объекты будут по крайней мере «не хуже» тех, которые возвращены не были.

Полноценная сортировка обладает несколько большими возможностями. Некоторые алгоритмы сортировки стабильны. При стабильной сортировке два эквивалентных элемента в интервале сохраняют свои относительные позиции после сортировки. Таким образом, если Widget А предшествует Widget В в несортированном векторе widgets и при этом ранги двух объектов совпадают, стабильный алгоритм сортировки гарантирует, что после сортировки Widget А по-прежнему будет предшествовать Widget В. Нестабильный алгоритм такой гарантии не дает.

Алгоритм partial_sort, как и алгоритм nth_element, стабильным не является. Алгоритм sort также не обладает свойством стабильности, но существует специальный алгоритм stable_sort, который, как следует из его названия, является стабильным. При необходимости выполнить стабильную сортировку, вероятно, следует воспользоваться stable_sort. В STL не входят стабильные версии partial_sort и nth_element.

Следует заметить, что алгоритм nth_element чрезвычайно универсален. Помимо выделения n верхних элементов в интервале, он также может использоваться для вычисления медианы по интервалу и поиска значения конкретного процентиля [3]:

vector<Widget>::iterator begin(widgets.begin()); // Вспомогательные переменные

vector<Widget>: iterator end(widgets.end()); // для начального и конечного

// итераторов widgets

vector<Widget>::iterator goalPosition; // Итератор, указывающий на

// интересующий нас объект Widget

// Следующий фрагмент находит Widget с рангом median

goalPosition = begin + widgets.size()/2; // Нужный объект находится

// в середине отсортированного вектора

nth_element(begin.goalPosition.end. // Найти ранг median в widgets qualityCompare):

// goalPositon теперь указывает // на Widget с рангом median // Следующий фрагмент находит Widget с уровнем 75 процентилей

vector<Widget>::size_type goalOffset - // Вычислить удаление нужного 0.25*wdgets.size():// объекта Widget от начала

nth_element(begin,begin+goalOffset,end, // Найти ранг в

qualityCompare):// begin+goalOffset теперь

// указывает на Widget // с уровнем 75 процентилей

Алгоритмы sort, stable_sort и partial_sort хорошо подходят для упорядочивания результатов сортировки, а алгоритм nth_element решает задачу идентификации верхних п элементов или элемента, находящегося в заданной позиции. Иногда возникает задача, близкая к алгоритму nth_element, но несколько отличающаяся от него. Предположим, вместо 20 объектов Widget с максимальным рангом потребовалось выделить все объекты Widget с рангом 1 или 2. Конечно, можно отсортировать вектор по рангу и затем найти первый элемент с рангом, большим 2. Найденный элемент определяет начало интервала с объектами Widget, ранг которых превышает 2.

Полная сортировка потребует большого объема работы, совершенно ненужной для поставленной цели. Более разумное решение основано на использовании алгоритма partition, упорядочивающего элементы интервала так, что все элементы, удовлетворяющие заданному критерию, оказываются в начале интервала.

Например, для перемещения всех объектов Widget с рангом 2 и более в начало вектора widgets определяется функция идентификации:

bool hasAcceptableQualty(const Widgets w) {

// Вернуть результат проверки того, имеет ли объект w ранг больше 2

}

Затем эта функция передается при вызове partition:

vector<Widget>::iterator goodEnd = // Переместить все объекты Widget.

partton(widgets.begin(),// удовлетворяющие условию

widgets.end() ,// hasAcceptableQuality. в начало

hasAcceptableQuality); // widgets и вернуть итератор

// для первого объекта.

// не удовлетворяющего условию

После вызова интервал от widgets.begin() до goodEnd содержит все объекты Widget с рангом 1 и 2, а интервал от goodEnd до widgets.end() содержит все объекты Widget с большими значениями ранга. Если бы в процессе деления потребовалось сохранить относительные позиции объектов Widget с эквивалентными рангами, вместо алгоритма partition следовало бы использовать stable_partition.

Алгоритмы sort, stable_sort, partial_sort и nth_element работают с итераторами произвольного доступа, поэтому они применимы только к контейнерам vector, string, deque и array. Сортировка элементов в стандартных ассоциативных контейнерах бессмысленна, поскольку эти контейнеры автоматически хранятся в отсортированном состоянии благодаря собственным функциям сравнения. Единственным контейнером, к которому хотелось бы применить алгоритмы sort, stable_sort, partial_sort и nth_element, является контейнер list — к сожалению, это невозможно, но контейнер list отчасти компенсирует этот недостаток функцией sort (интересная подробность: list:.-sort выполняет стабильную сортировку). Таким образом, полноценная сортировка list возможна, но алгоритмы partial_sort и nth_element приходится имитировать. В одном из таких обходных решений элементы копируются в контейнер с итераторами произвольного доступа, после чего нужный алгоритм применяется к этому контейнеру. Другое обходное решение заключается в создании контейнера, содержащего list:: iterator, применении алгоритма к этому контейнеру и последующему обращению к элементам списка через итераторы. Третье решение основано на использовании информации упорядоченного контейнера итераторов для итеративной врезки (splice) элементов list в нужной позиции. Как видите, выбор достаточно широк.

Алгоритмы partition и stable_partition отличаются от sort, stable_sort, partial_ sort и nth_element тем, что они работают только с двусторонними итераторами. Таким образом, алгоритмы partition и stable_partition могут использоваться с любыми стандартными последовательными контейнерами.

Подведем краткий итог возможностей и средств сортировки.

•Полная сортировка в контейнерах vector, string, deque и array: алгоритмы sort и stable_sort.

•Выделение n начальных элементов в контейнерах vector, string, deque и array: алгоритм partial_sort.

•Идентификация n начальных элементов или элемента, находящегося в позиции n, в контейнерах vector, string, deque и array: алгоритм nth_element.

•Разделение элементов стандартного последовательного контейнера на удовлетворяющие и не удовлетворяющие некоторому критерию: алгоритмы partition и stable_partition.

•Контейнер list: алгоритмы partition и stable_partition; вместо sort и stable_sort может использоваться list:: sort. Алгоритмы partial_sort или nth_element приходится имитировать. Существует несколько вариантов их реализации, некоторые из которых были представлены выше.

Чтобы данные постоянно находились в отсортированном состоянии, сохраните их в стандартном ассоциативном контейнере. Стоит также рассмотреть возможность использования стандартного контейнера priority_queue, данные которого тоже хранятся в отсортированном виде (контейнер priority_queue традиционно считается частью STL, но, как упоминалось в предисловии, в моем определении «контейнер STL» должен поддерживать итераторы, тогда как контейнер priority_queue их не поддерживает).

«А что можно сказать о быстродействии?» — спросите вы. Хороший вопрос. В общем случае время работы алгоритма зависит от объема выполняемой работы, а алгоритмам стабильной сортировки приходится выполнять больше работы, чем алгоритмам, игнорирующим фактор стабильности. В следующем списке алгоритмы, описанные в данном совете, упорядочены по возрастанию затрачиваемых ресурсов (времени и памяти):

1. partition;
2. stable_partition;
3. nth_element;
4. partial_sort;
5. sort;
6. stable_sort.

При выборе алгоритма сортировки я рекомендую руководствоваться целью, а не соображениями быстродействия. Если выбранный алгоритм ограничивается строго необходимыми функциями и не выполняет лишней работы (например, partition вместо полной сортировки алгоритмом sort), то программа будет не только четко выражать свое предназначение, но и наиболее эффективно решать поставленную задачу средствами STL.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

HTML-код страниц разных типов

Из книги автора

HTML-код страниц разных типов Детальное изучение кода страниц – очень кропотливая и неинтересная работа, но ее необходимо выполнить. Это позволит вам выявить ошибки, допущенные конкурентом, и решения, им разработанные. И то и другое необходимо учитывать при создании


Помните: в Интернете пользователь может делать все, что захочет

Из книги автора

Помните: в Интернете пользователь может делать все, что захочет Интернет – это совместно используемая, свободная информационная среда. Посетители не только сами решают, что смотреть, но и как смотреть. Пользователь может многое:– выбрать размер страницы и разрешение


Контент разных модальностей

Из книги автора

Контент разных модальностей Вы должны понимать: чтобы зарабатывать деньги в социальных сетях, кто-то кому-то должен что-то продать Если отсутствует факт продажи (хоть в Интернете, хоть в офлайне), деньгам просто неоткуда взяться.Но, чтобы продавать, нужно заинтересовать.


1. Предложение разных версий продукта

Из книги автора

1. Предложение разных версий продукта В продающем тексте вы можете предложить три версии своего продукта: «Стандартную», «Голд» и «Платинум». Однозначно, у вас будут заказывать не только стандарт. В запусках многих тренингов есть целая таблица разных


Наборы для разных ценовых групп

Из книги автора

Наборы для разных ценовых групп В интернет-магазине должны быть в наличии наборы из трех разных ценовых групп.Бюджетные – ориентированы на людей, которые хотят сэкономить и отслеживают соотношение «цена – качество», хотят получить приемлемый результат за разумные


Преимущества разных размеров тестов

Из книги автора

Преимущества разных размеров тестов Размер теста имеет значение. Он влияет на специфические преимущества теста. На рис. 2.5 показана общая сводка, а ниже мы приводим более подробный список достоинств и недостатков каждого типа тестов. Рис. 2.5. Ограничения разных размеров


Основные сведения о существовании объектов

Из книги автора

Основные сведения о существовании объектов При построении C#-приложений вы вправе предполагать, что управляемая динамическая память будет обрабатываться без вашего прямого вмешательства. "Золотое правило" управления памятью .NET является очень простым.• Правило. Следует


Совет 10. Помните о правилах и ограничениях распределителей памяти

Из книги автора

Совет 10. Помните о правилах и ограничениях распределителей памяти Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между near- и far-указателями в некоторых 16-разрядных


Совет 15. Помните о различиях в реализации string

Из книги автора

Совет 15. Помните о различиях в реализации string Бьерн Страуструп однажды написал статью с интригующим названием «Sixteen Ways to Stack a Cat» [27], в которой были представлены разные варианты реализации стеков. Оказывается, по количеству возможных реализаций контейнеры string не уступают


Совет 19. Помните о различиях между равенством и эквивалентностью

Из книги автора

Совет 19. Помните о различиях между равенством и эквивалентностью Алгоритм find и функция set::insert являются типичными представителями семейства функций, проверяющих совпадение двух величин, однако делают это они по-разному. Для find совпадением считается равенство двух


Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы

Из книги автора

Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы Не все алгоритмы работают с произвольными интервалами. Например, для алгоритма remove (см. советы 32 и 33) необходимы прямые итераторы и возможность присваивания через эти итераторы. Таким образом,


Совет 50. Помните о web-сайтах, посвященных STL

Из книги автора

Совет 50. Помните о web-сайтах, посвященных STL Интернет богат информацией об STL. Если ввести в любой поисковой системе запрос «STL», вы получите сотни ссылок, часть из которых даже будет содержать полезную информацию. Впрочем, большинство программистов STL в поисках не нуждается


8.2.2. Сопоставление объявлений в разных файлах

Из книги автора

8.2.2. Сопоставление объявлений в разных файлах Одна из проблем, вытекающих из возможности объявлять объект или функцию в разных файлах, – вероятность несоответствия объявлений или их расхождения в связи с модификацией программы. В С++ имеются средства, помогающие


4.7. Нанесение размеров разных типов

Из книги автора

4.7. Нанесение размеров разных типов В системе КОМПАС реализован режим полуавтоматического нанесения размеров. В этом режиме пользователю необходимо указать нужный элемент и установить размерное число в требуемую точку. На основе этих данных система автоматически