Когда скорость ввода-вывода не является „узким местом"

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

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

Рассмотрим случай, когда "узким местом" является слияние, а не считывание или запись данных. Это может произойти по следующим причинам.

1. Как мы уже видели, если в нашем распоряжении есть много дисководов или на­копителей на магнитной ленте, ввод-вывод можно ускорить настолько, что время для выполнения слияния превысит время ввода-вывода.

2. Может стать экономически выгодным применение более быстродействующих ка­налов обмена данными.

Поэтому имеет смысл подробнее рассмотреть проблему, с которой можно столк­нуться в случае, когда "узким местом" в процессе сортировки слиянием данных, хранящихся во вторичной памяти, становится их объединение. Сделаем следующие предположения.

1. Мы объединяем серии, размеры которых намного превышают размеры блоков.

2. Существуют два входных и два выходных файла. Входные файлы хранятся на одном внешнем диске (или каком-то другом устройстве, подключенном к основ­ной памяти одним каналом), а выходные файлы — на другом подобном устрой­стве с одним каналом.

3. Время считывания, записи и выбора для заполнения блока записей с наимень­шими ключами среди двух серий, находящихся в данный момент в основной памяти, одинаково.

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

Выполняются (возможно, одновременно) следующие действия.

1. Считывание входного блока во входной буфер.

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

3. Запись данных другого выходного буфера в один из двух формируемых выход­ных файлов.

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

Условия, при которых слияние можно выполнять параллельно со считыванием, достаточно просты. Допустим, k₁ и k₂ — наибольшие ключи среди невыбранных за­писей в основной памяти из первой и второй серий соответственно. В таком случае в основной памяти должно быть по крайней мере b невыбранных записей, ключи ко­торых не превосходят min(k_l, k₂).

ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ

Вопрос 4.1. Количество информации и энтропии. Формулы Хартли и Шеннона

Количество информации и энтропия. Формулы Хартли и Шеннона

Количество информации в дискретном сообщении. Энтропия

Дискретный источник сообщений – источник сообщений, принимающий случайным образом одно из конечного множества возможных состояний U в каждый момент времени. Совокупность состояний u₁, u₂,..,u_i,..,u_N источника называют его алфавитом, а количество состояний N ‑ объемом алфавита. Таким образом, дискретное сообщение – это символ u_i, выдаваемый источником, при этом источник может выдать дискретное сообщение в виде последовательности элементарных дискретных сообщений, представляющей сбой набор символов u_i (например, u₅, u₁, u₃) каждый из которых имеет длительность t_i секунд. Такая модель источника сообщений соответствует реальной ситуации имеющей место в телеграфии (t_iconst) и передаче данных (t_i=const). В общем случае источник хранится дискретным ансамблем U: ,

При выдаче источником сообщений в виде последовательности элементарных дискретных сообщений, полным вероятностным описанием является вероятность совместного появления набора различных символов u_i в момент t₁, t₂,...,t_n, где n ‑ длина последовательности

.

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

Если функция не меняется во времени, т.е. если она при любых , то источник называется стационарным.

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

Мера неопределенности источника с равновероятными состояниями и характеризующего его ансамбля U это логарифм объема алфавита источника H(U)=log N (1.1).

Легко видеть, что:

1. с ростом N величина H(U) монотонно возрастает.

2. в случае если объем алфавита источника N равен 1, т.е. когда неопределенность отсутствует, H(U)=log 1=0

3. величина H(U) обладает свойством аддитивности, поскольку log(N*M)=log(N)+log(M).

Впервые данная мера была предложена Хартли в 1928г. Основание логарифма в формуле не имеет принципиального значения и определяет только масштаб или единицу количества информации. Если основание равно 2, то единица количества информации называется двоичной единицей или битом. Если 10, то дитом или хартли. Если же равна е, то натом.

В общем случае, если вероятности различных состояний источника не одинаковы, степень неопределенности конкретного состояния зависит не только от объема алфавита источника, но и от вероятности этого состояния, тогда (1.2). Знак минус в первом равенстве (1.2) необходим для того, чтобы количество информации i(u_k) было неотрицательным числом т.к. всегда P(u_k)1. Очевидно что, так же как и мера H(U) определяемая (1.1) величина i(u_k) обладает свойством аддитивности. И в случае достоверного сообщения, когда P(u_k)=1, i(u_k)=0. Количество информации в сообщении тем больше, чем оно более неожиданно. Если источник выдает последовательность зависимых между собой элементарных сообщений, то наличие предшествующих сообщений может изменить вероятность последующего, а, следовательно, и количество информации в нем. Оно должно определяться по условной вероятности P(u_k|u_k-1,u_k-2,…) выдачи сообщения u_k при известных предшествующих сообщениях u_k-1,u_k-2,…, тогда количество информации

i(uk|uk-1,uk-2,…)=-log P(uk|uk-1,uk-2,…)

(1.3)

Определения (1.2) и (1.3) количества информации являются случайной величиной, поскольку сами сообщения являются случайными. Его распределение вероятностей определяется распределением вероятностей сообщений в данном ансамбле для цифровой характеристики всего ансамбля или источника сообщения используется математическое ожидание количества информации в отдельных сообщениях называемых энтропией или Мерой Шеннона

(1.4)

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