Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 56
Текст из файла (страница 56)
д Кслбса н Пар«ээ«(Ю7?), С э рыэ«см (1977). Л( ррэ сы П 979), Нэээбэы » м «э лээ«сы (ю79), гм р ш мэ««э эаэ«эм (19781 «и ня а, палом Ц рхж«П993). Бы б р ., э рю сбр а. ра(ет мэжю са ж эх сэ эа лычэ»зэ Глава ГО БЫСТРЫЕ АЛГОРИТй(Ы, ОСНОВАННЫЕ НА СТРАТЕГИИ ДУБЛИРОВАНИЯ Некоторые хорошие алгоритмы удается строить на основе стратегви, коюрая дублирует алгоритм решения половины задачи. Выберем объем задачи л в качестве параметра и разобьем, если южно, задачу на две подзадачи объема л(2 той же самой струи- туры, что и исходная задача.
Если решения этих подзадач можно скомбинировать в решение исходной задачи, то получается алгоритм решения данной задачи, который часто оказывается эффентивным. БПФ-алгоритм Куин — Тьюкн во основанию два можно понимать как алгоритм, полученный разбиением задачи на дне половины я дублиронаннем, так квк л-точечный алгоритм строится из двух (л!2)-точечных БПФ-алгоритмов. Алгоритм нтерирования фильтр-секций также имеет зту структуру, так как л-фильтрсекци» строится из двух (л/2)фильтр-секций. В иастоягцей главе строятся другие быстрые алюритмы, основанные на делении задачи пополам и дублировании.
Они нлл«ютрнруюг способ по. строения алгоритмов, пригодных для многих видо» задач. 10.1. Стратегия деления пополам ц дублирования Рассмотрим задачу нахождения многочлена р («) степени л, заданного своими нерпами Рш Рш ..., )), э Мм должны найти ке. зффициент» многочлена р (х) вида р (х) = (х — Р,) (л — И) ... (» — Р 4). Наиболее естественным путем решения этой задачи являетс» послеповательиое умножение на одночлены, зачиная с какого- нибудь конца, скажем правого, согласно процедуре рг'1(х) = (х — бэ) рн '1 (х), 1 = 1,,, л — 1, прв начальной точке ргэ' (х) = (х — И).
На 1-м шаге итерации такая процедура требует 1 умножений н 1 сложений, что в общей сложноств приводит к (!1 ) л (л — 1) умножениям и такому же чюлу сложений. л д з г чэм л х э в ° р Рэ . га.г. праитэурэ и ца ф 344 Гл. Ю. бь трм эзг рюмм, еснаээ з стр т г н дта нр зэ нв Деление задачи пополам и дублирование по*вопиет построить более эффективный алгоритм Предположим. что л равно степени двух, а именно л = 2 .
(Процедуру легка модифицировать для других значений л, пополняя данные фективными входами.) Положим теперь гь — 1 гз — 1 р'(х) — П (х — рг), р'(х): — П (» — р„гттг) г=а г э и р (х) = р" (х) р' (х). Последнее равенство в там виде, в «отаром оно записано, требует (п(2)з умножений. Если р' (х) и р" (х) вычнслнютсн непосредственным образам, та каждое из этих вычислений требует (1(2) (л(2) Дя(2) — 1) умножений. Полное число умножений равна что не лучше, чем при прямом методе вычислений. Для извлечения из стратегии дублирования какой-та выгоды надо применить лучшие способы сочетания двух частей вычисления р (х) = р"(х) р'(х).
Но эта задача представляет собой линейную свертку, кошрую мм столь интенсивно изучали и Которую можно вычислить не более чем с Ал )ай, и аперацнями, где А— некоторая малая константа. Следовательно, полное число умножений в таком алгоритме не превосходит величины А( (я) = Ал )айэн+ — ( — — 1у, нагорая при больших л уже лучше выписанной ранее. Это число можно уменьшать еще дальше, применяя к вычислению каждого из многачленов р' (х) и р" (х) ту же самую идею Каждая из этих задач может быть разбита на две и вычислена по алгоритму, сочетающему содержащие А (п(2) 1ощ (л)2) онериций решения двух половин, что дает е итоге меньше чем Ал 1об, (л(2) операций.
Продолжая таким образом, мы уменьшим число умножений да . М(л) = А ~~ л)обэ(л(21) = А — ()ой,'л — 1общ). Прн не очень малых л эта величина меньше, чем (1(2) и (л — 1), . тан что стратегия разбиения задачи пополам и дублирования . позволила построить улучшенный алгоритм. На рнс. 10.1 приведена схема органиэапии вычисления произведения многочленов с помощью рассмотренной процедуры ' дублирования. Этз схема «вляется хорошим примерам так иазываеиых рекурсивных процедур. Рекурсивная процедура представ. Ю.1. Стратмяэ деле эя вмм я эуаанразаэна 1О.э, Отргзсгрн лазнмх !0.2. Структуры данных Р» . 1О,я. Праныурэ БПФ. Ээб Гл. 1О Бис рис аэг рз мм.
Осзо эинмэ эз сш г дуби р Гхэя лает собой искусный программный модуль, который не содержит точнага описания каждого уровня вычислений, а описывает только один уровень, содержащий копию той же самой процедуры. Процедура обращается с вызовом и самой себе Это предполагает запись текущих данных в виде стека, который будет описан е следующем разделе.
При каждом вызове пронедуры происходит проталкивание вниз существующего стека даннык с целью освобаждевия чистого рабочега пространства. Подобная стратегия дублираванвя мажет использоваться для решения многих задач. Если задача некоторого вычисления зази.
сят ат иекаюрого целого числа л, то при л = 2" можно попы. таться получить ответ из атветоз для двух подзадач с и = 2 Рекурсивная форма БПФ-алгоритма Кули †Тью с дублироэа. пнем выплсэна на рис. 10.2. Полезно проследить, насколько от. личаютсз последовательности операций на рис. 9.8 и 1О 2. Рекурсивный алгоритм приводит к расточительному использованию текущей памяти, таи как спадает временный стек для запоминания результатов вычисления преобразований Фурье разных абъ.
емав. С другой стороны, рекурсивную форму алгоритма удобна использовать в спиной программе, позволяющей вычислять пронэаальнае преобразование Фурье па основанию лва. Рекурсивная фариа может быть также удобна для организации БПФ-алгоритмов по смешанному пснаэанню, так как легко разветвляется в Лругие подпрограммы. Стратегию дублиравани» обычво удастся распространить на задачи, в которых параметр и не равен степени двух. Один иэ способов состоит в добавлении достаточного для превращения числа л в ближайшую стеаень двух числа фальшивых итераций, хата иногда, как, например, в случае преобрззовання Фурье, этот способ не проходит. Можно также разбивать задачу на подзадачи другага объема, разного, скажем, трети нли пятой части объема исходной задачи, но, если задача допусиает, разбиение на половинки, как правило, дает лучший результат.
Входящий в некщорос вычисление набор данных перед начатом обработки должен быть соответствующим образам упорядочен. Данные промежуточных вычислений также подлежат определенному запоминанию; в рассмотренных в предыдущем параграфе алгоритмах дублирования для этого исполыовался обратный стек. Двумя основными методами организации данных являются опаски и деревья Сноскам длины Е называется упорядоченное множество из 8 позиций; иаждая позиция сача может представлять собой с.ванный набор данных, лаже, в частности, тоже содержать списки. Э«а Гл.
|О. Бышры «рз, «овшы «ш З пы луслыр|ш Ю.З. Б «тры« «л опыт ы сортыр кы | кр Р . |О 3. Д р «о. Рыс |Од Л аы З в Зь Список, все элементы которого ывлякггся |»сдам», часто называется еекторам. Если все элементы сопска приналлежат ненотарому копеч»очу алфавыту. список иногда называется цепочкой.
Цепочка ае обязательна имеет фнкснрозанную длину, но длина вектора обычна фнкснроэана Раза»чае между вектором » це. почкой лежит скорое » применен»», чем в существе дела. Списком переменной длины называется оп»сон, длнна каюрого не фиксирована, а со времене» растет или уменьшается. Список переМенной длины может расти нлн укорачиваться путем добавления невой познцнн в любую точку ониска или удалением позиция из любой гочки с»нека, но ва многнх случаях познани добавляытгс» нлн удаляются только на двух концах списка, Список, добавление нли удаленне паз»пай э котором происходят только аа одном конце, — скажем, в вершине — называется стеком, илн обритньм списком, нлн пшзеднизы-пришел-леремы.ушел-бу. фером. Со»сок, в котором добавление пазацнй происходит на одном конце, а !дале»ые на другом, называется очередью, нли червь.ы-пришел-пером ы-ушел-буфером.
Деревом называется такая структура даннык, и которой за каждой поющие» могут следовать одна нлп более позиций, называемых потомкам»; прнмер граф»ческаго изображения такой структуры приведен на рнс )О.З. Каждому узлу соответствует познцня данных, н каждая поэ»цня имеет в качестве своих потомка» другие позы»и». с которыми она связана. Возможна ситуация, в которой несколько узлов дерева соогесгствуют одной п той же поэ»цин данных В противоположность дереау каждая »азпцыя списка может нметь талька одншо потомка. Позиция данпык в списке нли в дереве может быть лостатачно сложной, включая, возыожно, текст на естестеенном языке; по с тачки зрения последования структуры списка» каждая познпия рассматрнваегся кан некая единица. В памятн вычислительного устройства сп»скн н дереаья запоминаются с помощью некоторых имен, присванааемых позициям; хорош»ми именами являются адреса ячеек памяти, в которых нзчннзются данные позиций Список )нли дереза) запоминается в ваде наследоеательнссги имен позиций, входящих в список.
Список не обязательно запомпнпть » непосредственной блнзости к позициям данных. Другим, иногда более удобным методам, является меп|д неправ|ай адресапни, пазы»а»мы» свцшышем спискам) он показан »а ряс. 10 4. Позиции даннмх пая»лаются з произвольном порядке, и наждый вход начинается с адреса следующей паз»цап данных спн«ка. Нз рнс.
10.4 показая дшдиой связанный слысшс. В двойном с»язаннон списке данные записаны двумя способами — снажем, в алфавитном » хронологическом порядке — но не обязательно аапоминаюгся дважды. Если список часто пересматривается, то удобнее пользоваться связанным спискам, так как эю позволяет не двигать данные Организация стека даже из сложных поэнцнй данных реалызуется простым присваиванием адреса пер»ой позиции данных п прнвязмваняем к каждой позиции данных адреса следующей по списку позиции данных.
Для заансн новой познци» данных в зер. шину стек» надо просто привязать адрес предыдущей вершины к новой вершине н изменить адрес первой позиция данных на адрес новой познц»». Для извлечения позицнн данных нз вершины стека надо обратить процедуру. !0.3. Быстрые алгоритмы сортироцкн Задача сорт»ранка формулируется следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
