В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 4
Текст из файла (страница 4)
Пусть файл занимает 6 кластеров 0..5, которые хранятся в кластерах с физическими номерами100..103 и 720..721 соответственно. Тогда атрибут Data будет содержать 2 run-а (поскольку файл содержит 2непрерывных цепочки:Run 1Run 20100447202Заметим, что такая технология позволяет иметь дырки в файлах, хотя всё это сопровождается довольнобольшими накладными расходами: если файл сильно фрагментирован, т. е. у него почти нет длинных цепочек,на каждый короткий кусочек будет использоваться по одному run-у.
Это неэкономно. Поэтому в NT5 была проведена оптимизация, которая позволяет сократить количество информации, необходимой для хранения файла:Структура run-ов в NT5 другая: каждый run состоит только из логического номера первого кластера цепочки и их количества. При этом последовательность run-ов предваряется заголовком фрагмента, состоящим изстартового виртуального номера и стопового виртуального номера, увеличенного на 1.Пример 3.2. Пусть файл содержит дырку: заполнены кластеры 0..15, отражаемые в физические 123..132 и200..205, и кластеры 64..65, отражаемые в физические 100..101.
Виртуальные кластеры файла с номерами 16..63никогда не использовались. Тогда атрибут Data будет содержать 2 фрагмента:Фрагмент 1016Заголовок12310RunФрагмент 22006Run6466Заголовок1002RunСистема NTFS поддерживает сжатие данных. Кластеры сжимаются блоками по 16 штук, но структура runов при этом сохраняется. Возьмём предыдущий пример и допустим, что кластеры 0..15 сжались в 10 кластеров.Здесь нулевой физический номер второго run-а не соответствует никакому кластеру и является сигналом сжатия:Фрагмент 1016Заголовок12310RunФрагмент 206Run6466Заголовок1002Run3. Эффективные алгоритмы сортировок массивовОдной из основных задач организации хранения данных в вычислительных системах является обеспечениеэффективного доступа к отдельным элементам этих данных. В предыдущих разделах мы уже рассматривалиразличные структурные методы хранения данных.
Однако часто вполне достаточным оказывается использование простейших одномерных упорядоченных массивов. В этом случае доступ к конкретному элементу данныхможно эффективно осуществить с помощью процедуры бинарного поиска (метода деления пополам). Как легковидеть, вычислительная сложность подобного поиска составляет O(log2 n) операций сравнения для массива,содержащего n элементов.
Формирование упорядоченного массива из некоторого исходного набора данных составляет другую сторону этой задачи — сортировку. Процедуры поиска и сортировки традиционно относятся кклассическим задачам программирования.Существует множество алгоритмов сортировки, различающихся по своим характеристикам и сферам применимости. Но любой алгоритм сортировки в качестве базовых операций использует сравнение двух элементов иих взаимную перестановку (или запись элемента в указанное место массива).
Таким образом, трудоёмкость алгоритма сортировки можно оценивать количеством элементарных операций, требующихся для упорядочиваниямассива из n элементов. Вообще говоря, скорости выполнения центральным процессором операций сравненияи перестановки могут существенно различаться, однако эти отличия зависят от архитектуры процессора иструктуры кода самой программы сортировки. Поэтому при оценке трудоёмкости мы не будем различать этиоперации.Итак, эффективность алгоритмов сортировки можно оценивать по следующими параметрам:••••Среднее количество операций, необходимых для сортировки массива из n элементовНаибольшее количество операций, которое может возникнуть при сортировке массива из n элементовНаименьшее количество операций, которое может возникнуть при сортировке массива из n элементовКоличество дополнительной памяти, необходимое для сортировки массива из n элементов10Первый пункт этого списка соответствует наиболее вероятной трудоёмкости алгоритма при сортировке случайного набора данных.
Второй и третий пункты относятся к случаям сортировки специальных массивов —«плохих» и «хороших» — и показывают, насколько алгоритм способен учитывать в своей работе особенностиначального распределения элементов сортируемого массива. Эти два пункта характеризуют крайние точки воценке трудоёмкости. При этом пункт 2 определяет так называемую гарантированную оценку трудоёмкости.Всюду в этом разделе для определенности мы будемсортировку по возрастанию, т. е. упоря рассматриватьдочивание элементов массива a[i] так, чтобы ∀ i ∈ 0, . . .
, n − 1 было выполнено a[i]6a[i+1]. Кроме этого,будем для простоты считать, что сортируемый массив содержит элементы типа int.3.1. Простейшие сортировкиЗдесь мы рассмотрим три хорошо известных алгоритма — сортировки выбором максимума, вставкой и «пузырьком».Метод выбора максимального элемента основан на следующей идее. Пусть k ∈ 0, . . . , n − 1 . Находиммаксимальный элемент aj среди чисел a0 , . . . , ak−1 .
Обмениваем значения элементов aj и ak−1 . Указаннуюпроцедуру последовательно выполняем для k = n, . . . , 2. Реализация данного алгоритма может выглядеть так:void SortFindMax(int * a, int n){int i, j, k, MaxElem, MaxIndex;for (k = n; k > 1; k--){MaxElem = a[0];MaxIndex = 0;for (j = 0; j < k; j++)if (MaxElem < a[j]){MaxElem = a[j];MaxIndex = j;}a[MaxIndex] = a[k-1];a[k-1] = MaxElem;}}Нетрудно подсчитать, что трудоёмкость этого алгоритма всегда составляет O(n2 ) операций независимо отисходного состояния массива.Сортировка вставкой тоже весьма проста.
Предположим, что элементы a0 , . . . , ak−1 уже упорядочены нужным образом. Возьмём элемент ak и вставим его на нужное место в набор a0 , . . . , ak−1 так, чтобы получиласьупорядоченная последовательность из k + 1 элемента. Далее выполняем эту процедуру для следующего элемента и так до конца массива. Фактически алгоритм состоит в выполнении описанной выше процедуры дляk = 1, . . . , n − 1. Поиск нужного места в упорядоченной части массива можно осуществлять простейшим последовательным просмотром. Итак, получаем следующую функцию:void SortInsert(int *{int i, j, k, tmp;for (k = 1; k < n;{for (i = 0; i <tmp = a[k];for (j = k; j >a[i] = tmp;}}a, int n)k++)k && a[i] < a[k]; i++);i; j--) a[j] = a[j-1];Трудоёмкость этого алгоритма также всегда оценивается величиной O(n2 ), поскольку при постановке на место каждого элемента массива нам приходится просматривать всех его предшественников, а затем отодвигать«хвост» упорядоченной части вправо на одну позицию.
Однако здесь мы можем снизить трудоёмкость сортировки «хороших» массивов за счёт некоторого усложнения процедуры поиска нужного места в упорядоченнойчасти. Действительно, если этот поиск осуществлять методом деления пополам, то на каждом упорядоченномучастке длины k мы затратим порядка log2 k операций сравнения. Суммируя эти оценки для k = 1, .
. . , n,получим O(n log2 n) операций сравнения. Таким образом, если исходный массив уже «почти» упорядочен, товставка будет, как правило, происходить в конце отсортированной части массива и не даст значительного вкладав общую трудоёмкость алгоритма, что позволит надеяться на трудоёмкость в O(n log2 n) операций. С другойстороны, если взять убывающий массив, то вставка каждый раз будет происходить в начало отсортированнойчасти, и постоянные сдвиги «хвостов» на одну позицию опять дадут общую трудоёмкость O(n2 ).11Анализ приведённого выше алгоритма показывает, что его слабым местом является поиск требуемой позициидля вставки элемента в упорядоченную часть, поскольку именно он определяет общую трудоёмкость в самомблагоприятном случае. Попытка совместить сравнения и перестановки элементов в алгоритме приводит к такназываемым «пузырьковым» сортировкам. Идея этих алгоритмов заключается в сравнении двух соседних элементов массива и возможной их перестановке в порядке возрастания.
Способы выбора этих соседних элементовопределяют различные варианты алгоритма.Простейший вариант пузырьковой сортировки можно получить из метода вставки, последовательно проводясравнения и обмены очередного элемента ak с элементами ak−1 , ak−2 , . . . , пока он не займёт свое законное место.void BubbleDownSort(int * a, int n){int i, k, tmp;for (k = 1; k < n; k++){for (i = k; i > 0 && a[i] < a[i-1]; i--){tmp = a[i];a[i] = a[i-1];a[i-1] = tmp;}}}Этот алгоритм обычно называют нисходящим вариантом пузырьковой сортировки.
В наилучшем случае(исходный массив уже упорядочен по возрастанию) его трудоёмкость составляет O(n) операций, так как здесьтело внутреннего цикла ни разу не выполнится. В наихудшем случае мы опять имеем трудоёмкость O(n2 ), ноесли массив имеет уже упорядоченные участки, то алгоритм сумеет это обнаружить и не будет делать на нихлишней работы.Классическим методом пузырьковой сортировки обычно называют другой вариант — так называемыйвосходящий алгоритм.
Его можно описать следующей схемой. Пусть дано некоторое число k ∈ 0, . . . , n − 1 .Сравниваем два соседних элемента ai−1 и ai и если ai−1 > ai , то меняем их местами. Такое сравнение и возможную перестановку последовательно выполняем для i = 1, . . . , k. Назовём эту процедуру подъёмом до k-йпозиции. Последовательно выполняем подъём до k-й позиции для k = n − 1, . . . , 1. Если при очередном подъёме не будет выполнено ни одной перестановки, то массив уже является упорядоченным и процесс сортировкиможно прекратить.}void BubbleUpSort(int * a, int n){int i, k, sorted, tmp;for (k=n-1; k>0; k--){sorted = 1;for (i = 1; i <= k; i++)if (a[i] < a[i-1]){tmp = a[i];a[i] = a[i-1];a[i-1] = tmp;sorted = 0;}if (sorted) break;}В смысле трудоёмкости этот вариант аналогичен предыдущему.
Именно, для уже упорядоченного массиватрудоёмкость составит O(n), но в общем случае оценка O(n2 ) сохраняется. Достоинством данного вариантаявляется то, что по мере подъёма алгоритм заодно упорядочивает внутренние фрагменты массива. Таким образом, если исходный массив отличается от упорядоченного лишь в некоторых местах, то общая вычислительнаяработа будет сравнительно малой.Кстати, мы можем довольно просто ввести в самый первый алгоритм аналогичную проверку так, чтобы приобнаружении упорядоченности массива алгоритм заканчивал работу.
Модифицированный вариант выглядиттак:void OptFindMaxSort(int * a, int n){int i, j, k, MaxElem, MaxIndex, s;for (k = n; k > 1; k--){MaxElem = a[0];12MaxIndex = 0;for (s = j = 0; j < k; j++)if (MaxElem <= a[j]){MaxElem = a[j];MaxIndex = j;s++;}if (s == k) break;a[MaxIndex] = a[k-1];a[k-1] = MaxElem;}}Некоторое представление о поведении этих алгоритмов может дать следующая таблица, в которой приведено условное время сортировки1 массивов из 100000 элементов с различными начальными распределениямиэлементов. Для сравнения в эту таблицу добавлен столбец, в котором приведены результаты для функции qsortиз стандартной библиотеки C.Тип массиваСлучайныйВозрастающийУбывающийВолнообразныйПочти возрастающийFindMax2136272121Insert3526443526BubbleDown39079391BubbleUp83077541OptFindMax220202221qsort0.050.030.030.030.04Как и следовало ожидать, метод перестановки максимума оказывается в среднем лучше за счет меньшегоколичества перестановок элементов, а пузырьковые методы хорошо реагируют на упорядоченность массива.Оценка трудоёмкости O(n2 ) также подтверждается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
