|
===========================================================================
> 13. Есть большой файл. Как его отсортировать ? Многофазная сортировка.
===========================================================================
В другом вопросе описывается простейшая сортировка слиянием. Ее вполне можно
применить к любому файлу и она будет работать.
Ниже мы разберем серьезно улучшенный алгоритм внешней сортировки слиянием
работающий намного быстрее.
Многофазная сортировка слиянием.
Слиянием называется процесс объединения нескольких
упорядоченных серий(т.е упорядоченных списков) в одну.
Пример для 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
Hа каждом шаге мы бе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
Стрелки показывают процесс слияния. Hапример, на втором шаге мы
слияем с f1, f2, f3, f4 и f6 на f5, пока одна из лент не опустеет.
В каждый момент времени слияние происходит на пустую ленту с остальных,
поэтому число требующихся проходов приблизительно равно log n.
N
Далее нам понадобятся числа Фибоначчи порядка p.
Они определяются следующим образом:
f_(i+1) = f_i + f_(i-1) + ... + f_(i-p) для i >=p,
f_p = 1,
f_i = 0 для 0 <= i < p.
Очевидно, обычные числа Фибоначчи имеют порядок 1.
В данном примере распределение начальных серий побрано искусственно.
Исходные числа серий для такой идеальной многофазной сортировки должны
быть суммами n-1 , n-2 , ... , 1 последовательных чисел Фибоначчи
порядка n-2.
Из этого следует, что наш алгоритм многофазного слияния применим только
к таким входным данным, в которых число серий есть сумма n-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 <stdio.h>
#include <stdlib.h>
#include <string.h>
/* темплейт для временных файлов (формат 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 long 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] */
/* Сделать инициализационные проходы через выбор с замещением.
* Проходы напиcаны с использованием распределения Фибоначчи.
*/
/* инициализовать файловые структуры */
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;
}
Обращаю Ваше внимание на формат входного файла - это HЕ последовательность
чисел в обычном формате, а двоичный файл с элементами recType.
Для проверки и демонстрации прилагаю две дополнительные программы:
Первая создает бинарный файл 'input' размера AMOUNT со случайными ключами.
Обратите внимание на соответствие типов keyType и recType -
они должны быть одинаковы здесь и в сортировке.
#include <stdio.h>
#include <stdlib.h>
#define AMOUNT 100 // Amount of data generated
#define LRECL 100
typedef long int keyType;
typedef struct recTypeTag {
keyType key; /* ключ, по которому сортируем */
#if LRECL
char data[LRECL-sizeof(keyType)]; /* остальные поля */
#endif
} recType;
void make_random (recType *data, long N) {
long int i;
for ( i=0; i < N; i++ ) data[i].key=rand()|(rand()<<16);
}
recType d[AMOUNT];
void main (void) {
FILE *f;
int i;
make_random(d, AMOUNT);
f=fopen("input","r+b");
for(i=0;i<AMOUNT;i++) fwrite(&d[i], sizeof(recType), 1, f);
fclose(f);
}
Вторая читает бинарный файл 'output' размера AMOUNT и выдает ключи в
порядке появления. Предположения о типах те же.
#include <stdio.h>
#include <stdlib.h>
#define AMOUNT 100 // Amount of data to be read
#define LRECL 100
typedef long int keyType;
typedef struct recTypeTag {
keyType key; /* ключ, по которому сортируем */
#if LRECL
char data[LRECL-sizeof(keyType)]; /* остальные поля */
#endif
} recType;
recType d[AMOUNT];
void main (void) {
FILE *f;
int i;
f=fopen("output","r+b");
for(i=0;i<AMOUNT;i++) {
fread(&d[i], sizeof(recType), 1, f);
printf("%ld\n", d[i].key);
}
fclose(f);
}
|
