Оптимизация программы бинарного поиска

При рассмотрении вопроса об оптимальности алгоритма бинарного поиска учитывалось только число требуемых сравнений. Не учитывались другие операции, а также «накладные расходы» программы (на организацию цикла, работу с индексами и т. п.). Оказывается, программу можно значительно улучшить, модифицировав ее и уменьшив «накладные расходы».

Для определенности положим, что глобальные константы и типы задаются, например, описанием

const  nMax = 2048; nMax1= 2049;

type  index=1..nMax; index0=0..nMax; index1=1..nMax1;

DimVec=index;

ElemT= Integer;

Vec = array  [index]  of  ElemT;

Начнем с полученного ранее алгоритма, оформленного в виде процедуры BinSearch1:

procedure  BinSearch1(n: DimVec; var a: Vec; x: ElemT; var q:Boolean; var L: index1);

{  арг : n, a, x;  рез : q, L}

{ Pred: (ALL i: 1<=i<n: a[i]<a[i+1])

{ Post: (1<=L<=n+1) & (a[L1]<x<=a[L]) & }

{ (q = (1<=L<=n)&(a[L]=x)) }

 var  R: index1; m: index;

begin

L := 1; R := n + 1; { a[L1]<x<=a[R] }

 while  L <> R  do

 begin  { (1<=L<R<=n+1) & (a[L1]<x<=a[R]) }

m := (L + R) div 2;

if a[m] < x then  L := m + 1  else  R := m

{ (1<=L<=R<=n+1) & (a[L1]<x<=a[R]) }

 end  { while };

{ (1<=L<=n+1) & (a[L1]<x<=a[L]) }

 if  L <> n + 1  then  q := (x = a[L])  else  q :=  False

end  { BinSearch1 }

Рассмотрим далее другой вариант бинарного поиска в виде процедуры:

procedure  BinSearch2 (n: DimVec;  var a: Vec; x: ElemT; var q: Boolean; var L: index0);

{  арг : n, a, x;  рез : q, L }

{ Pred: (ALL i: 1<=i<n : a[i]<a[i+1]) }

{ Post: (0<=L<=n) & (a[L]<x<=a[L+1]) & }

{ (q = (0<=L<=n1)&(a[L+1]=x) ) }

 var R: index1; m: index;

begin

L := 0; R := n + 1; { a[L]<x<=a[R] }

 while L + 1 <> R do

 begin  { (0<=L<R1<=n) & (a[L]<x<=a[R]) }

m := (L + R) div 2;

  if a[m] < x  then L := m  else  R := m

 end { while };

{ (0<=L<=n) & (a[L]<x<=a[L+1]) }

if  L <> n  then  q := (x = a[L + 1])  else  q :=  False

end { BinSearch2 }

Отличие этого варианта лишь в том, что интервал локализации нумеруется по своей левой границе: &.

Следующее преобразование проведем в предположении, что длина массива, в котором осуществляется поиск, заранее известна. Пусть, например, . Из анализа алгоритма бинарного поиска (см. 5.3) известно, что число итераций в циклеwhile-do равно либо , либо 1, где =. При(для некоторого) дерево бинарного поиска является ровным и число итераций в циклеwhile-do всегда равно . Этот факт можно использовать для оптимизации цикла. Перед циклом преобразуем исходный интервал к интервалу длины, где(приимеем):

i := 512; if a[i] < x  then  L := n – i + 1  else  L := 0;

здесь интервал локализации задается левой границей и длиной: (a[L] < x <= a[L + i]) & (i = 512 = 2^j) & (j = 9).

В самом цикле также вместо пары переменных L и R будем использовать пару переменных L и . В результате получим алгоритм

procedure BinSearch3 ({n: DimVec;} var a: Vec; x: ElemT;

 var q: Boolean; var L: index0);

{  арг : a, x;  рез : q, L }

{ Pred:  (n=1000) & (ALL i : 1<=i<n : a[i]<a[i+1]) }

{ Post: (0<=L<=n) & (a[L]<x<=a[L+1]) & }

{ (q = (0<=L<=n1)&(a[L+1]=x) ) }

const  n = 1000; { ! }

var  i: 1..512; m: index;

begin

i := 512;  if a[i] < x  then  L := n – i + 1  else  L := 0;

{ (a[L]<x<=a[L+i]) & (i=512=2^j) & (j=9) & (L0=L) }

 while  i <> 1  do

 begin

i := i div 2; m := L + i;280

  if a[m] < x then  L := m  else  { };

{(i=2^j)&(0<=j<9)&(a[L]<x<=a[L+i])&(L0<=L<=L0+511) }

{ & (L+i<=n+1) }

end { while }; { Bound: j = log2(i) }

{ (0<=L<=n) & (a[L]<x<=a[L+1]) }

 if L <> n  then q := (x = a[L + 1]) else q :=   False

end{ BinSearch3 }

Важно, что теперь цикл выполняется при любом ровно 9 раз (), а сравнениепроизводится при, гдепробегает значения 256, 128, 64, 32, 16, 8, 4, 2, 1. Этот факт явным образом учитывается в окончательной версии алгоритма:

procedure BinSearch4 ({n: DimVec;} var a: Vec; x: ElemT; var q: Boolean;  var L: index0 );

{  арг : a, x;   рез : q, L }

{ Pred: (n=1000) & (ALL i: 1<=i<n: a[i]<a[i+1]) }

{ Post: (0<=L<=n) & (a[L]<x<=a[L+1]) & }

{ (q = (0<=L<=n1)&(a[L+1]=x) ) }

const n = 1000; { ! }

begin L := 0;

 if  a[ 512 ]     < x then  L := n – 512 + 1; {a[L]<x<=a[L+512] }

 if  a[L + 256] < x  then  L := L + 256; {a[L]<x<=a[L+256] }

 if  a[L + 128] < x  then  L := L +128;

{ … }

 if  a[L +   64] < x  then  L := L +  64;

 if  a[L +   32] < x  then  L := L +  32;

 if  a[L +   16] < x  then  L := L +  16;

 if  a[L +     8] < x  then  L := L +    8;

 if  a[L +     4] < x  then  L := L +    4;

 if  a[L +     2] < x  then  L := L +    2;

{ … }

 if  a[L +     1] < x  then  L := L +    1;

{ (a[L]<x<=a[L+ 1]) & (0<=L<=n) }

 if  L <> n then q := (x = a[L + 1])  else q :=   False

end { BinSearch4 }

Здесь цикл явным образом развернут в последовательность операторов и исключена операция  div 2. Оптимизированный вариант работает быстрее в 2…5 раз.

Билет№41 Передача параметров в подпрограммах: назначение параметров в процессе обмена данных и способы передачи, реализация в Паскале. №41

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

По способу передачи параметры в Турбо Паскале делятся на 3 типа — параметры-значения, параметры-переменные, параметры-константы.

1. Заголовок процедуры с параметрами-значениями, имеет вид:

procedure Proc1( par1 : type1; par2; par3 : type2; par4 : type3);

При вызове формальным параметрам-значениям выделяется новое место в памяти и присваиваются значения фактических параметров (ими могут быть переменные, выражения, константы). Совместимость типов определяется возможностями присваивания. После выполнения память освобождается. Изменение формальных параметров не сказывается на значениях фактических.

2. Заголовок процедуры с параметрами-переменными, иметь вид:

procedure Proc2(var par1, par2 : type1; var par3, par4 : type2);

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

3. Заголовок процедуры с параметрами-константами, например, имеет вид:

procedure Proc3(const par1 : type1; const par2, par3, par4 : type2);

Использование формальных параметров-констант внутри процедуры (функции) аналогично применению локальных констант, но они принимают значения выражений фактических параметров. Новая память для них не выделяется. Их значения изменять нельзя. Использовать параметры-константы рекомендуется при передаче данных большого объема в случае, когда надо сохранить их значения.

По отношению параметров к данным в месте вызова и использованию их в теле процедуры или функции различают:

• входные параметры, обеспечивающие передачу значений при вызове в тело процедуры или функции;

• выходные, предназначенные для передачи результатов выполненных действий из тела; их значения могут быть изменены;

• транзитные, позволяющие использовать в теле передаваемые при вызове значения; возможно их изменение в теле с передачей из тела.

Передача параметров по :1)значению 2)ссылки : (перемен=имя+знач ; Перемен=имя+ссылка+знач)

(имя)  !ссылка-адресс! (знач)

Билет№42 Ф-ции ипроцедуры в языке Паскаль. Параметры и глобальные переменные №42

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

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

Описание процедуры имеет следующую структуру:

procedure <имя> (список формальных параметров);

label{ Описание локальных меток,}

const { констант, }

type { типов }

var { и переменных }

procedure { Описание внутренних процедур}

function { и функций}

begin

{ операторы }

end;

Описание функции имеет следующую структуру:

function <имя> (список формальных параметров) : тип результата;

label { Описание локальных меток, }

const { констант,}

type { типов }

var{ и переменных }

procedure{ Описание внутренних процедур}

function { и функций }

begin { операторы, среди которых есть хотя бы один оператор присваивания, в левой части которого стоит переменная, чье имя совпадает с именем функции, а в правой части – результат выполнения функции}

end;

Типом результата в ф-циях может быть любой из стандартных типов языка Паскаль за исключением файловых типов. Использование определяемых типов не допустимо.

Имена, описанные в основной программе, являются глобальными по отношению к процедурам и ф-циям, которые описаны после этих имен. Аналогично, имена, описанные в процедурах и ф-циях, являются глобальными по отношению к внутренним процедурам и ф-циям, которые в них описаны. Остальные имена называются локальными. Их область действия локализована (ограничена процедурой или ф-цией)

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

Параметры, находящиеся после имени в заголовке, называются формальными (необходимо указать их имена и типы, параметры разного типа отделяются точкой с запятой, а одного типа можно перечислять через запятую), а параметры, используемые при вызове, — фактическими (разделяются запятыми). Формальные параметры  локальным переменным. Память для локальных данных выделяется при вызове, а ее освобождение происходит при выходе из процедуры (ф-

-ции). Если имя локальной переменной совпадает с глобальным идентификатором, то все действия выполняются с локальным именем, т. е. происходит перекрытие области действия глобального имени.

По способу передачи параметры в Паскале делятся на 3 типа — параметры-значения, параметры-переменные, параметры-константы.

4. Заголовок процедуры с параметрами-значениями, имеет вид:procedure Proc1(par1 : type1; par2; par3 : type2; par4 : type3);

При вызове формальным параметрам-значениям выделяется новое место в памяти и присваиваются значения фактических параметров (ими могут быть переменные, выражения, константы). Совместимость типов определяется возможностями присваивания. После выполнения память освобождается. Изменение формальных параметров не сказывается на значениях фактических.

5. Заголовок процедуры с параметрами-переменными иметь вид:

procedure Proc2(var par1, par2 : type1; var par3, par4 : type2);

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

6. Заголовок процедуры с параметрами-константами имеет вид:

procedure Proc3(const par1 : type1; const par2, par3, par4 : type2);

Использование формальных параметров-констант внутри процедуры (функции) аналогично применению локальных констант, но они принимают значения выражений фактических параметров. Новая память для них не выделяется. Их значения изменять нельзя. Использовать параметры-константы рекомендуется при передаче данных большого объема в случае, когда надо сохранить их значения.

По отношению параметров к данным в месте вызова и использованию их в теле процедуры или функции различают:

• входные параметры, обеспечивающие передачу значений при вызове в тело процедуры или функции;

• выходные, предназначенные для передачи результатов выполненных действий из тела; их значения могут быть изменены;

• транзитные, позволяющие использовать в теле передаваемые при вызове значения; возможно их изменение в теле с передачей из тела.

Билет№43 Одномерные массивы:описание типов и переменных, индексация,использование процедур и ф-ций №43

Массив – это упорядоченная структура данных одного типа, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс.

Массивы можно описать следующим образом:

type имя_типа = array [ диапазоны индексов ] of тип эл-

-та массива;

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

Пример (способы описания одного и того же типа массива):

type {1)} Array1 = array ['a'..'z'] of Integer; Array2 = array [1..15] of Array1; Array3 = array [-5..5] of Array2; {2)} Array3 = array [-5..5] of array [1..15] of array ['a'..'z'] of Integer; {3)} Array3 = array [-5..5,1..15,'a'..'z'] of Integer;

var A : Array3; { Объявление и обращение к эл-там массива: }

begin

Read(A[-4,3,'w']) ;

Read(A[1][10]['g']); A[3][7,'h']:=100;

end.

Объем данных в программе, в стандартном режиме работы Паскаля ограничен 64 Кбайт. Над массивами допускается применение только операции присваивания массивов (подмассивов) одинаковых типов. Остальные операции должны выполняться поэлементно.

Массивы могут передаваться при вызове процедур (ф-

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

type MyElems = Real;

MyArray = array [-5..5] of MyElems;

procedure Inp( var parameter : MyArray);