Главная » Basic » ЭКСПЛУАТАЦИЯ ФАЙЛОВ

0

Методы обработки данных в больших файлах гораздо сложнее простых приемов, описанных ранее в данной  главе.  Поэтому  в  настоящем  разделе  предлагается  несколько  советов  тем,  кто   хочет разрабатывать на Бейсике программы для обработки данных.

Существенной  частью  эксплуатации  файлов  являются  поиск  отдельной  записи  и  модификация записей. Модификация состоит в добавлении новых документов или в удалении либо изменении уже существующих.

Термин "обработка данных" обычно связывают с наличием большого объема данных, хотя  слово "большой", вообще говоря, не поддается количественной оценке. Нетрудно видеть, что как  только объем данных вырастает до такой степени, что они уже не помещаются в памяти ЭВМ,  их объем можно рассматривать как большой; при этом для сортировки и поиска потребуются  совершенно иные методы по сравнению с теми, которые уже обсуждались в предыдущих главах.

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

ча записи не приведут к одному и тому же числу; в этом случае для помещения новой записи в файл применяют иной метод. Один из способов состоит в помещении новой информации в  свободную запись, ближайшую к уже занятой Конечно, механизм извлечения данных обязан  учитывать эту возможность при поиске требуемой записи.

Простой метод хэширования для поля, содержавшего фамилию, состоит в сложении кодов  ASCII всех букв и делении полученной суммы на простое число, несколько превышающее  максимально возможное число записей. Остаток от деления представляет собой число, лежащее между 0 и этим простым  числом;  его-то  и  можно  взять  в  качестве  хэшированного  адреса   данной  записи.  За детальными сведениями можно обратиться к многочисленной литературе.

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

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

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

По  описанной  выше  схеме  осуществляется  и  модификация  последовательного  файла.   Часто изменения основного файла происходят не при каждом запросе на изменение элементов  данных: запросы накапливаются в списке и вносятся в основной файл данных за один прием  (рис. 8.9). Список изменений обычно помещается в память ЭВМ, но его можно хранить и в специальном файле, "файле изменений".

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

Один из основных методов сортировки последовательного файла использует слияние  нескольких (более чем двух) файлов, каждый из которых соI держит много групп записей.  Каждая группа первоначально  способна  поместиться  в  памяти  ЭВМ,  где  ее  можно  отсортировать  внутренним образом. Этот метод называется многофазным слиянием; более детально о нем можно узнать в книге Peter Naur Concise Survey of Computer Methods,  выпущенной издательством Studentliteratur (Лунд, Швеция) в 1974 году.

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

считывается из файла 1 в память ЭВМ и сортируется там, а затем выводится в файл 2. Этот процесс повторяется;  когда будет достигнут конец файла 1, то в файле 2 ] будут    находиться    небольшие группы   отсортированных (внутри  группы) данных. Повторите этот процесс, переписав данные из файла 2 в файл 1, но использовав при этом другой размер рабочей области памяти, предназначенной для внутренней сортировки. Повторите еще раз, переписывая данные  из  файла 1 в файл 2 и т. д. Пусть при переносе данных в одном направлении, скажем из файла 1 в файл 2, область памяти для внутренней сортировки вмещает одно  и  то  же  число записей,  например 100,  а  при  переносе в обратном  направлении  число  сортируемых  в  памяти   записей  каждый  раз  меняется  (скажем, чередуется от 51 до 79). В противном случае возникает периодичность и полной сортировки файла данных никогда не произойдет; в результате он  окажется разбитым на отсортированные отрезки, длина которых равна произведению размеров  двух областей внутренней сортировки. Продолжайте процесс  переноса  данных  с  одной  ленты   на  другую  до  тех  пор,  пока  все  данные  не  будут отсортированы. Это  очень  длительный  процесс,  но  в  конце  концов  он  приводит  к  требуемому результату.

Источник: Уолш Б.    Программирование на Бейсике: Пер. с англ. М.: Радио и связь, 1988. 336 с: ил.

По теме:

  • Комментарии