Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Визуализация метода. Заключение

Визуализация метода | Характеристики метода | Визуализация метода | Характеристики метода | Вставка | Лабораторная работа «Списки», задание №9. | Лабораторная работа «Деревья», задание №6. |


Читайте также:
  1. Алгоритм метода множителей Лагранжа
  2. Архитектурная визуализация
  3. Базовый и производный классы. Конструкторы производного класса. Перегрузка методов при наследовании. Алгоритм выбора перегруженного метода.
  4. Вероятностная диагностика (скрининг) с использованием стратегия Байеса. Оценка информативности клинических признаков. Ограничения метода.
  5. Взаимоотношение между методами Пуассона-Абеля и Чезаро
  6. Взаимоотношение между методами Пуассона-Абеля и Чезаро
  7. Визуализация


Заключение

Внешняя сортировка методом поглощения позволяет сэкономить время и при не большом размере файла сортировка проходит быстро.

Реализация метода на C

/* external sort */

 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

/****************************

* implementation dependent *

****************************/

 

/* template for workfiles (8.3 format) */

#define FNAME "_sort%03d.dat"

#define LNAME 13

 

/* comparison operators */

#define compLT(x,y) (x < y)

#define compGT(x,y) (x > y)

 

/* define the record to be sorted here */

#define LRECL 100

typedef int keyType;

typedef struct recTypeTag {

keyType key; /* sort key for record */

#if LRECL

char data[LRECL-sizeof(keyType)]; /* other fields */

#endif

} recType;

 

/******************************

* implementation independent *

******************************/

 

typedef enum {false, true} bool;

 

typedef struct tmpFileTag {

FILE *fp; /* file pointer */

char name[LNAME]; /* filename */

recType rec; /* last record read */

int dummy; /* number of dummy runs */

bool eof; /* end-of-file flag */

bool eor; /* end-of-run flag */

bool valid; /* true if rec is valid */

int fib; /* ideal fibonacci number */

} tmpFileType;

 

static tmpFileType **file; /* array of file info for tmp files */

static int nTmpFiles; /* number of tmp files */

static char *ifName; /* input filename */

static char *ofName; /* output filename */

 

static int level; /* level of runs */

static int nNodes; /* number of nodes for selection tree */

 

void deleteTmpFiles(void) {

int i;

 

/* delete merge files and free resources */

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) {

 

/* cleanup files */

remove(ofName);

if (rc == 0) {

int fileT;

 

/* file[T] contains results */

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) {

 

/* cleanup tmp files and exit */

termTmpFiles(rc);

exit(rc);

}

 

void *safeMalloc(size_t size) {

void *p;

 

/* safely allocate memory and initialize to zero */

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;

 

/* initialize merge files */

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 { /* internal node */

struct iNodeTag *parent;/* parent of internal node */

struct eNodeTag *loser; /* external loser */

} iNodeType;

 

typedef struct eNodeTag { /* external node */

struct iNodeTag *parent;/* parent of external node */

recType rec; /* input record */

int run; /* run number */

bool valid; /* input record is valid */

} eNodeType;

 

typedef struct nodeTag {

iNodeType i; /* internal node */

eNodeType e; /* external node */

} nodeType;

 

static nodeType *node; /* array of selection tree nodes */

static eNodeType *win; /* new winner */

static FILE *ifp; /* input file */

static bool eof; /* true if end-of-file, input */

static int maxRun; /* maximum run number */

static int curRun; /* current run number */

iNodeType *p; /* pointer to internal nodes */

static bool lastKeyValid; /* true if lastKey is valid */

static keyType lastKey; /* last key written */

 

/* read next record using replacement selection */

 

/* check for first call */

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) {

 

/* replace previous winner with new record */

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;

}

 

/* adjust loser and winner pointers */

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 should be winner */

eNodeType *t;

 

t = p->loser;

p->loser = win;

win = t;

}

p = p->parent;

} while (p!= &node[0].i);

 

/* end of run? */

if (win->run!= curRun) {

/* win->run = curRun + 1 */

if (win->run > maxRun) {

/* end of output */

free(node);

return NULL;

}

curRun = win->run;

}

 

/* output top of tree */

if (win->run) {

lastKey = win->rec.key;

lastKeyValid = true;

return &win->rec;

}

}

}

 

void makeRuns(void) {

recType *win; /* winner */

int fileT; /* last file */

int fileP; /* next to last file */

int j; /* selects file[j] */

 

 

/* Make initial runs using replacement selection.

* Runs are written using a Fibonacci distintbution.

*/

 

/* initialize file structures */

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)) {

/* append to an existing run */

run = true;

} else if (file[j]->dummy) {

/* start a new run */

file[j]->dummy--;

run = true;

}

} else {

/* first run in file */

file[j]->dummy--;

run = true;

}

 

if (run) {

anyrun = true;

 

/* flush run */

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 no room for runs, up a level */

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) {

/* rewind file[j] and read in first record */

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;

 

/* polyphase merge sort */

 

fileT = nTmpFiles - 1;

fileP = fileT - 1;

 

/* prime the files */

for (j = 0; j < fileT; j++) {

rewindFile(j);

}

 

/* each pass through loop merges one run */

while (level) {

while(1) {

bool allDummies;

bool anyRuns;

 

/* scan for runs */

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;

 

/* merge 1 run file[0]..file[P] --> file[T] */

 

while(1) {

/* each pass thru loop writes 1 record to file[fileT] */

 

/* find smallest key */

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;

 

/* write record[k] to file[fileT] */

if (fwrite(&file[k]->rec, sizeof(recType), 1,

file[fileT]->fp)!= 1) {

perror("io6");

cleanExit(1);

}

 

/* replace record[k] */

lastKey = file[k]->rec.key;

if (fread(&file[k]->rec, sizeof(recType), 1,

file[k]->fp) == 1) {

/* check for end of run on 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);

}

}

 

/* fixup dummies */

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++;

}

 

/* end of run */

if (file[fileP]->eof &&!file[fileP]->dummy) {

/* completed a fibonocci-level */

level--;

if (!level) {

/* we're done, file[fileT] contains data */

return;

}

 

/* fileP is exhausted, reopen as new */

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;

 

/* start new runs */

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[]) {

 

/* command-line:

*

* ext ifName ofName nTmpFiles nNodes

*

* ext in.dat out.dat 5 2000

* reads in.dat, sorts using 5 files and 2000 nodes, output to 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;

}


 


Дата добавления: 2015-08-17; просмотров: 56 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Характеристики метода| Визуализация метода

mybiblioteka.su - 2015-2024 год. (0.046 сек.)