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),  причем отклонения от этого зна-
чения относительно невелики.