Сравнительный анализ описания данных для различных языков программирования

Содержание:

Введение

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

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

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

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

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

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

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

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

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

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

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

Глава 1

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

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

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

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

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

1.1 Линейный алгоритм поиска

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

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

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

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

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

For i := 1 To N Do

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

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

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

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

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

Каждое сравнение уменьшает диапазон приблизительно в два раза. количество сравнений можно вычислить по 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.

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

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

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

Сортировка

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

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

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

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

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

Быстрая сортировка – очень эффективный алгоритм, она известна как в самая быстрая из универсальных сортировки. Метод был разработан в 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 – количество элементов в .

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

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

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

Записи

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

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

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

Записи обычно используются в 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;

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

Разрешение функции GetTickCount ограничено системного таймера, которое обычно находится в от десяти миллисекунд до шестнадцати миллисекунд. Разрешение функции GetTickCount не о влиянию корректировок сделанных функцией GetSystemTimeAdjustment.

Истекшее время хранится как DWORD. Таким образом, время будет нулю, если система будет работать непрерывно в течении 49,7 дней. Чтобы этой проблемы, можно использовать функцию GetTickCount64. В противном случае, нужно проверить условия переполнения при сравнении.

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

time := getTickCount;

time := getTickCount –

Так как алгоритмы поиска гораздо быстрее, чем 49,7 дней нам функция GetTickCount.

DateTime

Представляет текущее время, обычно как дата и время

Тип значения DateTime представляет дату и в диапазоне от 00:00:00 1 0001 года (н. э.) до 9 31 декабря 9999 э.).

Значения времени измеряются в единицах, называемых тактами, и дата представляется числом тактов с 1 января 0001 года н. э. (н. э.) в GregorianCalendar (за исключением тактов, корректировочными секундами). Например, значение равное 31241376000000000L, представляет пятницу 1 0100 года 00:00:00. Значение DateTime выражается в контексте явно или заданного по умолчанию

Для внутренних целей, все DateTime представляются как количество тактов(количество 100-наносекундных интервалов), закончившихся в 1 января 0001 г. значение DateTime не зависит от появления этого значения, при в элементе пользовательского интерфейса или при в файл. Внешний вид значения DateTime – это результат операции форматирования. Форматирование – это процесс преобразования значения в его представление.

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

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

long time = DateTime.Now.Ticks;

DateTime dt = new

dt.Millisecond.ToString();

Время мы перевели в миллисекунды, так как GetTickCount вычисляет время в Потому что нам нужно время работы программ между

Глава 2

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

В данной работе мы три языка программирования: Borland 7, Visual C++, Visual C#. Рассмотрим их более

Delphi

Delphi – императивный, структурированный, ориентированный язык программирования, диалект Object Pascal. Начиная со среды Delphi 7.0, в официальных Borland стала использовать название Delphi для обозначения языка Object Pascal. Начиная с 2007 года уже язык Delphi (производный от Object Pascal) начал жить своей жизнью и претерпевал различные связанные с современными тенденциями с развитием платформы .NET) развития языков программирования: class helpers, перегрузки операторов и

Object Pascal – результат языка Turbo Pascal, который, в свою развился из языка Паскаль. был полностью процедурным языком. Turbo Pascal, начиная с 5.5, добавил в Паскаль свойства, а в Object – динамическую идентификацию типа с возможностью доступа к классов (то есть к классов и их членов) в коде, также называемом интроспекцией – технология получила обозначение RTTI. Так как все наследуют функции базового класса то любой указатель на можно преобразовать к нему, чего воспользоваться методом ClassType и TypeInfo, которые и обеспечат

Также отличительным свойством Object от С++ является то, что по умолчанию располагаются в памяти. Однако можно переопределить методы NewInstance и FreeInstance класса TObject. Таким образом, любой класс может осуществить «где хочу – там и буду Соответственно организуется и «многокучность».

Object Pascal (Delphi) является функционального расширения Turbo Pascal.

Delphi оказал огромное влияние на концепции языка C# для .NET. Многие его элементы и решения вошли в состав С#. из причин называют переход Хейлсберга, одного из ведущих разработчиков Delphi, из компании Borland Ltd. в Corporation.

В Delphi реализованы классы для самых распространенных структур данных – очередей и стеков, а массивов строк, которые широко в компонентах. Далее рассмотрим такую структуру как список.

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

2.1 Класс TList

Для реализации списков указателей на структуры данных в Delphi предназначен класс (англ. List – список), имеющий внутреннее строение, представленному:

ListClass: TList

Procedure Add(O: TObject);

Function Get: TObject;

За исключением того, что хранимые в списке, задаются указателями (указателями типа pointer), а не ссылками на экземпляры классов.

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

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

Function Add(Item: Pointer): Integer;

К элементам, которые хранятся в реализован индексный механизм доступа, то есть для на элемент используется его номер, возвращаемый методом Add. элементам выдаются по порядку от нуля, а при удалении элемента из списка все элементы, следующие за ним, Если существует необходимость вставить элемент в списка, то в программе использоваться метод insert:

Procedure Insert(Index: Integer; Item: Pointer);

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

Property Count: Integer;

Для удаления элементов из предусмотрены методы Delete и Параметр index определяет номер элемента, а параметр item – ссылку на удаляемый элемент.

Procedure Delete(Index: Integer);

Function Remove(Item: Pointer): Integer;

Метод Remove возвращает номер из списка элемента, который он имел до

Отметим, что при удалении из списка память, в хранится информационная структура, не автоматически, а ссылка на нее теряется. образом, вызов метода Delete местом потенциальной утечки памяти, если хранимые в списке, не дублируются в других программы. Аналогичным образом работает метод Clear, удаляющий все списка без разрушения информации, в нем хранится:

Procedure Clear; Virtual;

Для доступа к элементам предусмотрено несколько методов и свойств. Для получения указателей на хранимые в первом и последнем элементах списка, используются методы First и Last:

Function First: Pointer;

Function Last: Pointer;

Получить ссылку на любой элемент, хранимый в списке, можно с помощью property – свойства items, доступ к которому аналогичен доступу к массиву:

property Items[Index: Integer]: Pointer; default;

Свойство items может использоваться для получения данных, хранимых в некотором элементе списка, а также для установки таких данных.

Мы взяли версию Borland Delphi 7, потому что она интересна нам своим синтаксисом. Так как последующие версии своим синтаксисом больше напоминают язык С.

2.2 C++

С++ – компилируемый строго типизированный язык программирования общего назначения. Поддерживает разные парадигмы программирования: процедурную, обобщённую, функциональную; наибольшее внимание уделено поддержке объектно-ориентированного программирования.

В 1990–х годах язык стал одним из наиболее широко применяемых языков программирования общего назначения.

При создании С++ стремились сохранить совместимость с языком C. Большинство программ на С будут исправно работать и с компилятором С++. С++ имеет синтаксис, основанный на синтаксисе С.

Нововведениями С++ в сравнении с С являются:

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

Язык возник в начале 1980–х годов, когда сотрудник фирмы «Bell Laboratories» Бьёрн Страуструп придумал ряд усовершенствований к языку С под собственные нужды. До начала официальной стандартизации язык развивался в основном силами Страуструпа в ответ на запросы программистского сообщества. В 1998 году был ратифицирован международный стандарт языка С++: ISO/IEC 14882:1998 «Standard for the C++ Programming Language»; после принятия технических исправлений к стандарту в 2003 году нынешняя версия этого стандарта – ISO/IEC 14882:2003.

Название «С++» происходит от С, в котором унарный оператор ++ обозначает приращение.

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

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

Шаблон типа для класса задает способ построения отдельных классов, подобно тому, как описание класса задает способ построения его отдельных объектов. Можно определить стек, содержащий элементы произвольного типа:

template<class T>

class stack

{

T* v;

T* p;

int sz;

public:

stack(int s) { v = p = new T[sz=s]; }

~stack() { delete[] v; }

void push(T a) { *p++ = a; }

T pop() { return *--p; }

int size() const { return p-v; }

};

Для простоты не учитывается контроль динамических ошибок. Префикс template<class T> указывает, что описывается шаблон типа с параметром T, обозначающим тип, и что это обозначение будет использоваться в последующем описании. После того, как идентификатор T указан в префиксе, его можно использовать как любое другое имя типа. Область видимости T продолжается до конца описания, начавшегося префиксом template<class T>.

Отметим, что в префиксе T объявляется типом, и оно не обязано быть именем класса. Так, ниже в описании объекта sc тип T оказывается просто char.

Имя шаблонного класса, за которым следует тип, заключенный в угловые скобки <>, является именем класса (определяемым шаблоном типа), и его можно использовать как все имена класса. Например, ниже определяется объект sc класса stack<char>:

stack<char> sc(100); // стек символов.

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

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

C#

С# – объектно–ориентированный язык программирования. Разработан в 1998–2001 годах группой инженеров под руководством Андерса Хейлсберга в компании Microsoft как основной язык разработки приложений для платформы Microsoft .NET и впоследствии был стандартизирован как ECMA-334 и ISO/IEC 23270. Компилятор с C# входит в стандартную установку самой платформы .NET.

C# относится к семье языков с C–подобным синтаксисом, из них его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку операторов (в том числе операторов явного и неявного приведения типа), делегаты, атрибуты, события, свойства, обобщённые типы и методы, итераторы, анонимные функции с поддержкой замыканий, LINQ, исключения. Кроме того, немаловажным фактором является сравнительно хорошее знание языка программирования С#. Так же C# содержит ряд важных моментов. Например, C# является полностью объектно-ориентированным языком с продуманной структурой организации межклассового взаимодействия, непротиворечивую систему множественного наследования по средствам интерфейсов, а также, имеет единую систему типов. В состав элементов языка C# включены такие понятия, как делегаты (представители), индексаторы. Добавлен синтаксис, поддерживающий атрибуты. Упрощено создание компонентов за счёт исключения проблем, связанных с COM. Язык C# предлагает средства динамического обнаружения ошибок, обеспечения безопасности и управляемого выполнения программ. В дополнении можно отметить простоту работы с различными базами данных, в том числе Microsoft SQL.

Глава 3

Так как тема данной курсовой работы – «Сравнительный анализ алгоритмов поиска, реализованных в разных языках программирования», нам нужно сравнить реализации данных алгоритмов между собой. В качестве параметра, по которому мы будем проводить сравнение, мы выбрали производительность алгоритмов. Производительность можно измерить во времени работы алгоритма. Таким образом, мы постараемся выяснить, какая реализация алгоритмов поиска работает наиболее быстро. Ведь чем быстрее алгоритм работает, тем удобнее он в использовании.

Мы реализовали линейный и бинарный алгоритмы поиска в языках программирования Delphi, C++ и C#. Так как сравнивать данные алгоритмы мы будем по отдельности, то постараемся выяснить, реализация на каком языке работает эффективней.

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

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

Чтобы получить окончательный результат, мы берем среднее значение всех проведенных нами тестов.

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

	Delphi	C++	C#
Тест 1(мс)	31	47	30
Тест 2(мс)	16	78	35
Тест 3(мс)	31	93	27
Тест 4(мс)	15	63	30
Тест 5(мс)	32	62	32

Таблица 1

Ниже приведена таблица полученных результатов для бинарного алгоритма поиска:

	Delphi	C++	C#
Тест 1(мс)	1120	359	390
Тест 2(мс)	1185	374	482
Тест 3(мс)	1263	344	290
Тест 4(мс)	1217	328	372
Тест 5(мс)	1154	358	370

Таблица 2

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

Ниже приведена таблица результатов для линейного поиска:

Delphi	C++	C#
25 мс	68,6 мс	30,8 мс

Таблица 3

Ниже приведена таблица результатов для бинарного поиска:

Delphi	C++	C#
1187,8 мс	352,6 мс	380,8 мс

Таблица 4

По результатам, полученным в Таблице 3 и Таблице 4, мы составили диаграмму, которая представлена ниже:

Диаграмма 1

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

Заключение

В данной работе представлены наиболее распространенные алгоритмы поиска. А также проведены сравнения на конкретных реализациях данных алгоритмов и тестах.

В результате проведенной работы мы исследовали производительность линейного и бинарного алгоритмов поиска. Как видно из Диаграммы 1 большей производительностью обладает линейный алгоритм поиска. Наиболее быстро работает его реализация на языке Delphi. В бинарном поиске наиболее быстро работает реализация на языке С++.

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

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

Список литературы

1. Окулов С. М. Основы программирования М.: Юнимедиастайл, 2002 – 424 с.: ил.
2. Бьерн Страуструп Язык программирования С++ М.: Бином–Пресс, 2011 – 1136 с.: ил.
3. Герберт Шилдт С#: Учебный курс М.: Издательская группа BHV, 2003 – 512 с.: ил.
4. msdn.microsoft.com

Приложение

Линейный поиск

Delphi

program linear_search;

{$APPTYPE CONSOLE}

uses

SysUtils,

Windows;

type rec = record

field1 : integer;

field2 : double;

field3 : char;

end;

const n = 800000;

var FindIndex, i: integer;

x : rec;

time: cardinal;

A:array[1..n]of rec;

function Equal(a, b : rec) : boolean;

begin

if (a.field1 = b.field1) and (a.field2 - b.field2 < 0.001) and (a.field3 = b.field3) then Equal := true

else Equal := false;

end;

begin

randomize;

for i:=1 to n do

begin

A[i].field1 := random(1000);

A[i].field2 := random(1000) / 100;

A[i].field3 := char(random(255));

end;

writeln(A[n - 1].field1, ' ', A[n - 1].field2, ' ', A[n - 1].field3);

x := A[n - 1];

FindIndex := 0;

time := getTickCount;

for i:=1 to n do

if Equal(A[i], x) then FindIndex:=i;

writeln('Index of element = ', FindIndex);

writeln('Time = ', getTickCount - time);

readln;

end.

С++

#include <iostream>

#include <conio.h>

#include <windows.h>

using namespace std;

struct rec

{

int field1;

double field2;

char field3;

};

const int n = 800000;

bool Equal(rec a, rec b)

{

if ((a.field1 == b.field1) && (a.field2 - b.field2 < 0.001) && (a.field3 == b.field3)) return true;

else return false;

}

int main()

{

DWORD time;

int i;

rec x;

rec* A = new rec[n];

for (int i = 0; i < n; i++)

{

A[i].field1 = rand()%1000;

A[i].field2 = (rand()+rand())/100.f;

A[i].field3 = rand()%256;

}

cout << A[n-1].field1 << " " << A[n-1].field2 << " " << (int)A[n-1].field3 << endl;

x = A[n-1];

int FindIndex = 0;

time = GetTickCount();

for (i = 0; i < n && !Equal(A[i], x); i++);

if (i == n)

cout << "Not found!!!";

else

cout << "Index of element = " << i;

time = GetTickCount() - time;

cout << endl << "Time = " << time << "ms";

_getch();

return 0;

}

C#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace linear_search

{

struct rec

{

public int field1;

public double field2;

public char field3;

}

class Program

{

static int n = 800000;

static bool Equal(rec a, rec b)

{

if ((a.field1 == b.field1) && (a.field2 - b.field2 < 0.001) && (a.field3 == b.field3)) return true;

else return false;

}

static void Main(string[] args)

{

Random r = new Random((int)DateTime.Now.Ticks);

rec x = new rec();

rec[] A = new rec[n];

for (int i = 0; i < n; i++)

{

A[i] = new rec();

A[i].field1 = r.Next(1000);

A[i].field2 = r.Next(1000) / 100;

A[i].field3 = (char)r.Next(255);

}

Console.WriteLine(A[n - 1].field1 + " " + A[n - 1].field2 + " " + A[n - 1].field3);

x = A[n - 1];

int FindIndex = 0;

long time = DateTime.Now.Ticks;

for (int i = 1; i < n; i++)

if (Equal(A[i], x)) FindIndex = i;

Console.WriteLine("Index of element = " + FindIndex);

time = DateTime.Now.Ticks - time;

DateTime dt = new DateTime(time);

Console.WriteLine("Time = " + dt.Millisecond.ToString() + "ms");

Console.ReadKey();

}

}

}

Бинарный поиск

Delphi

program binary_search;

{$APPTYPE CONSOLE}

uses

SysUtils,

Windows;

type rec = record

field1 : integer;

field2 : double;

field3 : char;

end;

const n = 800000;

var FindIndex, i: integer;

x : rec;

time: cardinal;

A:array[1..n] of rec;

function Equal(a, b : rec) : boolean;

begin

if (a.field1 = b.field1) and (a.field2 - b.field2 < 0.001) and (a.field3 = b.field3) then Equal := true

else Equal := false;

end;

function less(a, b : rec) : boolean;

begin

less := false;

if (a.field1 < b.field1) then

less := true

else if (a.field1 > b.field1) then

less := false

else begin

if (a.field2 < b.field2 - 0.00001) then

less := true

else if (a.field2 > b.field2 + 0.00001) then

less := false

else if (a.field3 < b.field3) then

less := true;

end;

end;

procedure QuickSort(L, R: integer);

var i, j, w1: Integer;

w2: double;

w3: char;

x: rec;

begin

i := L;

j := R;

x := A[(L + R) div 2];

while i <= j do

begin

while less(A[i], x) do

inc(i);

while (not less(A[j], x)) and (not Equal(A[j], x)) do

dec(j);

if (i <= j) then

begin

w1 := A[i].field1;

w2 := A[i].field2;

w3 := A[i].field3;

A[i].field1 := A[j].field1;

A[i].field2 := A[j].field2;

A[i].field3 := A[j].field3;

A[j].field1 := w1;

A[j].field2 := w2;

A[j].field3 := w3;

inc(i);

dec(j);

end;

end;

if (L < j) then

QuickSort(L, j);

if (i < R) then

QuickSort(i, R);

end;

function Search(x: rec) : integer;

var i,j,m:integer;

f:boolean;

begin

i := 0;

j := n - 1;

FindIndex:=0;

//f:=false;

while (i <= j) do

begin

m:=(i+j) div 2;

if Equal(x, A[m]) then

begin

FindIndex := m;

exit;

end else begin

if not(Less(x, A[m])) then

i:=m+1

else

j:=m-1;

end;

end;

if (Equal(x, A[m])) then

result := m

else

result := n;

end;

begin

randomize;

for i:=1 to n do

begin

A[i].field1 := random(1000);

A[i].field2 := random(1000) / 100;

A[i].field3 := char(random(255));

end;

time := getTickCount;

QuickSort(0, n - 1);

writeln(A[n - 1].field1, ' ', A[n - 1].field2, ' ', A[n - 1].field3);

x := A[n - 1];

FindIndex := Search(x);

writeln('Index of element = ', FindIndex);

writeln('Time = ', getTickCount - time);

readln;

end.

C++

#include <iostream>

#include <conio.h>

#include <windows.h>

using namespace std;

struct rec

{

int field1;

double field2;

char field3;

};

const int n = 800000;

rec A[n];

bool Equal(rec a, rec b)

{

if ((a.field1 == b.field1) && (a.field2 - b.field2 < 0.001) && (a.field3 == b.field3)) return true;

else return false;

}

bool Less(rec a, rec b)

{

if (a.field1 < b.field1)

return true;

if (a.field1 > b.field1)

return false;

else

{

if (a.field2 < b.field2 - 0.00001)

return true;

if (a.field2 > b.field2 + 0.00001)

return false;

else if (a.field3 < b.field3)

return true;

}

return false;

}

void QuickSort(int L,int R)

{

int i=L, j=R;

int w1;

double w2;

char w3;

rec x = A[(L+R)/2];

while( i <= j )

{

while (Less(A[i], x))

i++;

while (!Less(A[j], x) && !Equal(A[j], x))

j--;

if (i<=j)

{

w1 = A[i].field1;

w2 = A[i].field2;

w3 = A[i].field3;

A[i].field1 = A[j].field1;

A[i].field2 = A[j].field2;

A[i].field3 = A[j].field3;

A[j].field1 = w1;

A[j].field2 = w2;

A[j].field3 = w3;

i++;

j--;

}

}

if(L<j)

QuickSort(L, j);

if(i<R)

QuickSort(i, R);

}

int Search(rec x)

{

int i=0, j=n-1, m;

while (i <= j)

{

m = (i + j) / 2;

if (Equal(x, A[m]))

{

return m;

}

else

{

if (!Less(x, A[m]))

i = m + 1;

else

j = m - 1;

}

}

return (Equal(x, A[m]))?m:n;

}

int main()

{

DWORD time;

int i;

rec x;

for (int i = 0; i < n; i++)

{

A[i].field1 = rand()%1000;

A[i].field2 = (rand()+rand())/100.f;

A[i].field3 = rand()%256;

}

time = GetTickCount();

QuickSort(0, n-1);

cout << A[n-1].field1 << " " << A[n-1].field2 << " " << (int)A[n-1].field3 << endl;

x = A[n - 1];

int FindIndex = Search(x);

if (FindIndex == n)

cout << "Not found!!!";

else

cout << "Index of element = " << FindIndex << endl;

time = GetTickCount() - time;

cout << "Time = " << time << "ms";

_getch();

return 0;

}

C#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace binary_search

{

struct rec

{

public int field1;

public double field2;

public char field3;

}

class Program

{

static int n = 800000;

static rec x = new rec();

static rec[] A = new rec[n];

static bool Equal(rec a, rec b)

{

if ((a.field1 == b.field1) && (a.field2 - b.field2 < 0.001) && (a.field3 == b.field3)) return true;

else return false;

}

static bool Less(rec a, rec b)

{

if (a.field1 < b.field1)

return true;

if (a.field1 > b.field1)

return false;

else

{

if (a.field2 < b.field2 - 0.00001)

return true;

if (a.field2 > b.field2 + 0.00001)

return false;

else if (a.field3 < b.field3)

return true;

}

return false;

}

static void QuickSort(int L, int R)

{

int i = L, j = R;

int w1;

double w2;

char w3;

rec x = A[(L + R) / 2];

while (i <= j)

{

while (Less(A[i], x))

i++;

while (!Less(A[j], x) && !Equal(A[j], x))

j--;

if (i <= j)

{

w1 = A[i].field1;

w2 = A[i].field2;

w3 = A[i].field3;

A[i].field1 = A[j].field1;

A[i].field2 = A[j].field2;

A[i].field3 = A[j].field3;

A[j].field1 = w1;

A[j].field2 = w2;

A[j].field3 = w3;

i++;

j--;

}

}

if (L < j)

QuickSort(L, j);

if (i < R)

QuickSort(i, R);

}

static int Search(rec x)

{

int i = 0, j = n - 1, m = 0;

while (i <= j)

{

m = (i + j) / 2;

if (Equal(x, A[m]))

{

return m;

}

else

{

if (!Less(x, A[m]))

i = m + 1;

else

j = m - 1;

}

}

return (Equal(x, A[m])) ? m : n;

}

static void Main(string[] args)

{

Random r = new Random((int)DateTime.Now.Ticks);

for (int i = 0; i < n; i++)

{

A[i] = new rec();

A[i].field1 = r.Next(1000);

A[i].field2 = r.Next(1000) / 100;

A[i].field3 = (char)r.Next(255);

}

long time = DateTime.Now.Ticks;

QuickSort(0, n - 1);

Console.WriteLine(A[n - 1].field1 + " " + A[n - 1].field2 + " " + A[n - 1].field3);

x = A[n - 1];

int FindIndex = 0;

FindIndex = Search(x);

Console.WriteLine("Index of element = " + FindIndex);

time = DateTime.Now.Ticks - time;

DateTime dt = new DateTime(time);

Console.WriteLine("Time = " + dt.Millisecond.ToString() + "ms");

Console.ReadKey();

}

}

}