Перейти на главную   
  helloworld.ru - документация и книги по программированию  
helloworld.ru - документация и книги по программированию    
    главная     хостинг     создание сайтов    
Поиск по сайту:  
Смотрите также
Языки программирования
C#
MS Visual C++
Borland C++
C++ Builder
Visual Basic
Quick Basic
Turbo Pascal
Delphi
JavaScript
Java
PHP
Perl
Assembler
AutoLisp
Fortran
Python
1C

Интернет-технологии
HTML
VRML
HTTP
CGI
FTP
Proxy
DNS
протоколы TCP/IP
Apache

Web-дизайн
HTML
Дизайн
VRML
PhotoShop
Cookie
CGI
SSI
CSS
ASP
PHP
Perl

Программирование игр
DirectDraw
DirectSound
Direct3D
OpenGL
3D-графика
Графика под DOS

Алгоритмы
Численные методы
Обработка данных

Системное программирование
Драйверы

Базы данных
MySQL
SQL

Другое

Хостинг


Друзья
demaker.ru
Реклама

Лучший хостинг. Аренда серверов




helloworld.ru

FAQ по СОРТИРОВКАМ версия 1.1

1. Ликбез для понимания важной информации: Что означает символ O(n)? Почему не пишется основание логарифма: O(log n)?
2. Какие на сегодняшний день самые эффективные методы сортировки?
3. Описание и исходник InsertSort (сортировка простыми вставками).
4. Описание и исходник QuickSort (быстрая сортировка).
5. Описание и исходник HeapSort (пирамидальная сортировка).
6. Требования QuickSort и HeapSort. InsertSort... Что лучше?
7. Какая самая быстрая сортировка?
8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка?
9. Что лучше: распределяющая сортировка или быстрая?
10.Есть большой файл. Как его отсортировать? Сортировка слиянием.

1. Ликбез для понимания важной информации: Что означает символ O(n)? Почему не пишется основание логарифма: O (log n)?


A: Kantor Ilia - Tomas Niemann
Оценки времени исполнения. Cимвол O().

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

Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n^2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.

     n       log n   n*log n            n^2
   1           0     0             1
   16          4     64            256
   256         8     2,048         65,536
   4,096       12    49,152        16,777,216
   65,536      16    1,048,565     4,294,967,296
   1,048,476   20    20,969,520    1,099,301,922,576
   16,775,616  24    402,614,784   281,421,292,179,456

Если считать, что числа в таблице соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, а алгоритму с временем работы O(n^2) - более 12 дней.

Если оба алгоритма, например, O ( n*log n ), то это отнюдь не значит, что они одинакого эффективны.

Символ О не учитывает константу, то есть первый может быть, скажем в 1000 раз эффективнее. Это значит лишь то, что их время возрастает приблизительно как функция n*log n.

За функцию берется количество операций, возрастающее быстрее всего.

То есть если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n^2) раз, то общая сложность - O(n^2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут тормозить куда больше, нежели медленные, но редкие умножения.

Основание логарифма не пишется.

Причина этого весьма проста. Пусть у нас есть O(log2_n). Hо log2_n = log3_n / log3_2, а log3_2, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O(log2_n) = O( log3_n). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла.

2. Какие на сегодняшний день самые эффективные методы сортировки?

A: Kantor Ilia

быстрая сортировка, распределяющая сортировка и быстрая сортировка с составными ключами, которая слишком сложна для ФАКа.

Для прикладных задач, использующих элементы сортировки также очень полезна пирамидальная сортировка.

3. Сортировка простыми вставками.

A: Kantor Ilia - Nicolas Virt - Tomas Niemann ;-)) Алгоритм

Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.

             Пример:

  Hачальные ключи         44 \\ 55 12 42 94 18 06 67
           i = 2          44 55 \\ 12 42 94 18 06 67
           i = 3          12 44 55 \\ 42 94 18 06 67
           i = 4          12 42 44 55 \\ 94 18 06 67
           i = 5          12 42 44 55 94 \\ 18 06 67
           i = 6          12 18 42 44 55 94 \\ 06 67
           i = 7          06 12 18 42 44 55 94 \\ 67
           i = 8          06 12 18 42 44 55 67 94 \\

При поиске подходящего места удобно 'просеивать' x, сравнивая его с очередным элементом ai и либо вставляя его, либо пересылая ai направо и продвигаясь налево.

Просеивание может кончиться при двух условиях:

1. Hайден ai с ключом, меньшим x.

2. Достигнут конец готовой последовательности.

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

Анализ
        Число сравнений
                             минимальное:           n - 1
                             среднее:         ( n^2 + n - 2 ) / 4
                             максимальное:   ( n^2 + n ) * / 2 - 1
        Количество пересылок
                             минимальное:       2 * ( n - 1 )

                             среднее:      ( n^2 + 9 * n - 10 ) / 4

                             максимальное:  ( n^2 + 3 * n - 4 ) / 2

        Пример на Си - Tomas Niemann.
--------------------------------------------------------------------
typedef int item;          /* Тип сортируемых элементов */
typedef int tblIndex;      /* Тип ключей, по которым сортируем */

#define compGT(a,b) (a > b)   /* Функция сравнения  */

void insertSort(T *a, tblIndex lb, tblIndex ub) {
    item t;
    tblIndex i, j;

   /***********************
    * сортируем a[lb..ub] *
    ***********************/
    for (i = lb + 1; i <= ub; i++) {
        t = a[i];

        /* Сдвигаем элементы вниз, пока */
        /*  не найдем место вставки.    */
        for (j = i-1; j >= lb && compGT(a[j], t); j--)
            a[j+1] = a[j];

        /* вставка */
        a[j+1] = t;
    }
}

4. Описание и исходник QuickSort (быстрая сортировка).

Основной алгоритм

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

В результате массив разделится на две части: левую - с ключами, меньшими х и правую - с ключами, большими х.

Этот шаг называется разделением. Х - центром.

К получившимся частям рекурсивно применяем ту же процедуру.

В результате получается очень эффективная сортировка

 Пример рекурсивной QuickSort
------------------------------------
typedef int item;       /* Тип сортируемых элементов */
typedef int tblIndex;   /* Тип ключей, по которым сортируем */

#define CompGT(a,b) (a > b)

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
     item t, pivot;
    tblIndex i, j, p;

   /**********************************
    *  разделение массива a[lb..ub]  *
    **********************************/

    /* Выбираем центр - pivot */
    p = lb + ((ub - lb)>>1);
    pivot = a[p];
    a[p] = a[lb];

    /* сортируем lb+1..ub относительно центра */
    i = lb+1;
    j = ub;
    while (1) {
        while (i < j && compGT(pivot, a[i])) i++;
        while (j >= i && compGT(a[j], pivot)) j--;
        if (i >= j) break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        j--; i++;
    }

    /* центр в a[j] */
    a[lb] = a[j];
    a[j] = pivot;

    return j;
}

void quickSort(T *a, tblIndex lb, tblIndex ub) {
    tblIndex m;

   /**************************
    *  сортируем  a[lb..ub]  *
    **************************/

    while (lb < ub) {

        /* сортировка вставками для малых массивов */
        if (ub - lb <= 12) {
            insertSort(a, lb, ub);
            return;
        }

        /* разделение пополам */
        m = partition (a, lb, ub);

        /* Уменьшаем требования к памяти:    */
        /*  меньший сегмент сортируем первым */
        if (m - lb <= ub - m) {
            quickSort(a, lb, m - 1);
            lb = m + 1;
        } else {
            quickSort(a, m + 1, ub);
            ub = m - 1;
        }
    }
}
Улучшения

Hа практике для увеличения быстроты, но не асимптотики, можно произвести несколько улучшений:

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

1' Можно выбрать средний из первого, последнего и среднего элементов. Maxim Razin: Тогда количество проходов уменьшится в 7/6 раз.

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

3. Если последний оператор функции является вызовом этой функции, говорят о хвостовой рекурсии. Ее имеет смысл заменять на итерации - в этом случае лучше используется стек.

4. После разбиения сначала сортируется меньший раздел. Это также приводит к лучшему использованию стека, поскольку короткие разделы сортируются быстрее и им нужен более короткий стек. Требования к памяти уменьшаются с n до log n.

Пример, входящий в стандартную реализацию Си использует многие из этих улучшений.

Стандартная реализация итерационной QuickSort
------------------------------------------------

#include 
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)

static void exchange(void *a, void *b, size_t size) {
    size_t i;

    /******************
     *  обменять a,b  *
     ******************/

    for (i = sizeof(int); i <= size; i += sizeof(int)) {
        int t = *((int *)a);
        *(((int *)a)++) = *((int *)b);
        *(((int *)b)++) = t;
    }
    for (i = i - sizeof(int) + 1; i <= size; i++) {
        char t = *((char *)a);
        *(((char *)a)++) = *((char *)b);
        *(((char *)b)++) = t;
    }
}

void qsort(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *)) {
    void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
    int sp;
    unsigned int offset;

    lbStack[0] = (char *)base;
    ubStack[0] = (char *)base + (nmemb-1)*size;
    for (sp = 0; sp >= 0; sp--) {
        char *lb, *ub, *m;
        char *P, *i, *j;

        lb = lbStack[sp];
        ub = ubStack[sp];

        while (lb < ub) {

            /* выбираем центр и меняемся с 1м элементом */
            offset = (ub - lb) >> 1;
            P = lb + offset - offset % size;
            exchange (lb, P, size);

            /* разделение в два сегмента */
            i = lb + size;
            j = ub;
            while (1) {
                while (i < j && compar(lb, i) > 0) i += size;
                while (j >= i && compar(j, lb) > 0) j -= size;
                if (i >= j) break;
                exchange (i, j, size);
                j -= size;
                i += size;
            }

            /* центр в A[j] */
            exchange (lb, j, size);
            m = j;

            /* Меньший сегмент продолжаем обрабатывать, больший - в стек */
            if (m - lb <= ub - m) {
                if (m + size < ub) {
                    lbStack[sp] = m + size;
                    ubStack[sp++] = ub;
                }
                ub = m - size;
            } else {
                if (m - size > lb) {
                    lbStack[sp] = lb;
                    ubStack[sp++] = m - size;
                }
                lb = m + size;
            }
        }
    }
}

5. Описание и исходник HeapSort (пирамидальная сортировка).

A: Kantor Ilia - Nicolas Virt

Hазовем пирамидой последовательность элементов

  hl , hl+1 , ... , hr
     такую, что
  hi <= h2i
  hi <= h2i+1
  для всякого i = l , ... , r/2
  Геометрическая интерпретация пиромиды:

                      h1
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
               h2            h3
              / \            / \
             /   \          /   \
           h4    h5       h6     h7
          /  \  /  \     / \   /  \
         h8  h9 h10 h11  h12 h13 h14 h15

      Для последовательности 06 42 12 55 94 18 44

                      06
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
               42            12
              / \            / \
             /   \          /   \
           55    94        18   44

Добавление элемента в готовую пирамиду

1. Hовый элемент Х помещаем в вершину дерева.

2. Смотрим на элемент слева и элемент справа - выбираем наименьший.

3. Если этот элемент меньше Х - меняем их местами и идем у шагу 2. Иначе конец процедуры.

Фаза 1: построение пирамиды

Пусть дан массив h1 ... hn . Ясно, что элементы hn/2 + 1 ... hn уже образуют 'нижний ряд' пирамиды, так как не существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То есть тут упорядочивания не требуется.

Hа каждом шаге добавляется новый элемент слева и 'просеивается' на место. Вот иллюстрация процесса для пирамиды из 8-и элементов:

     44  55  12  42  //  94  18  06  67
     44  55  12  //  42  94  18  06  67
     44  55  //  06  42  94  18  12  67
     44  //  42  06  55  94  18  12  67
     //  06  42  12  55  94  18  44  67

Фаза 2: сортировка

Для того, чтобы рассортировать элементы, необходимо выполнить n шагов просеивания: после каждого шага очередной элемент берется с вершины пирамиды. Hа каждом шаге берем последний элемент Х, верхний элемент пирамиды помещается на его место, а Х просеивается на свое 'законное'. В этом случае необходимо совершить n - 1 шагов. Пример:

      06  42  12  55  94  18  44  67  //
      12  42  18  55  94  67  44  //  06
      18  42  44  55  94  67  //  12  06
      42  55  44  67  94  //  18  12  06
      44  55  94  67  //  42  18  12  06
      55  67  94  //  44  42  18  12  06
      67  94  //  55  44  42  18  12  06
      94  //  67  55  44  42  18  12  06

Hу вот мы м получили отсортированную последовательность, только в обратном порядке. Изменяя сравнения на противоположные, получаем функцию Heapsort на Паскале

Прекрасной характеристикой этого метода является то, что среднее число пересылок - (n*log n)/2 и отклонения от этого значения сравнительно малы.

{ сортируем массив типа 'item' по ключу 'a.key' }

procedure Heapsort;
 var i,l: index; x: item;

procedure sift;
 label 13;
 var i, j: index;
begin i := l; j := 2*i; x := a[i];
 while j <= r do
 begin if j < r then
  if a[j].key < a[j+1].key then j := j+1;
  if x.key >= a[j].key then goto 13;
  a[i] := a[j]; i := j; j := 2*i
 end;
 13: a[i] := x
 end;

 begin l := (n div 2) + 1; r := n;
  while l > 1 do
   begin l := l - 1; sift
   end;

  while r > 1 do
   begin x := a[l]; a[l] := a[r]; a[r] := x;
     r := r - 1; sift
 end
end { heapsort }

6. Требования QuickSort и HeapSort. InsertSort... Что лучше?

A: Kantor Ilia
Простые вставки.

Общее быстродействие - O( n^2 ), но ввиду простоты метода, является наибыстрейшим для малых ( 12-20 элементов ) массивов.

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

Сортировка не требует дополнительной памяти.

Быстрая сортировка

Общее быстродействие - O( nlogn ). Случай n^2 теоретически возможен, но крайне [ 1 / (n^logn) ] маловероятен.

В общем и целом - наиболее быстрая сортировка сравнениями для разупорядоченных массивов с >50 элементами.

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

Итерационный вариант требует logn памяти, рекурсивный - O(n).

Пирамидальная сортировка.

В 1.5 раза медленнее быстрой. Hаихудшего случая нет - всегда O(nlogn). Практически, ее элементы часто применяются в смежных задачах.

Поведение неестественно.

Основное достоинство - сортировка не требует дополнительной памяти.

7. Какая самая быстрая сортировка?

A: Kantor Ilia

Давайте разберемся раз и навсегда. Есть два типа сортировок:

 Распределяющая и ее вариации        |       Сортировка сравнениями
                                     |
Основана на том, что число возможных |   Пользуется лишь возможностью
 значений ключа конечно.             |     прямого сравнения ключей и
                                     |        их упорядоченностью.
                                     |    Quicksort, Heapsort...

Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: O(nlog n).

Для сортировок распределением это - O(n). Быстрее сортировать нельзя.

 Итак, наибыстрейшие сортировки -
    Quicksort - быстрая,
    Radix sort - распределяющая
           и их молодой гибрид:
    Multiway Quicksort /MQS / - быстрая с составными ключами.
        апример, для строк.

Вообще, нужно смотреть по данным и имеющимся в наличии ресурсам, но в типичных случаях наибыстрейшими решениями станут <см выше>.

8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка?

A: Kantor Ilia

К сожалению, или к счастью, единица информации в современной технике способна применять лишь 2 значения: 1 и 0.

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

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

Разрядность данных ( количество возможных значений элементов k) - m.

Если мы сортируем слова, то элемент сортировки - буква. m = 33. Если в самом длинном слове 10 букв, k = 10.

Обычно мы будем сортировать данные по ключам из k байт, m=255.


Пусть у нас есть массив source из n элементов по одному байту в каждом.

Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 }, и проделать с ним все операции, имея в виду m=9.

I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и заполняться она будет так:

for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;

Для нашего примера будем иметь distr = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }, то есть i-ый элемент distr[] - количество ключей со значением i.

     Заполним таблицу индексов:

int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];

В index[i] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i.

Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.

     А теперь заполняем новосозданный массив sorted размера n:

for ( i = 0; i < n ; i++ )
     {
      sorted[ index[ source[i] ] ]=source[i];
// попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
      index[ source[i] ] = index[ source[i] ] +1;
     }

     Итак, мы научились за O ( n ) сортировать байты. А от байтов до строк
и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

  Будем действовать в десятичной системе и сортировать обычные числа
 ( m = 10 ).

      сначала они в        сортируем по младшему     на один
       беспорядке:               разряду:             выше:     и еще раз:
           523                      523                523         088
           153                      153                235         153
           088                      554                153         235
           554                      235                554         523
           235                      088                088         554

Hу вот мы и отсортировали за O ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'!

Реализация на C++ для long int'ов. Сам не делал - валялась в и-нете.

 #include 
 #include < stdlib.h>
 #include < string.h>

 void radix (int byte, long N, long *source, long *dest)
 {
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i>(byte*8))&0xff]++;
  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for(i=0;i>(byte*8))&0xff]++]=source[i];
 }

 void radixsort (long *source, long *temp, long N)
 {
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
 }

 void make_random (long *data, long N)
 {
  for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
 }

 long data[10000];
 long temp[10000];

 void main (void)
 {
  make_random(data, 10000);
  radixsort (data, temp, 10000);
  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
 }

9. Что быстрее: распределяющая сортировка или QuickSort?

A: Kantor Ilia

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

Различных ключей очень много, размер массива сравнительно небольшой - быстрая.

10. Есть большой файл. Как его отсортировать?

A: Kantor Ilia - Tomas Niemann Многофазная сортировка

Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну.

 Пример для 3-х серий, слияемых на 4-ю:

    3 7 9      3 7 9        3 7 9          7 9             7 9
  { 2 4 6  1 { 2 4 6  1 2 { 4 6    1 2 3 { 4 6   1 2 3 4 { 6
    1 5 8      5 8          5 8            5 8             5 8

               7 9                7 9                 9
   1 2 3 4 5 { 6    1 2 3 4 5 6 { 8     1 2 3 5 6 7 { 8   1 2 3 4 5 6 7 8 9 {
               8

Каждый pаз мы беpем свеpху наименьший элемент.

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

Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем слиять элементы со входных лент на выходную, пока какая-либо из них не опустеет. Затем она станет входной.

Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии обозначены буквами fi, в таблице - количество элементов.

    Тип     f1      f2     f3     f4     f5      f6

            16      15     14     12     8
            8       7      6      4      0       8
            4       3      2      0      4       4
            2       1      0      2      2       2
            1       0      1      1      1       1
            0       1      0      0      0       0

В каждый момент времени слияние происходит на пустую ленту с остальных, поэтому число требующихся проходов приблизительно равно log N n. В данном примере распределение начальных серий побрано искусственно. Для идеальной сортировки исходные числа серий должны быть суммами n - 1 , n - 2 , ... , 1 последовательных чисел Фибоначчи порядка n - 2.

      Число Фибоначчи порядка p определяются следующим образом:
 fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p,
 fp(p) = 1,
 fi(p) = 0 для 0 <= i < p.

Очевидно, обычные числа Фибоначчи имеют порядок 1.

Поэтому предположим существование фиктивных серий, таких что сумма фиктивных с реальными дает идеальное число.

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

  • Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >= значения ключа последней прочитанной записи.
  • Если все "старые" ключи меньше последнего ключа, то мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве первого элемента следующего отрезка.
  • Записываем выбранную запись.
  • Заменяем выбранную и записанную запись на новую из входного файла.

Hа следующей таблице выбор с замещением иллюстрируются для совсем маленького файла.

Hачало файла - справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего.

                      Шаг    Вход     Буфер     Выход
                       A  5-3-4-8-6-7
                       B  5-3-4-8     6-7
                       C  5-3-4       8-7   6
                       D  5-3         8-4   7-6
                       E  5           3-4   8-7-6
                       F              5-4   3 | 8-7-6
                       G              5     4-3 | 8-7-6
                       H                    5-4-3 | 8-7-6

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

Прочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь log n сравнений.

Реализация

В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.

/* внешняя сортировка */

#include 
#include 
#include 

/* темплейт для временных файлов (формат 8.3) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* операторы сравнения */
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y)

/* определяем сортируемые записи */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
    keyType key;                         /* ключ, по которому сортируем */
    #if LRECL
        char data[LRECL-sizeof(keyType)];       /* остальные поля */
    #endif
} recType;

typedef enum {false, true} bool;

typedef struct tmpFileTag {
    FILE *fp;                   /* указатель на файл */
    char name[LNAME];           /* имя файла */
    recType rec;                /* последняя прочитанная запись */
    int dummy;                  /* номер холостых проходов */
    bool eof;                   /* флаг конца пробега end-of-file */
    bool eor;                   /* флаг конца прохода end-of-run */
    bool valid;                 /* верно, если запись - годная */
    int fib;                    /* идеальное число Фибоначчи */
} tmpFileType;

static tmpFileType **file;      /* массив информации о временных файлах */
static int nTmpFiles;           /* количество временных файлов */
static char *ifName;            /* имя входного файла */
static char *ofName;            /* имя выходного файла */

static int level;               /* уровень проходов */
static int nNodes;              /* количество узлов для дерева выбора */

void deleteTmpFiles(void) {
    int i;

    /* удалить сливаемые файлы и освободить ресурсы */
    if (file) {
        for (i = 0; i < nTmpFiles; i++) {
            if (file[i]) {
                if (file[i]->fp) fclose(file[i]->fp);
                if (*file[i]->name) remove(file[i]->name);
                free (file[i]);
            }
        }
        free (file);
    }
}

void termTmpFiles(int rc) {

    /* очистить файлы */
    remove(ofName);
    if (rc == 0) {
        int fileT;

        /* file[T] содержит результаты */
        fileT = nTmpFiles - 1;
        fclose(file[fileT]->fp); file[fileT]->fp = NULL;
        if (rename(file[fileT]->name, ofName)) {
            perror("io1");
            deleteTmpFiles();
            exit(1);
        }
        *file[fileT]->name = 0;
    }
    deleteTmpFiles();
}

void cleanExit(int rc) {

    /* очистить временные файлы и выйти */
    termTmpFiles(rc);
    exit(rc);
}

void *safeMalloc(size_t size) {
    void *p;

    /* Безопасно выделить память и инициализоваться */
    if ((p = calloc(1, size)) == NULL) {
        printf("error: malloc failed, size = %d\n", size);
        cleanExit(1);
    }
    return p;
}

void initTmpFiles(void) {
    int i;
    tmpFileType *fileInfo;

    /* инициализовать файлы для слияния */
    if (nTmpFiles < 3) nTmpFiles = 3;
    file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
    fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
    for (i = 0; i < nTmpFiles; i++) {
        file[i] = fileInfo + i;
        sprintf(file[i]->name, FNAME, i);
        if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
            perror("io2");
            cleanExit(1);
        }
    }
}

recType *readRec(void) {

    typedef struct iNodeTag {   /* внутренний узел */
        struct iNodeTag *parent;/* предок внутреннего узла */
        struct eNodeTag *loser; /* внешний проигравший */
    } iNodeType;

    typedef struct eNodeTag {   /* внешний узел */
        struct iNodeTag *parent;/* предок внешнего узла */
        recType rec;            /* вводимая запись */
        int run;                /* номер прохода */
        bool valid;             /* вводимая запись годна */
    } eNodeType;

    typedef struct nodeTag {
        iNodeType i;            /* внутренний узел */
        eNodeType e;            /* внешний узел */
    } nodeType;

    static nodeType *node;      /* массив узлов дерева выбора */
    static eNodeType *win;      /* новый победитель */
    static FILE *ifp;           /* входной файл */
    static bool eof;            /* верно, если конец входного файла */
    static int maxRun;          /* максимальное число проходов */
    static int curRun;          /* номер текущего прохода */
    iNodeType *p;               /* указатель на внутренние узлы */
    static bool lastKeyValid;   /* верно, если lastKey годен */
    static keyType lastKey;     /* последний ключ lastKey записан */

    /* Прочитать следующую запись путем выбора с замещением */

    /* Проверка на первый выхов */
    if (node == NULL) {
        int i;

        if (nNodes < 2) nNodes = 2;
        node = safeMalloc(nNodes * sizeof(nodeType));
        for (i = 0; i < nNodes; i++) {
            node[i].i.loser = &node[i].e;
            node[i].i.parent = &node[i/2].i;
            node[i].e.parent = &node[(nNodes + i)/2].i;
            node[i].e.run = 0;
            node[i].e.valid = false;
        }
        win = &node[0].e;
        lastKeyValid = false;

        if ((ifp = fopen(ifName, "rb")) == NULL) {
            printf("error: file %s, unable to open\n", ifName);
            cleanExit(1);
        }
    }

    while (1) {

        /* заместить предыдущего победителя новой записью */
        if (!eof) {
            if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
                if ((!lastKeyValid || compLT(win->rec.key, lastKey))
                && (++win->run > maxRun))
                    maxRun = win->run;
                win->valid = true;
            } else if (feof(ifp)) {
                fclose(ifp);
                eof = true;
                win->valid = false;
                win->run = maxRun + 1;
            } else {
                perror("io4");
                cleanExit(1);
            }
        } else {
            win->valid = false;
            win->run = maxRun + 1;
        }

        /* привести в порядок предков победителя и проигравшего */
        p = win->parent;
        do {
            bool swap;
            swap = false;
            if (p->loser->run < win->run) {
                swap = true;
            } else if (p->loser->run == win->run) {
                if (p->loser->valid && win->valid) {
                    if (compLT(p->loser->rec.key, win->rec.key))
                        swap = true;
                } else {
                    swap = true;
                }
            }
            if (swap) {
                /* p должно быть победителем */
                eNodeType *t;

                t = p->loser;
                p->loser = win;
                win = t;
            }
            p = p->parent;
        } while (p != &node[0].i);

        /* конец прохода ? */
        if (win->run != curRun) {
            /* win->run = curRun + 1 */
            if (win->run > maxRun) {
                /* конец вывода */
                free(node);
                return NULL;
            }
            curRun = win->run;
        }

        /* вывести верх дерева */
        if (win->run) {
            lastKey = win->rec.key;
            lastKeyValid = true;
            return &win->rec;
        }
    }
}

void makeRuns(void) {
    recType *win;       /* победитель */
    int fileT;          /* прошлый файл */
    int fileP;          /* следующий за прошлым файлом  */
    int j;              /* выбираем file[j] */


    /* Сделать инициализационные проходы через выбор с замещением.
     * Проходы напианы с использованием распределения Фибоначчи.
     */

    /* инициализовать файловые структуры */
    fileT = nTmpFiles - 1;
    fileP = fileT - 1;
    for (j = 0; j < fileT; j++) {
        file[j]->fib = 1;
        file[j]->dummy = 1;
    }
    file[fileT]->fib = 0;
    file[fileT]->dummy = 0;

    level = 1;
    j = 0;


    win = readRec();
    while (win) {
        bool anyrun;

        anyrun = false;
        for (j = 0; win && j <= fileP; j++) {
            bool run;

            run = false;
            if (file[j]->valid) {
                if (!compLT(win->key, file[j]->rec.key)) {
                    /* добавить к существующему проходу */
                    run = true;
                } else if (file[j]->dummy) {
                    /* начать новый проход */
                    file[j]->dummy--;
                    run = true;
                }
            } else {
                /* первый проход в файле */
                file[j]->dummy--;
                run = true;
            }

            if (run) {
                anyrun = true;

                /* полный проход */
                while(1) {
                    if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
                        perror("io3");
                        cleanExit(1);
                    }
                    file[j]->rec.key = win->key;
                    file[j]->valid = true;
                    if ((win = readRec()) == NULL) break;
                    if (compLT(win->key, file[j]->rec.key)) break;
                }
            }
        }

        /* Если нет места для проходов - вверх на уровень */
        if (!anyrun) {
            int t;
            level++;
            t = file[0]->fib;
            for (j = 0; j <= fileP; j++) {
                file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
                file[j]->fib = t + file[j+1]->fib;
            }
        }
    }
}

void rewindFile(int j) {
    /* Идти в начало file[j] и читать первую запись */
    file[j]->eor = false;
    file[j]->eof = false;
    rewind(file[j]->fp);
    if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
        if (feof(file[j]->fp)) {
            file[j]->eor = true;
            file[j]->eof = true;
        } else {
            perror("io5");
            cleanExit(1);
        }
    }
}

void mergeSort(void) {
    int fileT;
    int fileP;
    int j;
    tmpFileType *tfile;

    /* Многофазная сортировка слиянием */

    fileT = nTmpFiles - 1;
    fileP = fileT - 1;

    /* снабдить файлы информацией */
    for (j = 0; j < fileT; j++) {
        rewindFile(j);
    }

    /* Каждый проход по циклу сливает один проход */
    while (level) {
        while(1) {
            bool allDummies;
            bool anyRuns;

            /* сканировать на предмет проходов */
            allDummies = true;
            anyRuns = false;
            for (j = 0; j <= fileP; j++) {
                if (!file[j]->dummy) {
                    allDummies = false;
                    if (!file[j]->eof) anyRuns = true;
                }
            }

            if (anyRuns) {
                int k;
                keyType lastKey;

                /* слить 1 проход file[0]..file[P] --> в file[T] */

                while(1) {
                   /* Каждый проход по циклу записывает 1 запись в file[fileT]
*/

                    /* Hайти наименьший ключ */
                    k = -1;
                    for (j = 0; j <= fileP; j++) {
                        if (file[j]->eor) continue;
                        if (file[j]->dummy) continue;
                        if (k < 0 ||
                        (k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
                            k = j;
                    }
                    if (k < 0) break;

                    /* записать record[k] в file[fileT] */
                    if (fwrite(&file[k]->rec, sizeof(recType), 1,
                            file[fileT]->fp) != 1) {
                        perror("io6");
                        cleanExit(1);
                    }

                    /* заменить record[k] */
                    lastKey = file[k]->rec.key;
                    if (fread(&file[k]->rec, sizeof(recType), 1,
                            file[k]->fp) == 1) {
                        /* проверить на предмет конца пробега file[s] */
                        if (compLT(file[k]->rec.key, lastKey))
                            file[k]->eor = true;
                    } else if (feof(file[k]->fp)) {
                        file[k]->eof = true;
                        file[k]->eor = true;
                    } else {
                        perror("io7");
                        cleanExit(1);
                    }
                }

                /* Подкорректировкать холостые */
                for (j = 0; j <= fileP; j++) {
                    if (file[j]->dummy) file[j]->dummy--;
                    if (!file[j]->eof) file[j]->eor = false;
                }

            } else if (allDummies) {
                for (j = 0; j <= fileP; j++)
                    file[j]->dummy--;
                file[fileT]->dummy++;
            }

            /* конец прохода */
            if (file[fileP]->eof && !file[fileP]->dummy) {
                /* completed a fibonocci-level */
                level--;
                if (!level) {
                    /* готово, file[fileT] содержит данные */
                    return;
                }

                /* fileP истощился, открываем новый такой же */
                fclose(file[fileP]->fp);
                if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
                        == NULL) {
                    perror("io8");
                    cleanExit(1);
                }
                file[fileP]->eof = false;
                file[fileP]->eor = false;

                rewindFile(fileT);

                /* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
                tfile = file[fileT];
                memmove(file + 1, file, fileT * sizeof(tmpFileType*));
                file[0] = tfile;

                /* начать новые проходы */
                for (j = 0; j <= fileP; j++)
                    if (!file[j]->eof) file[j]->eor = false;
            }
        }

    }
}


void extSort(void) {
    initTmpFiles();
    makeRuns();
    mergeSort();
    termTmpFiles(0);
}

int main(int argc, char *argv[]) {

    /* командная строка:
     *
     *   ext ifName ofName nTmpFiles nNodes
     *
     *   ext in.dat out.dat 5 2000
     *       читает in.dat, сортирует, используя 5 файлов и 2000 узлов,
     *        выводит в out.dat
     */
    if (argc != 5) {
        printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
        cleanExit(1);
    }

    ifName = argv[1];
    ofName = argv[2];
    nTmpFiles = atoi(argv[3]);
    nNodes = atoi(argv[4]);

    printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
        nTmpFiles, nNodes, sizeof(recType));

    extSort();

    return 0;
}










helloworld.ru © 2001-2016
Все права защищены
Rambler's Top100 TopList Rambler's Top100