S0rting FAQ 4/4
- From
- Ilia Kantor (2:5020/1815.6)
- To
- All
- Date
- 2002-05-01T22:26:22Z
- Area
- RU.ALGORITHMS
=== Cut ===
Сначала все данные располагаются на одной ленте. Лента читается и
отрезки распределяются по другим лентам, имеющимся в системе. после того,
как созданы начальные отрезки, они сливаются, как описано выше. Один из
методов, который можно использовать для создания начальных отрезков, состоит
в чтении порции записей в память, их сортировке и записи результата на
ленту. Выбор с замещением(см. другой вопрос) позволяет нам получать более
длинные отрезки. Этот алгоритм работает с буфером, располагающимся в
оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие
шаги до тех пор, пока не будут исчерпаны входные данные:
* Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >=
значения ключа последней прочитанной записи.
* Если все "старые" ключи меньше последнего ключа, то мы достигли конца
отрезка. Выбираем запись с наименьшим ключом в качестве первого
элемента следующего отрезка.
* Записываем выбранную запись.
* Заменяем выбранную и записанную запись на новую из входного файла.
На следующей таблице выбор с замещением иллюстрируются для совсем
маленького файла.
Начало файла - справа. Чтобы упростить пример, считается, что в буфер
помещается всего лишь 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] */
/* Найти наименьший ключ */
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;
}
Обращаю Ваше внимание на формат входного файла - это НЕ последовательность
чисел в обычном формате, а двоичный файл с элементами 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);
}
====================================================================
> 14. Есть большое количество слов. Как их отсортировать ?
====================================================================
Способ 1.
Во-первых, если хочется сортировать слова, то желательно иметь какое-то
отношение сравнения, то есть функцию, которая по двум словам
определяет, какое из них 'больше' и обладающую некоторыми свойствами.
Пример такой функции: лексикографическое сравнение, то есть
сравниваем буквы слова, начиная от первой. Если 1я буква одного слова
идет в алфавите перед 1й буквой другого слова, то оно меньше:
Даша < Маша.
Если буквы одинаковые, то смотрим 2ю букву и далее, при необходимости.
Абракадабра < Абрек
Если буквы в каком-то из слов кончились, то оно меньше:
Брахма < Брахман.
При сравнении слов пропускаются значки типа кавычек, апострофов и проч.
Дальше - если слова влезают в массив, то можно загрузить его в память
и применить имеющуюся почти во всех языках программирования процедуру
быстрой сортировки (в Си это qsort() ).
Если слова хранятся в большом файле - можно воспользоваться
многофазной сортировкой слияния, данной в другом вопросе.
Исходник придется немного изменить: во-первых, поменять keyType - тип
ключа, по которому сортируем. Это будет слово.
А, во-вторых, поменять операторы сравнения
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y),
например, на функцию сравнения, данную выше.
Способ 2.
Если слов много, и они невелики по длине, а максимальную длину слова мы
знаем _до_ запуска процедуры - можно воспользоваться распределяющей
сортировкой. Она может оказаться в разы быстрее.
Проблема тут в апострофах и других возможных лишних знаках, которые
можно как-то запоминать и убирать до сортировки и вставлять на место
- после (это один из вариантов решения).
====================================================================
> App. Использованная литература.
====================================================================
При составлении FAQ'а наиболее полно использовалась информация из
книги Дональда Кнута (D. Knuth)
'Искусство программирования на ЭВМ',
книги Николаса Вирта (Niklaus Wirth)
'Алгоритмы + Структуры Данных = Программы'
а также 'Краткое руководство по сортировке и поиску'
Томаса Нимана (Thomas Niemann), которое можно найти в интернете
по адресу http://epaperpress.com/sortsearch/russian/index.html
Приношу благодарности всем критиковавшим, а также высказывавшим
мудрые идеи и вопросы. === Cut ===
[Team Гитара][Team Former MUD-player][Team Chinese][Team NLP]
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)