динамические алгоритмы сортировки
Это интересно!!!
динамические алгоритмы

динамические алгоритмы картинки

Алгоритмы работы с динамическими структурами. вс, 08/12/2012 - 14:34 — tech. Добавление элемента в стек.

Алгоритмы динамического упpавления памятью
Next: Открытая память (продолжение) Up: Управление оперативной памятью Previous: Открытая память
Алгоритмы динамического упpавления памятью
Динамическое распределение памяти (его еще иногда называютуправлением кучей ( pool или heap)) представляет собойнетривиальную проблему. Действительно, активное использование функций malloc/free может привести к тому, что вся доступная памятьбудет разбита на блоки маленького размера, и попытка выделениябольшого блока завершится неудачей,даже если сумма длин маленьких блоков намного больше требуемой.Это явление называется фрагментацией памяти.Кроме того, большое количество блоков требует длительного поиска.Существует также много мелких трудностей разного рода.К счастью, человечество занимается проблемой распределения памятиуже давно, и найдено много хороших или приемлемых решений.
В зависимости от решаемой задачи используются различные алгоритмыпоиска свободных блоков памяти. Действительно, программа может требоватьмножество блоков одинакового размера, или нескольких фиксированных размеров.Это сильно облегчает решение проблемы фрагментации и поиска.Возможны ситуации, когда блоки освобождаются в порядке, обратном тому,в котором они выделялись. Это позволяет свести выделение памяти кстековой структуре.Возможны ситуации, когда некоторые из занятых блоков можно переместитьпо памяти. Так, например, функцию realloc() в ранних реализацияхсистемы UNIX можно было использовать именно для этой цели.
В стандартных библиотеках языков высокого уровня, таких как malloc/free/realloc в C, new/dispose в Pascal и т.д.,как правило, используются алгоритмы, рассчитанные на худший случай:программа требует блоки случайного размера в случайном порядке иосвобождает их также случайным образом.Возможен, правда, более непpиятный случай:
Example: while(TRUE) { void Случайный размер от 0 до 10 байт b2 = malloc(random(10)+10); // if(b1 == NULL && b2 == NULL) // break; // free(b1); } void Скорее всего, память не будет выделена */
В результате исполнения такой программы вся доступная память будет``порезана на лапшу': между любыми двумя свободными блоками будет размещензанятый блок меньшего размера.К счастью, пример 4 носит искусственный характер.В обычных программах такая ситуация встречается редко, и частооказывается проще исправить программу, чем вносить изменения вуниверсальный алгоритм управления кучей.

В связи с проблемами планирования в ОСРВ используются статические алгоритмы планирования (RMS – Rate Monotonic Scheduling) [LL73] и динамические алгоритмы

Варианты алгоритмов распределения памяти исследовались еще в 50-е годы.Итоги многолетнего изучения этой проблемы приведены в [ 2]и многих других учебниках.
Возможны алгоритмы распределения памяти двух типов: когда размерблока является характеристикой самого блока, и когда его сообщают отдельнопри освобождении. К первому типу относится malloc/free, ко второму - GetMem/FreeMem в Turbo Pascal. В первом случае с каждым блокомассоциируется некоторый дескриптор, который содержит длину этого блока и,возможно, какую-то еще информацию.Этот дескриптор может храниться отдельно от блока, или быть его заголовком.Иногда такой дескриптор ``окружает' блок, то есть состоит из двух меток -в начале блока и в его конце.Для чего это может быть полезно, будет обсуждаться ниже.
Обычно все свободные блоки памяти объединяются в двунаправленныйсвязанный список. Список должен быть двунаправленным для того, чтобы из негов любой момент можно было извлечь любой блок. Впpочем, если все действия поизвлечению блока пpоизводятся после поиска, то можно слегка усложнитьпpоцедуpу поиска и всегда сохpанять указатель на пpедыдущий блок. Этоpешает пpоблему извлечения и можно огpаничиться однонапpавленным списком.Беда только в том, что многие алгоpитмы пpи объединении свободных блоковизвлекают их из списка в соответствии с адpесом, поэтому для таких алгоpитмовдвунапpавленный список остpо необходим.
При первом взгляде на проблему возникает желание отсортироватьсписок по размеру блока. На самом деле это бессмысленно:время поиска в сортированном списке улучшается всего в два раза посравнению с несортированным (вот в массиве или в дереве - совсем другое дело),зато добавляется время вставки в список, пропорциональное O( n), где n -размер списка. Помещать блоки в сортированный массив еще хуже -время вставки становится и появляется ограничение наколичество блоков.Использование хэш-таблиц или двоичных деревьев требует большихнакладных расходов и усложнений программы, которые себя в итогене оправдывают. Поэтому используют несортированный список.
Поиск в списке может вестись двумя способами:до нахождения первого подходящего ( first fit) блокаили до блока, размер которого ближе всего к заданному - наиболее подходящего ( best fit).Для нахождения наиболее подходящего мы обязаны просматривать весь список,в то время как первый подходящий может оказаться в любом месте,и среднее время поиска будет меньше.Насколько меньше - зависит от отношения количества подходящихблоков к общему количеству. (Читатели, знакомые с теорией вероятности,могут самостоятельно вычислить эту зависимость).

Алгоритм динамической адресации объектов. Воробиенко П.П., Тихонов В.И., Смирнов И.В., Сопина У.И

Кроме того, в общем случае best fit увеличивает фрагментацию памяти.Действительно, если мы нашли блок с размером большезаданного, мы должны отделить ``хвост' и пометить его как новыйсвободный блок. Понятно, что в случае best fit средний размер этого хвостабудет маленьким, и мы в итоге получим большое количество мелких блоков,которые невозможно объединить, так как пространство между ними занято.
При использовании first fit с линейным двунаправленным спискомвозникает специфическая проблема. Если каждый раз просматривать списокс одного и того же места, то большие блоки, расположенные ближе к началу,будут чаще удаляться. Соответственно, мелкие блоки будут иметь тенденциюскапливаться в начале списка, что увеличит среднее время поиска.Простой способ борьбы с этим явлением состоит в том, чтобы просматриватьсписок то в одном направлении, то в другом.Более радикальный и еще более простой метод состоит в том,что список делается кольцевым, и поиск каждый начинается с того места,где мы остановились в прошлый раз.В это же место добавляются освободившиеся блоки.В результате список очень эффективно перемешивается и никакой``антисортировки' не возникает.
В ситуациях, когда мы размещаем блоки несколькихфиксированных размеров, алгоритмы best fit оказываются лучше. Однакобиблиотеки распределения памяти рассчитывают на худший случай, и в нихобычно используются алгоритмы first fit.
В случае работы с блоками нескольких фиксированных размеровнапрашивается такое решение: создать для каждого типоразмера свой список.Это избавляет программиста от необходимости выбирать между first и best fit,устраняет поиск в списках как явление... короче, решаетсразу много проблем.
Интересный вариант этого подхода для случая, когда различные размерыявляются степенями числа 2, как 512 байт, 1Кбайт, 2Кбайта и т.д.,называется алгоритмом близнецов.Он состоит в том, что мы ищем блок требуемого размера в соответствующем списке.Если этот список пуст, мы берем список блоков вдвое большего размера.Получив блок вдвое большего размера, мы делим его пополам.Ненужную половину мы помещаем в соответствующий список свободных блоков.Любопытно, что нам совершенно неважно, получили ли мы этот блок просто изсоответствующего списка, или же делением пополам вчетверо большего блока,и далее по рекурсии. Одно из преимуществ этого метода состоит в простотеобъединения блоков при их освобождении. Действительно, адрес блока-близнецаполучается простым инвертированием соответствующего бита в адресе нашегоблока. Нужно только проверить, свободен ли этот близнец. Если он свободен,то мы объединяем братьев в блок вдвое большего размера, и т.д.
Алгоритм близнецов значительно снижает фрагментацию памяти и резко ускоряетпоиск блоков. Наиболее важным преимуществом этого подхода является то,что даже в наихудшем случае время поиска не превышает , где и обозначаютсоответственно максимальный и минимальный размеры используемых блоков.Это делает алгоритм близнецов труднозаменимым для ситуаций, когданеобходимо гарантированное время реакции - например, для задач реальноговремени. Часто этот алгоритм или его варианты используются для выделенияпамяти внутри ядра ОС. Например, функция kmalloc, используемаяв ядре ОС Linux, основана именно на алгоритме близнецов.
Разработчик программы динамического распределения памяти обязанрешить еще одну важную проблему, а именно - объединение свободных блоков.Действительно, обидно, если мы имеем сто свободных блоков по одномукилобайту и не можем сделать из них один блок в сто килобайт.Но если все эти блоки расположены в памяти один за другим, а мы неможем их при этом объединить - это просто унизительно. Кроме того, еслимы умеем объединять блоки и видим, что объединенный блок ограничен сверхузначением brklevel, то мы можем вместо помещения этого блока в списокпросто уменьшить значение brklevel и, таким образом, вернуть ненужнуюпамять системе.
Рассмотрим способы решения этой проблемы. Один способ упоминалсяв описании алгоритма близнецов, но он пригоден только в особых случаях.
Представим себе для начала, что все, что мы знаем о блоке, - это егоначальный адрес и размер. Такая ситуация возможна при выделении памяти``второго рода', т.е. когда размер освобождаемого блока передается какпараметр процедуры FreeMem.Кроме того, такое возможно и в случаях, когда дескриптор блока содержиттолько его длину.
Легко понять, что это очень плохая ситуация. Действительно, дляобъединения блока с соседями мы должны найти их в списке свободных, илиже убедиться, что там их нет. Для этого мы должны просмотреть весьсписок. В порядке мозгового штурма можно высказать идею сортировать списоксвободных блоков по адресу...
Гораздо проще запоминать в дескрипторе блока указатели надескрипторы соседних блоков. Немного развив эту идею, мы приходим к методу,который упоминался в начале раздела. Этот метод называется алгоритмом парныхметок и состоит в том, что мы добавляем к каждому блоку по два слова памяти.
*

2.1. Итеративные алгоритмы. 2.2. Рекурсия.  Лекция 2.4: Базовые алгоритмы / Динамические структуры данных.


ПРИБОРЫ ДИНАМИЧЕСКОЙ ОБРАБОТКИ Динамические процессоры применяются практически во всех областях работы со звуком. На сегодняшний день алгоритмы

ТУРСУНБАЙ кызы Ырысгуль. Локальные и динамические алгоритмы для анализа граф-моделей систем.


Мифы о динамических кодах: Самым известным алгоритмом динамического кодирования является Keeloq — разработка американской компании Microchip.


Название: Алгоритмы и структуры данных. Новая версия для Оберона Автор: Никлаус Вирт  рекурсию, сортировку, поиск, динамические структурные типы данных.

Динамические соединения. Допустим мы имеем массив из N объектов, а также 2  А квадратичные алгоритмы не масштабируются, даже с учетом развития технологий.


Рекомендуем

rd-ok.ru Телефон: +7 (382) 089-44-12 Адрес: Краснодарский край, Армавир, Посёлок РТС, дом 43