Файл: Сравнительный анализ описания данных для различных языков программирования (Линейный алгоритм поиска).pdf

Введение

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

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

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

В работе мы выделяем две части: теоретическую и Теоретические задачи работы:

• обзор известных алгоритмов поиска;
• обзор реализации алгоритмов поиска в таких языках программирования, как C++, C#, Delphi.

Практические задачи:

• реализация алгоритмов поиска на С++, C#, Delphi;
• их сравнительный анализ.

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

Во второй главе исследуются нами языки программирования.

В третьей главе описано нами исследование.

В программной части для представленной курсовой работы используется язык Delphi в среде программирования Borland Delphi 7, а также языки С++ и С# в программирования Microsoft Visual Studio 2010.

Глава 1. Линейный алгоритм поиска

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

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

Основная задача поиска – в заданной совокупности данных который обладает заданным свойством. Большинство задач поиска к поиску элемента с заданным значением в массиве.

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

Рассмотрим используемые нами алгоритмы подробно.

Данный алгоритм имеет простейшую реализацию. Он не накладывает ограничений на массив. Принцип работы алгоритма заключается в том, что элемент массива последовательно просматривается и сравнивается с ключом поиска. Если совпадение найдено считается завершенным. Как правило, поиск происходит направо, то есть от значений аргумента к большим. Исследования начинаются с первого массива. Если искомое значение не значению данного элемента массива, то переход к следующему элементу Таким образом в результате проверки область поиска уменьшается на один

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

В среднем количество сравнений вычислить по формуле (N + 1) Div 2, где N – количество элементов в массиве. Если искомого элемента в нет, то число сравнений N. Эффективность алгоритма поиска O(N).

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

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

For i := 1 To N Do

If A[i] = x Then k := i;

Метод линейного поиска лучше использовать в небольших или в массивах. В иных случаях он

1.1. Бинарный алгоритм поиска

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

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

Каждое сравнение уменьшает диапазон приблизительно в два раза. количество сравнений можно вычислить по N * logN, где N – количество элементов в

Реализация бинарного алгоритма поиска осуществляется следующим :

Procedure Search;

Var i, j, m: Integer;

f: Boolean;

Begin

i := 1;

j := N;

f := False;

While (i <= j) And Not f Do Begin

m := (i + j) Div 2;

If A[m] = x Then f := True

Else

If A[m] < x Then i := m + 1

Else j := m - 1;

End;

End;

На первом шаге мы весь массив. F показывает найден элемент или нет. m := (i + j) Div 2 можно заменить на m := i + (j - i) Div 2, так как i + (j - i) Div 2 = (2 * i + (j - i)) Div 2=(i + j) Div 2.

Так как бинарный алгоритм может быть применен только к массиву, то предварительно массив отсортировать.

Сравнивать данные алгоритмы мы по отдельности. Как было сказано ранее, отсортировать массив, а для надо добавить сортировку в код.

Рассмотрим алгоритм сортировки.

1.2. Сортировка

Сортировка – это упорядочивание чисел в массиве, в первоначально элементы расположены в порядке. Сортировка может быть :

• по возрастанию – каждый следующий элемент больше предыдущего;
• по убыванию – каждый следующий больше предыдущего;
• по невозрастанию – каждый следующий не больше предыдущего, то есть или равен ему;
• по неубыванию – каждый следующий не меньше предыдущего, то есть или равен ему.

Сортировка важна и часто применяется в базах так как поиск информации в массиве происходит гораздо быстрее.

Алгоритмы сортировки отличаются друг от степенью эффективности, под которой количество сравнений и количество происходящих в результате сортировки. Так как в задачах поиска операцию сортировки выполнять для достаточно больших объёмов данных, то значение имеет время сортировки. эффективность алгоритма сортировки имеет очень значение. Разработано множество сортировки, отличающихся эффективностью в тех или иных данных.

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

Быстрая сортировка – очень эффективный алгоритм, она известна как в самая быстрая из универсальных сортировки. Метод был разработан в 1962 году информатиком Чарльзом Хоаром. Из–за эффективности автор назвал алгоритм сортировкой».

Идея сортировки в том, что в массиве произвольно выбирается некоторый который называется опорным. Цель в том. Чтобы записать элемент на нужное место в Место должно быть таким, слева от опорного элемента были меньшие или равные опорному. А справа элементы опорного. В результате, когда элемент встает на свое массив делится на две части. Барьером между этими является опорный элемент. Затем каждая из этих двух подвергается независимой сортировке по той же , и так до тех пор, пока не останутся части массива, из одного элемента. Таким сортировка продолжается пока весь не будет отсортирован.

Реализация алгоритма быстрой сортировки следующим образом:

Procedure QuickSort(m, t: Integer);

Var i, j, w, x: Integer;

Begin

i := m;

j := t;

x := A[(m + t) div 2];

While i <= j Do

If A[i] < x Then Inc(i)

Else If A[j] > x Then Dec(j)

Else Begin

w := A[i];

A[i] := A[j];

A[j] := w;

Inc(i);

Dec(j);

End;

If m < j Then QuickSort(m, j);

If i < t Then QuickSort(i, t);

End;

Таким образом, быстрая сортировка – это рекурсивный алгоритм, то есть вызывающий сам себя. Время сортировки пропорционально N * logN, где N – количество элементов в .

Однако, у алгоритма быстрой есть и недостатки. Массив чисел сортируется очень быстро, только что отсортированный массив повторно процедура обрабатывать крайне медленно, вплоть до исчерпания ёмкости стека, так как эффективность алгоритма крайне зависит от выбора опорного элемента.

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

Рассмотрим тип данных запись подробно.

1.3. Записи

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

При описании записи для элемента указывается его длина в и, что необязательно, некоторое

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

Записи обычно используются в Windows API вызовах, где они как "структуры", которые являются в программирования C++ терминологией для очень похожих вещей.

С помощью зарезервированного слова record(запись) в одном типе объединять данные разных типов. синтаксис объявления этого типа выглядит следующим образом:

Record

fieldname1: fieldtype1;

fieldname2, fieldname3: fieldtype2;

case optional tagfield: required type of

1: variantnamel: varianttype3;

2, 3: variantname2: varianttype4;

End;

Данное объявление состоит из и вариантной частей. Однако не обязательно вставлять в одно записи обе эти части. удобнее работать с каждой из этих отдельно.

Фиксированные записи.

В фиксированной части записи одно или несколько независимых Каждому полю обязательно присваивается имя и тип:

Record

fieldnamel: fieldtypel;

fieldname2, fieldname3: fieldtype2;

End;

Имея доступ к информации в можно обрабатывать всю запись , то есть все поля или только отдельное Для обращения к отдельному полю нужно набрать имя записи, точку и идентификатор поля,

MyRec.Fieldnamel

Для доступа ко всей нужно просто указать ее имя.

Вариантные записи.

Вариантная часть типа record дает по–разному трактовать область памяти, занимаемую вариантами поля:

Record

case optional tagfield: required type of

1: variantnamel: varianttype3;

2, 3: variantname2: varianttype4;

End;

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

Каждый вариант обозначается как минимум одной константой. Все должны быть порядковыми и по типу с меткой

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

Необязательное поле можно не однако порядковый тип необходим. При необязательного поля программе придется подходящий вариант каким-то иным

Данные некоторых типов бессмысленно различным образом, и в Pascal на некоторые критические типы соответствующее ограничение. Как следствие, в часть записи нельзя включать строки и переменные типа Variant, а также структурные содержащие эти типы.

Время работы алгоритмов мы программно. В языках С++ и Delphi с помощью функции GetTickCount. В языке С# с помощью DateTime. Время мы засекали в .

Рассмотрим данные функции более

GetTickCount

Описание: function GetTickCount: Longint;

Считывает время, прошедшее с момента запуска