ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 421
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Решение задач с помощью повторного использования кода 223
чу с помощью нашей текущей реализации studentCollection. Если итератор поддерживает ссылку на определенный узел в списке, то переход к следующему узлу требует простого следования по ссылке в узле. Тем не менее возврат к предыдущему узлу требует повтор- ного обхода списка вплоть до этой точки. Вместо этого нам бы по- требовался двусвязный список, узлы которого имеют указатели в обоих направлениях — как на следующий узел, так и на предыду- щий. Мы можем обобщить эту мысль и начать рассматривать раз- личные структуры данных и то, какие виды обходов или доступа к данным могут быть эффективно предложены клиентам. Например, в предыдущей главе, посвященной рекурсии, мы кратко описали структуру двоичного дерева. Существует ли способ позволить кли- енту совершить эффективный обход этой структуры в своей стан- дартной форме? Если нет, какие изменения нам нужно внести для обеспечения эффективных разворотов? Что такое правильный по- рядок узлов в двоичном дереве, подлежащем обходу? Размышление по поводу таких вопросов помогает нам стать более хорошими про- граммистами. Мы не только приобретем новые навыки, но и узна- ем больше о достоинствах и недостатках различных компонентов.
Знание плюсов и минусов компонента позволит нам использовать его с умом. Игнорирование ограничений конкретного подхода мо- жет заводить в тупик, и чем больше мы знаем о компонентах, кото- рые используем, тем меньше вероятность того, что это с нами про- изойдет.
1 ... 23 24 25 26 27 28 29 30 ... 34
Выбор типа компонента
Как мы видели в этих примерах, одна и та же проблема может быть решена с использованием различных типов компонентов. Шаблон может выражать идею решения, алгоритм может описывать реали- зацию этой идеи или другую идею, которая решает ту же пробле- му, абстрактный тип данных может инкапсулировать концепцию, а класс в библиотеке может содержать полностью проверенную реа- лизацию абстрактного типа данных. Если каждый из них — это выра- жение той концепции, которая требуется нам для решения пробле- мы, как мы узнаем, какой тип компонента следует выбрать из нашего инструментария?
Одно из основных соображений заключается в том, сколько уси- лий может потребоваться для интеграции компонента в наше реше- ние. Привязывание библиотеки классов к нашему коду часто явля- ется быстрым способом решения проблемы, тогда как реализация алгоритма из описания псевдокода может занять много времени.
Еще одно важное соображение заключается в степени гибкости, обес печиваемой предлагаемым компонентом. Часто компонент из- начально имеет удобную, готовую к использованию форму, но ког- да он интегрируется в проект, программист обнаруживает, что, хотя компонент выполняет большую часть необходимых задач, он дела-
224 Глава 7
ет не все. Например, возвращаемое значение одного метода имеет неправильный формат и требует дополнительной обработки. Если компонент все равно используется, то в будущем могут обнаружи- ваться другие проблемы до тех пор, пока компонент не будет совер- шенно отброшен, а для этой части проблемы не будет разработан с нуля новый код. Если программист выбрал компонент более высоко- го концептуального уровня, например шаблон, то полученная в ре- зультате реализация кода идеально впишется в проблему, поскольку она создавалась специально для ее решения.
На рис. 7.1 показано взаимодействие этих двух факторов. Как правило, код из библиотеки готов к использованию, но его нельзя изменить напрямую. Его можно модифицировать косвенно либо с помощью шаблонов C++, либо в том случае, если код, о котором идет речь, реализует нечто вроде шаблона-стратегии, о котором говори- лось ранее в этой главе. С другой стороны, шаблон может быть пред- ставлен в качестве идеи («класс, который может иметь только один экземпляр»), обеспечивая максимальную гибкость в плане реализа- ции, но требуя от программиста большой работы.
Конечно, это всего лишь общее руководство, а конкретные слу- чаи будут иметь свои отличия. Возможно, класс из библиотеки, ко- торый мы используем, находится на таком низком уровне в нашей программе, что гибкость не пострадает. Например, мы можем обер- нуть класс коллекции нашего собственного дизайна вокруг базово- го контейнерного класса, вроде list, который имеет такие широкие возможности, что, даже если нам придется расширить функцио- нальность нашего контейнерного класса, мы можем ожидать того, что класс list с этим справится. Прежде чем использовать шаблон, возможно, мы уже реализовали конкретный шаблон раньше, поэ- тому мы не столько создаем новый код, сколько адаптируем ранее написан ный.
Рис. 7.1. Типы компонентов: степень гибкости против количества требуемых усилий
Решение задач с помощью повторного использования кода 225
Чем больше у вас опыта использования компонентов, тем более уверены вы можете быть в том, что начинаете с нужного места. Пока вы не наработаете этот опыт, вы можете использовать компромисс между гибкостью и количеством необходимых усилий в качестве об- щего руководства. В каждой конкретной ситуации задайте себе сле- дующие вопросы. y
Могу ли я использовать компонент как есть, или для его вне- дрения в мой проект мне потребуется написать дополнитель- ный код? y
Уверен ли я в том, что понимаю всю суть проблемы или ту ее часть, которая относится к этому компоненту, а также в том, что она не изменится в будущем? y
Расширю ли я свои знания в области программирования, выбрав этот компонент?
Ответы на эти вопросы помогут вам оценить, сколько усилий вам потребуется, а также то, какую пользу вы получите от каждого из возможных подходов.
Процесс выбора компонента
Теперь, когда мы понимаем общую идею, давайте рассмотрим не- большой пример, чтобы разобрать конкретные детали.
: #
Проект требует того, чтобы вы отсортировали массив объектов studentRecord по оценкам, однако существует один подвох. Другая часть программы использует специ- альное значение оценки –1, обозначающее студента, запись которого не может быть перемещена. Таким образом, в то время как все остальные записи должны переме- щаться, те, которые имеют значение оценки –1, должны оставаться на своем месте, в результате получается массив, в котором отсортированные объекты перемежаются объектами со значением оценки равным –1.
Это сложная задача, и существует много способов, с помощью которых мы могли бы попытаться ее решить. Для простоты, да- вайте ограничимся двумя вариантами: либо мы выберем алго- ритм, то есть процедуру сортировки, вроде сортировки вставка- ми, и модифицируем его так, чтобы проигнорировать объекты studentRecord с оценкой –1, либо найдем способ использования библиотечной процедуры qsort для решения этой проблемы. Воз- можны оба варианта. Поскольку мы уже освоились с кодом сорти- ровки вставками, нам не составит труда добавить несколько ин- струкций if, чтобы конкретно проверить и пропустить записи с оценкой –1. Чтобы метод qsort сделал за нас всю работу, нам по- требуется воспользоваться обходным путем. Мы могли бы скопи- ровать записи учеников с реальными оценками в отдельный мас-
226 Глава 7
сив, отсортировать их с помощью qsort, а затем скопировать их обратно, убедившись в том, что мы не копируем ни одну из запи- сей с оценкой –1.
Давайте рассмотрим оба варианта, чтобы понять, как выбор типа компонента влияет на итоговый код. Мы начнем с такого компонента, как алгоритм, написав собственный модифициро- ванный код сортировки вставками для решения этой задачи. Как обычно, мы будем решать задачу поэтапно. Во-первых, давайте уменьшим ее, удалив всю проблему объектов с оценкой –1 и про- сто отсортировав массив объектов studentRecord без каких-либо специальных правил. Если sra — это массив, содержащий объек- ты arraySize типа studentRecord, то итоговый код будет выглядеть так: int start = 0;
int end = arraySize — 1;
for (int i = start + 1; i <= end; i++) {
for (int j = i; j > start &&
Xsra[j-1].grade() > sra[j].grade(); j--) {
Y studentRecord temp = sra[j-1];
sra[j-1] = sra[j];
sra[j] = temp;
}
}
Этот код очень похож на код сортировки вставками для целых чисел. Отличия состоят лишь в том, что для сравнения требуют- ся вызовы метода grade
X
, а наш временный объект, используемый в качестве подкачки, поменял свой тип
Y
. Этот код работает нор- мально, однако существует один нюанс, касающийся тестирования этого и других блоков кода приведенных далее в данном разделе: наш класс studentRecord проверяет данные, и, как было сказано ранее, не принимает оценку –1, поэтому убедитесь, что вы внесли необходимые изменения. Теперь мы готовы закончить эту версию решения. Нам нужно, чтобы алгоритм сортировки вставками игно- рировал записи с оценкой –1. Сделать это не так просто, как кажет- ся. В базовом алгоритме сортировки вставками мы всегда меняем местами соседние позиции в массиве — в приведенном выше коде это j и j — 1. Тем не менее, если мы оставим на месте записи с оцен- кой –1, то расстояние между записями, подлежащими перестанов- ке, может быть произвольным.
На рис. 7.2 приведен пример для иллюстрации этой задачи.
Если массив изображен в исходной конфигурации, то стрелки ука- зывают местоположение первых записей, которые нужно поме- нять местами, и они не являются соседними. Кроме того, в конце концов, последняя запись (для Арта) должна быть перемещена с по- зиции [5] на [3], а затем с [3] на [0], поэтому все замены, необхо- димые для сортировки этого массива (поскольку мы его сортиру- ем), касаются записей, которые не являются соседними.
Решение задач с помощью повторного использования кода 227
Рис. 7.2. Произвольное расстояние между записями, подлежащими перестановке в моди-
фицированном коде для сортировки вставками
В процессе размышления над решением этой задачи я искал ана- логию и нашел ее в обработке связных списков. Во многих алгоритмах связных списков необходимо поддерживать указатель не только на те- кущий узел в процессе обхода нашего списка, но и на предыдущий.
Поэтому в конце тела цикла мы часто назначаем текущий указатель предыдущему указателю, прежде чем перемещать текущий указатель.
Здесь должно происходить что-то подобное. Нам нужно отслеживать последнюю «реальную» запись студента по мере линейного продвиже- ния по массиву, чтобы найти следующую «реальную» запись. Практи- ческая реализация этой идеи выглядит следующим образом: for (int i = start + 1; i <= end; i++) {
X if (sra[i].grade() != -1) {
Y int rightswap = i;
for (int leftswap = i — 1; leftswap >= start
&& (sra[leftswap].grade() > sra[rightswap].grade()
Z || sra[leftswap].grade() == -1); leftswap--)
{
[ if(sra[leftswap].grade() != -1) {
studentRecord temp = sra[leftswap];
sra[leftswap] = sra[rightswap];
sra[rightswap] = temp;
\ rightswap = leftswap;
}
}
}
}
В базовом алгоритме сортировки вставками мы многократно вставляем несортированные элементы в постоянно растущую отсо- ртированную область внутри массива. Внешний цикл выбирает сле- дующий несортированный элемент, подлежащий вставке в отсор- тированный порядок. В этой версии кода мы начинаем с проверки того, что значение оценки в позиции i не равно –1
X
внутри внеш- него цикла. Если это так, мы просто перейдем к следующей записи, оставив эту запись на месте. Как только мы установили, что запись студента в позиции i может быть перемещена, мы инициализиру- ем переменную rightswap значением этой позиции
Y
. Затем запу- скаем внутренний цикл. В базовом алгоритме сортировки вставка- ми каждая итерация внутреннего цикла меняет местами соседние
228 Глава 7
элементы. Однако в нашей версии, поскольку оставляем на месте за- писи с оценкой –1, мы осуществляем обмен только тогда, когда в ме- стоположении j не находится оценка –1
[
. Затем мы меняем местами позиции leftswap и rightswap и присваиваем переменной rightswap значение leftswap
\
, настраивая следующий обмен во внутреннем цикле, если он есть. Наконец, нам нужно изменить условие в нашем внутреннем цикле. Обычно при сортировке вставками внутренний цикл прекращает выполняться, когда мы достигаем переднего конца массива или когда находим меньшее значение по сравнению с тем, которое вставляем. Здесь мы должны сформулировать составное ус- ловие с использованием логического или так, чтобы цикл продолжал выполняться после нахождения оценки –1
Z
(поскольку значение –1 всегда будет меньше любой допустимой оценки, что приведет к пре- ждевременной остановке цикла).
Этот код позволяет нам решить задачу, но может испускать неко- торый «неприятный запах». Стандартный код сортировки вставка- ми легко читается, особенно если вы понимаете суть того, что он де- лает. Однако эта модифицированная версия сложна для восприятия и, возможно, требует нескольких строк с комментариями, если мы хотим иметь возможность позднее его понять. Возможно, здесь мо- жет быть уместен рефакторинг, однако давайте попробуем исполь- зовать для решения этой задачи другой подход и рассмотрим соот- ветствующий ему код.
Первое, что нам понадобится, — это функция сравнения для ис- пользования с методом qsort. В данном случае мы будем сравнивать два объекта studentRecord, и наша функция будет вычитать одну оценку из другой: int compareStudentRecord(const void * voidA, const void * voidB) {
studentRecord * recordA = (studentRecord *) voidA;
studentRecord * recordB = (studentRecord *) voidB;
return recordA->grade() — recordB->grade();
}
Теперь мы готовы отсортировать записи. Мы сделаем это в три этапа. Во-первых, скопируем все записи, которые не содержат оцен- ки –1, во вторичный массив, без пропусков. Затем вызовем метод qsort для сортировки вторичного массива. Наконец, скопируем за- писи из вторичного массива обратно в исходный массив, пропустив записи с оценкой –1. Итоговый код выглядит следующим образом:
X studentRecord * sortArray = new studentRecord[arraySize];
Y int sortArrayCount = 0;
for (int i = 0; i < arraySize; i++) {
Z if (sra[i].grade() != -1) {
sortArray[sortArrayCount] = sra[i];
sortArrayCount++;
}
}
[ qsort(sortArray, sortArrayCount, sizeof(studentRecord), compareStudentRecord);
Решение задач с помощью повторного использования кода 229
\ sortArrayCount = 0;
] for (int i = 0; i < arraySize; i++) {
^ if (sra[i].grade() != -1) {
sra[i] = sortArray[sortArrayCount];
sortArrayCount++;
}
}
Хотя этот код имеет примерно ту же длину, что и другое реше- ние, он более прост и удобен для восприятия. Мы начинаем с объ- явления вторичного массива sortArray
X
, имеющего тот же размер, что и исходный массив. Переменная sortArrayCount инициализиру- ется нулем
Y
; в первом цикле мы будем использовать ее для отсле- живания количества записей, скопированных во вторичный массив.
Внутри этого цикла при каждом нахождении записи, не содержащей оценки –1
Z
, мы присваиваем ей следующий доступный слот в sor- tArray и инкрементируем sortArrayCount. После завершения цикла мы сортируем вторичный массив
[
. Значение переменной sortAr- rayCount сбрасывается на 0
\
; мы будем использовать ее во втором цикле для отслеживания количества записей, скопированных из вто- ричного массива обратно в исходный массив. Обратите внимание на то, что второй цикл обходит исходный массив
]
, ища слоты, которые необходимо заполнить
^
. Если мы подойдем к этому другим спосо- бом, пытаясь обработать циклом вторичный массив и поместив за- писи в исходный массив, нам понадобился бы двойной цикл, при чем внутренний цикл искал бы в исходном массиве следующий слот с реальной оценкой. Это еще один пример того, как наша концептуа- лизация задачи может сделать ее более легкой или трудной.
Сравнение результатов
Оба решения работают и представляют собой разумные подходы.
Для большинства программистов первое решение, в котором мы мо- дифицировали алгоритм сортировки вставками, чтобы оставить на месте некоторые записи, обойдя их в процессе сортировки, слож- нее в плане написания и восприятия. Тем не менее второе решение, похоже, несколько неэффективно, поскольку требует копирования данных во вторичный массив и обратно. Здесь могут пригодиться знания в области анализа алгоритмов. Предположим, мы сортируем
10 000 записей — если бы мы сортировали намного меньше записей, то не заботились бы об эффективности. Мы не можем точно знать, какой алгоритм лежит в основе вызова метода qsort, однако в худ- шем случае универсальная сортировка потребовала бы поменять ме- стами записи 100 миллионов раз, а в лучшем случае — около 130 000.
Вне зависимости от того, в каком месте диапазона мы находимся, ко- пирование 10 000 записей туда и обратно нанесет по производитель- ности не столь серьезный удар по сравнению с сортировкой. Кроме того, мы должны учесть, что любой алгоритм, используемый мето- дом qsort, может оказаться гораздо эффективнее, чем наша простая сортировка вставками, нивелировав любое преимущество, которое