Какая сортировка самая быстрая? Тестируем алгоритмы. Оптимальный алгоритм замещения страниц

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

СП с пространственно-временными корреляционными связями и СП независимых случайных величин с нулевыми средними и дисперсиями . Вектор параметров позволяет учесть, например, возможные взаимные пространственные смещения и повороты соседних кадров изображения.

Появление детерминированного сигнала приводит к изменению модели (2.1) лишь в области индексов (рис. 1) последнего из наблюдаемых кадров:

где - совокупность отсчетов полезного сигнала.

В рассмотренных условиях необходимо найти правило проверки гипотезы Н0 об отсутствии аномалии в области G при альтернативном предположении Н1 о справедливости модели (2.2).

При заданных вероятностных характеристиках компонент моделей (2.1), (2.2) могут быть определены соответствующие условные плотности распределения вероятностей (ПРВ) наблюдений W(Z|Н0) и W(Z|Н1). Поэтому для решения задачи обнаружения следует воспользоваться сравнением с пороговым уровнем отношения правдоподобия (ОП):

(2.3)

Для упрощения вычислений представим условные ПРВ в виде произведений: , где ZG - совокупность наблюдений по области G; Z0 - совокупность всех наблюдений, не принадлежащих области предполагаемого сигнала. Поскольку , ОП (2.3) перепишется в форме:

. (2.4)

Будем аппроксимировать условные ПРВ, входящие в ОП (2.4), гауссовскими распределениями:

где , и , , - условные математические ожидания и пространственные ковариационные матрицы наблюдений ZG при отсутствии и наличии полезного сигнала соответственно.

С учетом моделей наблюдений (2.1), (2.2) нетрудно получить следующие формулы для условных средних , где - оптимальный прогноз значений СП , построенный на основе всех имеющихся наблюдений Z0 , не принадлежащих области сигнала. Пространственные матрицы V0 и V1 оказываются одинаковыми:, где - ковариационная матрица ошибок оптимального прогноза.

После подстановки приведенных соотношений в (2.4), (2.5) и логарифмирования находим следующий алгоритм обнаружения сигнала:

, (2.6)

где- порог обнаружения. Как следует из формулы (2.6), процедура обнаружения аномалий включает в себя компенсацию мешающих изображений с помощью вычитания из наблюдения оптимального прогноза , найденного на основе всех наблюдений, не принадлежащих области G. После компенсации мешающих СП осуществляется линейное весовое cуммирование остатков

Применяя формулу Фробениуса обращения блочных матриц, можно показать, что статистика приводиться к эквивалентному виду:

где ,- оптимальный прогноз значения , построенный на основе всех имеющихся наблюдений, кроме ; . -дисперсия ошибки этого прогноза. В отличие от будем называть "прогнозом в точку". При обнаружении аномалий во всевозможных областях G с большим числом элементов "прогноз в точку" может быть найден с помощью значительно меньшего числа вычислительных операций, чем "прогноз в область" .

Еще одна форма записи оптимальной процедуры обнаружения может быть получена в предположении, что полезный сигнал может занимать все имеющиеся кадры изображения, т.е. область G включает все многомерные сетки . Тогда наилучший прогноз , и алгоритм (2.6) принимает вид:

, (2.8)

где ; - ковариационная матрица мешающего изображения.

Непосредственная реализация процедуры (2.8) затруднительна из-за большого числа вычислительных операций. Тем не менее, раскладывая пространственную симметрическую матрицу в произведение двух треугольных , можно представить (2.8) в форме

(2.9)

соответствующий предварительному "выбеливанию" последовательности изображений , и последующему весовому суммированию с весами . Во многих случаях такой подход позволяет найти приемлемые для практики квазиоптимальные алгоритмы "выбеливания" . При этом самостоятельное рассмотрение адаптивных рекурсивных фильтров, близких по свойствам к выбеливающим, является важным направлением поиска возможностей относительно простой технической или программной реализации системы обработки последовательностей изображений. Новым качеством, которым обладают алгоритмы (2.7), (2.8) и (2.9) по отношению к (2.6), является разделение трудоемкой операции оптимального прогнозирования или выбеливания, не связанной с формой сигнала, и относительно простого весового суммирования, учитывающего вид полезного сигнала. Это позволяет достаточно просто решать как задачи обнаружения аномалий с неизвестными параметрами положения, так и более сложные проблемы многоальтернативного обнаружения (распознавания) нескольких видов сигналов .

Приведенные результаты позволяют уточнить условия, при которых справедлива предложенная замена условных ПРВ нормальными распределениями. Прежде всего, это широкий класс с гауссовскими моделями (2.1), (2.2). В этих случаях процедуры (2.6), (2.7), (2.9) строго оптимальны. При негауссовских компонентах моделей (2.1), (2.2) достаточным условием оптимальности служит возможность аппроксимации апостериорной ПРВ прогноза нормальным распределением. Заметим, что последнее условие выполняется и во многих прикладных задачах обработки СП со значительными пространственно-временными корреляционными связями и обычно эквивалентно условию высокой апостериорной точности прогнозирования.

Оптимизация алгоритма разрабатываемой программы
Этап разработки алгоритма вашего приложения - самый сложный во всей цепочке жизненного цикла программы. От того, насколько глубоко продуманы все аспекты вашей задачи, во многом зависит успех ее реализации в виде программного кода. В общем случае изменения в структуре самой программы дают намного больший эффект, чем тонкая настройка программного кода. Идеальных решений не бывает, и разработка алгоритма приложения всегда сопровождается ошибками и недоработками. Здесь важно найти узкие места в алгоритме, наиболее влияющие на производительность работы приложения.

Кроме того, как показывает практика, почти всегда можно найти способ улучшить уже разработанный алгоритм программы. Конечно, лучше всего тщательно разработать алгоритм в начале проектирования, чтобы избежать в дальнейшем многих неприятных последствий, связанных с доработкой фрагментов программного кода в течение короткого промежутка времени. Не жалейте времени на разработку алгоритма приложения - это избавит вас от головной боли при отладке и тестировании программы и сэкономит время.

Следует иметь в виду, что алгоритм, эффективный с точки зрения производительности программы, никогда не соответствует требованиям постановки задачи на все 100% и наоборот. Неплохие с точки зрения структуры и читабельности алгоритмы, как правило, не эффективны в плане реализации программного кода. Одна из причин - стремление разработчика упростить общую структуру программы за счет использования везде, где только можно, высокоуровневых вложенных структур для вычислений. Упрощение алгоритма в этом случае неизбежно ведет к снижению производительности программы.

В начале разработки алгоритма довольно сложно оценить, каким будет программный код приложения. Чтобы правильно разработать алгоритм программы, необходимо следовать нескольким простым правилам:
1. Тщательно изучить задачу, для которой будет разработана программа.
2. Определить основные требования к программе и представить их в формализованном виде.
3. Определить форму представления. входных и выходных данных и их структуру, а также возможные ограничения.
4. На основе этих данных определить программный вариант (или модель) реализации задачи.
5. Выбрать метод реализации задачи.
6. Разработать алгоритм реализации программного кода. Не следует путать алгоритм решения задачи с алгоритмом реализации программного кода.
В общем случае, они никогда не совпадают. Это самый ответственный этап разработки программного обеспечения!
7. Разработать исходный текст программы в соответствии с алгоритмом реализации программного кода.
8. Провести отладку и тестирование программного кода разработанного приложения.

Не следует воспринимать эти правила буквально. В каждом конкретном случае программист сам выбирает методику разработки программ. Некоторые этапы разработки приложения могут дополнительно детализироваться, а некоторые вообще отсутствовать. Для небольших задач достаточно разработать алгоритм, слегка подправить его для реализации программного кода и затем отладить.

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

Оптимизация с учетом аппаратных средств компьютера
Обычно разработчик программного обеспечения стремится к тому, чтобы производительность работы приложения как можно меньше зависела от аппаратуры компьютера. При этом следует принимать во внимание наихудший вариант, когда у пользователя вашей программы будет далеко не самая последняя модель компьютера. В этом случае "ревизия" работы аппаратной части часто позволяет найти резервы для улучшения работы приложения.
Первое, что нужно сделать, - проанализировать производительность компьютерной периферии, на которой должна работать программа. В любом случае знание того, что работает быстрее, а что медленнее, поможет при разработке программы. Анализ пропускной способности системы позволяет определить узкие места и принять правильное решение. Различные устройства компьютера имеют разную пропускную способность. Наиболее быстрыми из них являются процессор и оперативная память, относительно медленными - жесткий диск и CD-привод. Самыми медленными являются принтеры, плоттеры и сканеры.

Алгоритмы замещения страниц. FIFO. Вторая попытка. Алгоритм LRU.

Алгоритмы замещения страниц. Оптимальный алгоритм. Алгоритм NRU.

Алгоритмы замещения страниц

Хотя при каждом прерывании можно выбирать случайную страницу, производительность системы увеличится, если удалить саму редко используемую страницу.

Оптимальный алгоритм

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

NRU (Not Recently Used) алгоритм (не использовавшаяся в последнее время страница)

В табличной записи для каждой страницы присутствуют 2 бита:

Бит R (бит обращения) устанавливается в единицу при каждом обращении к странице. Возможен сброс этого бита, например каждые n тиков таймера, чтобы отличить страницы, к которым давно не было обращения;

Бит M (бит модификации) устанавливается в единицу при изменении страницы. Сигнализирует о том, что при удалении надо страницу записать на диск.

При страничном прерывании, на основании значений битов R и M, ОС делит все страницы на 4 класса. Для удаления случайным образом выбирается страница из низшего класса. Алгоритм легок в реализации и может дать вполне достаточный результат.

FIFO алгоритм

ОС поддерживает список всех страниц, находящихся в памяти. Список отсортирован в порядке появления страниц. При страничном прерывании выгружается страница из начала списка. Алгоритм редко используется в чистом виде.

Алгоритм "вторая попытка"

Является модификацией алгоритма FIFO. При страничном прерывании, у первой страницы в списке изучается бит R. Если он равен единице, страница помещается в конец списка, а бит R сбрасывается, и проверяется следующая страница. Данный алгоритм ищет в списке страницу, к которой не было обращений за последние n тиков таймера. Если происходили ссылки на все страницы, алгоритм превращается в обычный FIFO.

Алгоритм "часы"

Предыдущий алгоритм является корректным, однако неэффективным, потому что постоянно передвигает все страницы по списку. Поэтому лучше хранить записи страниц в кольцевом списке и использовать указатель на одну из ячеек. Когда происходит страничное прерывание, проверяется бит R у страницы, на которую указывает указатель. В зависимости от бита R содержимое записи может измениться, и изменяется значение указателя, что значительно быстрее модификации всего списка. Алгоритм полностью идентичен алгоритму "вторая попытка", кроме непосредственной реализации.

Алгоритм LRU (Last Recently Used), страница, не использовавшаяся больше всего

В основе этого алгоритма лежит наблюдение, что страницы, к которым происходило многократное обращение в нескольких последних командах, вероятно, так же будут использоваться в последующих командах и наоборот. Алгоритм состоит в том, что при страничном прерывании из памяти выгружается страница, к которой дольше всего не было обращений. Реализация данного алгоритма является недешевой. Для полного осуществления необходимо поддерживать связанный список всех содержащихся в памяти страниц, где последняя используемая страница находится в начале списка. Сложность заключается в том, что список должен обновляться при каждом обращении к памяти. При таком подходе поиск страницы, ее удаление и вставка в начало списка занимают очень много времени. Существуют аппаратные методы реализации данного алгоритма.

Для первого метода требуется оснащение компьютера специальным N-разрядным счетчиком, который автоматически возрастает после каждой команды. Кроме этого, каждая запись в таблице страниц должна иметь поле для хранения значения этого счетчика. После каждого обращения к памяти, значение счетчика запоминается в записи в таблице в соответствующей странице, к которой произошло обращение. Если возникает страничное прерывание, менеджер памяти проверяет значение счетчиков во всей таблице и ищет наименьшее. Эта страница и является неиспользуемой дольше всего.

Второй вариант аппаратной реализации заключается в том, что на системе с N-страничными блоками поддерживается аппаратная матрица размером NxM, изначально равных нулю. При обращении к странице k аппаратура присваивает всем битам k-ой строки единицу, затем всем битам k-ого столбца - нуль. В любой момент времени строка с наименьшим двоичным значением является неиспользуемой дольше всего.

Предположим, что все искажения в канале строго детерминированы и случайным является только гауссовский аддитивный шум который будем вначале полагать белым, со спектральной плотностью Это значит, что при передаче сигнала (символа приходящий сигнал можно описать моделью (3.28):

где все известны. Неизвестны лишь реализация помехи и индекс действительно переданного сигнала, который и должна определить решающая схема.

Будем также считать, что все являются финитными сигналами, длительность которых Это имеет место, если передаваемые сигналы финитны и имеют одинаковую длительность (система синхронная), а в канале нет ни многолучевого распространения, ни линейных искажений, вызывающих растяжение сигнала (либо они скорректированы).

В дальнейшем будем везде полагать, что в системе обеспечена надежная тактовая синхронизация, т. е. границы тактового интервала, на котором приходит сигнал известны точно. Вопросы синхронизации весьма существенны при реализации оптимальных демодуляторов и синхронных систем связи вообще, но они выходят за пределы данного курса. Момент начала посылки примем за нуль.

Определим в этих условиях алгоритм работы оптимального (т. е. основанного на правиле максимального правдоподобия) демодулятора, анализирующего сигнал на тактовом интервале С этой целью необходимо найти отношения правдоподобия для всех возможных сигналов относительно нулевой гипотезы

Задача затрудняется тем, что ширина спектра сигнала бесконечна (поскольку он финитный), а поэтому пространство сигналов бесконечномерное Для таких сигналов (или бесконечномерных векторов), как уже отмечалось, не существует плотности вероятностей. Однако существуют -рные плотности вероятностей для любых сечений сигнала (см. § 2.1).

Заменим вначале белый шум. квазибелым, имеющим ту же одностороннюю спектральную плотность мощности но только в некоторой полосе частот где 1. Рассмотрим вначале нулевую гипотезу, т. е. будем считать, что - шум. Возьмем на тактовом интервале равноотстоящих сечений через Отсчеты в этих сечениях для квазибелого гауссовского шума независимы в соответствии с (2.49). Поэтому -мерная плотность вероятностей для взятых отсчетов

где дисперсия (мощность) квазибелого шума.

При гипотезе, что передавался символ Следовательно, условная -мерная плотность вероятности сечений определится такой же формулой, как и (4.18), если заменить разностью

Отношение правдоподобия для сигнала (относительно нулевой гипотезы), вычисленное для сечений:

Заменим дисперсию ее выражением:

По правилу максимума правдоподобия в случае квазибелого шума решающая схема должна выбирать значение обеспечивающее максимум Вместо максимума можно отыскивать максимум его логарифма:

Заметим, что второй член в (4.22) не зависит от и его можно при сравнении не учитывать. Тогда правило решения о том, что передавался сигнал можно сформулировать следующим образом:

В -мерном евклидовом пространстве определяет норму разности векторов или расстояние между ними. Поэтому алгоритм (4.23) можно записать в виде

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

Рис. 4.2. Оптимальное разбиение пространства принимаемых колебаний при двоичном коде и точно известных сигналах

Преобразуем (4.22), раскрыв скобки и произведя сокращения:

Вернемся теперь к исходной задаче для белого шума. С этой целью будем расширять полосу Тогда число сечений будет стремиться к бесконечности, к нулю. Суммы в (4.24) обратятся в интегралы, и логарифм отношения правдоподобия определится как

а алгоритм решения о передаче примет вид

где энергия ожидаемого сигнала

Устройство, непосредственно вычисляющее скалярное произведение,

называют активным фильтром, или коррелятором, поэтому приемник, реализующий алгоритм (4.26), называют корреляционным.

На рис. 4.3 показана структурная схема приемного устройства, работающего в соответствии с (4.26). Здесь блоки X - перемножители; А - генераторы опорных сигналов - интеграторы, вычитающие устройства; решающее устройство, определяющее в моменты времени, кратные (при замыкании ключа), номер ветви с максимальным сигналом.

Если сигналы выбраны таким образом, что все их реализации (а следовательно, и все реализации имеют одинаковые энергии алгоритм

Рис. 4.3. Оптимальный демодулятор при точно известных сигналах

приема (4.26) (и соответственно его реализация) упрощается (отпадает необходимость в вычитающих устройствах) и принимает

Из (4.29) видно, что правило решения не изменится, если сигнал поступающий на вход демодулятора, умножить на любое число. Поэтому система, в которой все реализации сигнала имеют равную энергию, отличается тем, что оптимальный алгоритм приема в ней не требует знания «масштаба» приходящего сигнала или, другими словами, знания коэффициента передачи канала. Эта важная особенность обусловила широкое распространение систем сигналов с равной энергией, которые обычно называют системами с активной паузой. Особенно важна эта особенность для каналов с замираниями, в которых коэффициент передачи флуктуирует (см. ниже § 4.7).

Следует подчеркнуть, что правильный тактовый синхронизм для выявления границ посылок (съем сигналов на выходе блока в моменты времени, кратные и сброс напряжения с интегратора после принятия решения) является непременным условием практической реализации рассмотренных алгоритмов по схеме рис. 4.3.

Для наиболее распространенной двоичной системы неравенств (4.26) остается лишь одно, и алгоритм приема можно представить в более простом виде:

где разностный сигнал; пороговый уровень. Для системы с активной паузой что значительно облегчает реализацию оптимальной схемы.

При выполнении неравенства (4.30) регистрируется символ 1, в противном случае - 0. Для реализации (4.30) в схеме рис. 4.3 требуется лишь одна ветвь.

На рис. 4.4 показана схема, реализующая алгоритм (4.30) для двоичной системы передачи однополярными импульсами (с пассивной паузой):

Рис. 4.4. Реализация оптимального приема двоичных прямоугольных видеоимпульсов

При этих сигналах и правило (4.30) примет следующий вид:

Интегрирование в схеме рис. 4.4 осуществляется с достаточной точностью цепью при условии, что При этом на конденсаторе С напряжение в момент равно - Следовательно, правило сводится к тому, что это напряжение должно превысить пороговый уровень который и вводится в При выполнении этого неравенства в записывается 1, при невыполнении - 0. После этой записи (происходящей при замыкании ключа необходимо произвести сброс напряжения с интегратора, чтобы можно было принимать следующий элемент сигнала. Сброс осуществляется замыканием ключа разряжающего конденсатор.

Эта же схема, с небольшой модификацией, может использоваться для демодуляции в двоичной системе передачи двухполярными импульсами (с активной паузой): При этом следовательно, В этом случае правило (4.30) после сокращения принимает вид

Его реализует схема рис. 4.4, если пороговый уровень X положить равным нулю. При этом превращается в дискриминатор полярности, выдающий символ 1, когда на его входе напряжение положительно, противном случае.

Рассмотренные две системы используются в простейших устройствах проводной связи. В радиоканалах, а также в современных кабельных каналах используются высокочастотные сигналы. Наиболее простыми двоичными системами с гармоническими сигналами являются системы с амплитудной (AM), фазовой (ФМ) и частотной манипуляцией.

В двоичной Все входящие сюда постоянные в этом параграфе полагаем известными. Поскольку здесь правило (4.30) запишется так:

Оно реализуется схемой рис. 4.5, которая отличается от рис. 4.4. блоком перемножения приходящего сигнала с опорным сигналом Пороговый уровень в этом случае равен

Рис. 4.5. Реализация оптимального приема в двоичной системе AM, ФМ при точно известном сигнале

При двоичной ФМ системе

Это - система с активной паузой, и поэтому в Легко убедиться, что правило решения сводится при этом к следующему: и

реализуется той же схемой рис. 4.5 при В этом случае играет роль дискриминатора полярностей. Вид его можно определить, зная на фоне белого шума со спектральной плотностью Легко видеть, что на выходе фильтра будут сигналы а шум будет окрашенным, со спектральной плотностью т. е. на вход воображаемого оптимального демодулятора будут поступать именно те сигналы и тот шум, на которые он рассчитан. Таким образом, схема рис. 4.66 представляет собой демодулятор для сигналов на фоне белого шума, в котором вероятность ошибок меньше, чем в оптимальном демодуляторе, подключенном к выходу обеляющего фильтра на рис. 4.6а. Это противоречие и доказывает, что не может существовать демодулятор для сигналов на фоне окрашенного шума лучший, чем на рис. 4.6а.

Заметим, что при реализации такого демодулятора с обеляющим фильтром возникают трудности, связанные с тем, что сигналы при прохождении через фильтр, как правило, растягиваются и возникает взаимное наложеине элементов, сигнала Существует ряд путей преодоления этой трудности, однако подробный анализ их выходит за пределы курса

Следует обратить внимание на то, что в схеме рис. 4.5 опорный сигнал должен иметь те же начальные фазы, что и ожидаемые приходящие сигналы или, другими словами, должен быть когерентным с приходящими сигналами. Это требование обычно затрудняет реализацию демодулятора и требует введения в него помимо указанных на рис. 4.5 блоков дополнительных устройств, предназначенных для регулировки фаз опорных сигналов.

Все методы приема, для реализации которых необходимо точное априорное знание начальных фаз приходящих сигналов, называются когерентными. В тех случаях, когда сведения о начальных фазах ожидаемых сигналов извлекаются из самого принимаемого сигнала (например, если фаза флуктуирует, но настолько медленно, что может быть предсказана по предыдущим элементам сигнала), прием называют квазикогерентным. Если же сведения о начальных фазах приходящих сигналов отсутствуют или по каким-либо соображениям не используются, то прием называют некогерентным (см. ниже § 4.6).