|
KrNews
#16
29 июля 2003 |
|
Кодинг - Алгоритмы и структуры данных.
________________________
Цодинг
_________________________
Просто страшно называть эту залипень
coding'ом -так, просто цодинг.
Хотел я погрузить немного рулеза от
Вирта (Вирт рулез! Винер рулез!). Ааааа,
да и опять не успел. А оно вам надо ?
Пишите, если надо. Вообще есть у него
целая книжка:
[Л]. Вирт Н. Алгоритмы и структуры дан-
ных: Пер. с англ. -2-е изд., испр. -
СПб.: Невский Диалект, 2001. -352c.:ил.
РУЛЕЗ! от корки до корки! Увидите -
хватайте не задумываясь!
Только не охота мне все переписывать
оттуда, да еще и на асм перекладывать :)
В общем идите в приложение -там все
исходники в XAS'е и в txt с комментария-
ми, а также пояснительная записка (под
Speccy и матричный принтер) курсовика в
тему сортировки. Тут просто не хочется
конвертить асм к 40 символам -жуткая
вещь получится.
А для затравки предлагаю результаты
работы сей проги -сравнение двух мето-
дов сортировки (кстати в том каркасе
можно любые методы потестировать):
4 Результаты исследования
Пункты в таблице оаначают следующее:
- Количество сортируемых элементов (по
2 байта каждый);
- Метод заполнения сортируемого массива,
-упорядоченное (уже сортированный)
-обратное (упорядочен наоборот)
-случайное (по RND)
-упорядоченное + случайное (в упоря-
доченный массив по случайным адресам
заносятся случайные числа -их коли-
чество дозируется в основном меню
как 1/2, 1/4 etc);
- Количество произведенных сравнений;
- Количество перемещений (обменов);
- Время сортировки (с шагом 0.02 сек).
4.1 Результаты сортировки прямым вы-
бором (один из 'обычных' методов):
Кол-во │ метод │ кол-во кол-во время,
эл-ов │ зап-я │ срав-й перем-й сек
───────┼───────┼────────────────────────
64 │упоряд.│ 2016 0 0.20
│обратн.│ 2016 1024 0.24
│случай.│ 2016 186 0.20
│уп.+сл.│ 2016 162 0.22
───────┼───────┼────────────────────────
256 │упоряд.│ 32640 0 3.18
│обратн.│ 32640 16384 3.96
│случай.│ 32640 1088 3.24
│уп.+сл.│ 32640 1027 3.22
───────┼───────┼────────────────────────
1024 │упоряд.│ 523776 0 50.78
│обратн.│ 523776 262144 63.72
│случай.│ 523776 5770 51.18
│уп.+сл.│ 523776 5166 50.76
───────┼───────┼────────────────────────
4096 │упоряд.│ 8386560 0 715.70
│обратн.│ 8386560 4194304 896.20
│случай.│ 8386560 27806 716.88
│уп.+сл.│ 8386560 26703 716.82
4.2 Результаты сортировки по дереву:
Кол-во │ метод │ кол-во кол-во время,
эл-ов │ зап-я │ срав-й перем-й сек
───────┼───────┼────────────────────────
64 │упоряд.│ 593 457 0.12
│обратн.│ 525 383 0.10
│случай.│ 578 425 0.10
│уп.+сл.│ 523 371 0.10
───────┼───────┼────────────────────────
256 │упоряд.│ 3452 2355 0.64
│обратн.│ 3106 2025 0.56
│случай.│ 3281 2194 0.62
│уп.+сл.│ 3009 1978 0.54
───────┼───────┼────────────────────────
1024 │упоряд.│ 18060 11503 3.24
│обратн.│ 16407 10077 2.88
│случай.│ 17305 10858 3.08
│уп.+сл.│ 17225 10803 3.04
───────┼───────┼────────────────────────
4096 │упоряд.│ 88835 54503 15.56
│обратн.│ 82304 48673 13.86
│случай.│ 85671 51633 14.72
│уп.+сл.│ 85811 51777 14.82
пс// Да, я просто выпал, когда какая-то
гнилая сортировка каких-то 4096 элемен-
тов (8кб) работала 800 сек.!!! (я внача-
ле хотел сортировать всю страничку, т.е.
16 кб - 8192 элемента), пришлось даже
симуляцию сделать (см. сорцы)
Но я еще больше выпал, когда сорти-
ровка по некоему дереву (я еще и в прин-
цип ее долго въежал) работала в 30 раз
быстрее !!!
3. Краткие теоретические сведения
3.1 Сортировка
3.1.1 При обработке данных важно
знать информационное поле данных и раз-
мещение их в машине. Различают внутрен-
нюю и внешнюю сортировку:
- внутренняя сортировка -сортировка
в оперативной памяти;
- внешняя сортировка -сортировка во
внешней памяти.
Сортировка -это расположение данных
в памяти в регулярном виде по их ключам.
Регулярность рассматривают как возраста-
ние (убывание) значения ключа от начала
к концу в массиве.
Если сортируемые записи занимают
большой объем памяти, то их перемещение
требует больших затрат. Для того, чтобы
их уменьшить, сортировку производят в
таблице адресов ключей, делают переста-
новку указателей, т.е. сам массив не пе-
ремещается. Это метод сортировки таблицы
адресов.
При сортировке могут встретиться
одинаковые ключи. В этом случае при сор-
тировке желательно расположить после
сортировки одинаковые ключи в том же по-
рядке, что и в исходном файле. Это -ус-
тойчивая сортировка.
Эффективность сортировки можно расс-
матривать с нескольких критериев:
- время, затрачиваемое на сортиров-
ку;
- объем оперативной памяти, требуе-
мой для сортировки;
- время, затраченное программистом
на написание программы.
Выделяем первый критерий, поскольку
будем рассматривать только методы сорти-
ровки "на том же месте", то есть не ре-
зервируя для процесса сортировки допол-
нительную память. Эквивалентом затрачен-
ного на сортировку времени можно считать
количество сравнений при выполнении сор-
тировки и количество перемещений, хотя
это и весьма приблизительная оценка. По-
этому следует также производить непос-
редственное измерение времени, затрачи-
ваемого на сортировку, в данных конкрет-
ных условиях.
Различают следующие методы сортиров-
ки:
- строгие (прямые) методы, к которым
относится простая сортировка прямым вы-
бором;
- улучшенные методы, к которым отно-
сится сортировка по дереву.
Строгие методы демонстрируют естест-
венное поведение человека, они наиболее
просты, но работают очень медленно, т.к.
их эффективность падает пропорционально
квадрату числа элементов -f (n^2). В то
время как для улучшенных методов это вы-
ражение близко к f (n * log n), хотя они
более сложны и более трудны в понимании
и контроле.
3.2 Сортировка с помощью прямого вы-
бора
3.2.1 Этот прием основан на следую-
щих принципах:
- Выбирается элемент с наименьшим
ключом.
- Он меняется местами с первым эле-
ментом A[1].
- Затем этот процесс повторяется с
оставшимися n-1 элементами, n-2 элемен-
тами и т.д. до тех пор, пока не останет-
ся один, самый "большой" элемент.
Алгоритм формулируется следующим об-
разом:
FOR i:= 1 TO n-1 DO
k:= индекс min (a[i], ... , a[n]);
поменять местами a[i]<->a[k];
END;
;
;// (c) Niklaus Wirth "Algorithms and
;// data structures"
;// --> source written on Modula-2.
;//
;// PROCEDURE StraightSelection;
;// VAR i,j,k: index; x: item;
;// BEGIN
;// FOR i := 1 TO n-1 DO
;// k := i; x := a[i];
;// FOR j := i+1 TO n DO
;// IF a[j] < x THEN
;// k := j; x := a[k] END
;// END;
;// a[k] := a[i]; a[i] := x
;// END
;// END StraightSelection;
;
Эффективность алгоритма. Число срав-
нений ключей C, очевидно, не зависит от
начального порядка ключей. Можно ска-
зать, что в этом смысле поведение этого
метода менее естественно, чем поведение
прямого включения. Для С при любом рас-
положении ключей имеем:
С = n(n-1)/2 (3.1)
Порядок числа сравнений, таким обра-
зом, O(n^2).
Число перестановок минимально в слу-
чае изначально упорядоченных ключей:
Mmin = 3 * (n-1) (3.2)
И максимально, если первоначально
ключи располагались в обратном порядке:
Mmax = (n^2)/4 + 3*(n-1) (3.3)
Для случайно расположенных ключей
приблизительно [1]:
Mavg = n * (ln(n) + g)(3.4)
где g=0.577216...- константа Эйлера.
В худшем случае сортировка прямым
выбором дает порядок n^2, как для числа
сравнений, так и для числа перемещений.
3.3 Сортировка с помощью дерева
3.3.1 Метод сортировки с помощью
прямого выбора основан на повторяющихся
поисках наименьшего ключа среди n эле-
ментов, среди оставшихся n-1 элементов и
т.д. Очевидно, что каждый раз необходимо
выполнить K-1 сравнений, где K -коли-
чество оставшихся элементов. Улучшить
метод можно лишь оставляя на каждом про-
ходе больше информации о структуре мас-
сива. Наиболее удобным в этом случае яв-
ляется представление массива двоичным
деревом. Д. Уилльямсом была предложена
специальная структура дерева -пирамида.
Она определяется как последовательность
ключей h(L), h(L+1),..., h(R), такая,
что
h(i) <= h(2*i) и
h(i) <= h(2*i+1) для i = L, ..., R/2
(3.5)
Т.е. вышестоящий элемент всегда не
меньше нижестоящих. В частности, в вер-
шине дерева стоит min элемент.
h1 3 3
/ / 42
/ / 6
h2h3 426 55
/ / / / 94
h4 h5 h6 h7 55 94 18 12 18
12
Рис. 3.1 Пирамида из семи элементов
В теории показано, что к такой
структуре можно добавлять слева элемен-
ты. Тогда для перемещения нового элемен-
та на нужное место (из вершины) потребу-
ется максимум log(n) сравнений.
Р. Флойд предложил способ построения
пирамиды "на том же месте". Здесь h1,
..., hn -некий массив, причем hm, ...,
hn (где m=(n div 2)+1.) уже образуют пи-
рамиду, поскольку индексов i,j, удовлет-
воряющих условиям j=2*i, j=2*i+1, просто
не существует. Эти элементы образуют
нижний уровень пирамиды (Рис. 3.1), для
них никакой упорядоченности не требует-
ся. Теперь пирамида расширяется влево;
каждый раз добавляется и сдвигами ста-
вится в надлежащую позицию новый эле-
мент.
Для того, чтобы получить не только
частичную, но и полную упорядоченность
среди элементов, нужно проделать n сдви-
гающих шагов, причем после каждого шага
на вершину выталкивается минимальный
элемент.
Алгоритм описывается следующим обра-
зом:
;//
;// (c) Niklaus Wirth "Algorithms and
;// data structures"
;// --> source written on Modula-2.
;//
;// PROCEDURE HeapSort;
;// VAR L,R: index; x: item;
;//
;// PROCEDURE sift (L,R: index);
;// VAR i,j: index; x: item;
;// BEGIN i := L; j := 2*L; x := a[L];
;// IF (j < R) & (a[j] < a[j+1])
;// THEN j := j+1 END;
;// WHILE (j <= R) & (x < a[j]) DO
;// a[i] := a[j]; i := j; j := 2*j;
;//IF (j < R) & (a[j] < a[j+1])
;// THEN j := j+1 END;
;// END;
;// a[i] := x
;// END sift;
;//
;// BEGIN (* начало HeapSort *)
;// L := (n DIV 2)+1; R := n;
;// WHILE L > 1 DO L := L-1;
;// sift (L,R) END; (* R=n *)
;// WHILE R > 1 DO x := a[1];
;// a[1] := a[R]; a[R] := x;
;// R := R-1; sift (L,R) END;
;// (* L=1 *)
;// END HeapSort;
;//
;
Эффективность алгоритма. В худшем
случае нужно n/2 сдвигающих шагов, они
сдвигают элементы на log(n/2),
log(n/2-1), ..., log(n-1) позиций. Сле-
довательно, фаза сортировки требует n-1
сдвигов с самое большее log(n-1),
log(n-2), ..., 1 перемещениями. Кроме
того, нужно еще n-1 перемещений для про-
сачивания сдвинутого элемента на некото-
рое расстояние вправо. Эти соображения
показывают, что даже в самом плохом из
возможных случаев HeapSort потребует n *
log n шагов. Великолепная производитель-
ность в таких плохих случаях -одно из
привлекательных свойств HeapSort.
Совсем не ясно, когда следует ожи-
дать наихудшей (или наилучшей) произво-
дительности. Но вообще-то кажется, что
HeapSort "любит" начальные последова-
тельности, в которых элементы более или
менее отсортированы в обратном порядке.
Поэтому ее поведение несколько неестест-
венно. Если мы имеем дело с обратным по-
рядком, то фаза порождения пирамиды не
требует перемещений. Среднее число пере-
мещений приблизительно равно (n/2) *
log(n), причем отклонения от этого зна-
чения относительно невелики.
Другие статьи номера:
Похожие статьи:
В этот день... 21 ноября