Файл: Сравнительный анализ описания данных для различных языков программирования.pdf
Добавлен: 22.04.2023
Просмотров: 186
Скачиваний: 2
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. В бинарном поиске наиболее быстро работает реализация на языке С++.
В целом производительность бинарного поиска гораздо выше, чем у линейного поиска. Но за счет алгоритма сортировки реализация бинарного поиска работает гораздо медленней.
На самом деле сказать какой из алгоритмов поиска лучше всего подходит для решения задачи поиска очень сложно. Невозможно сказать какой алгоритм является самым оптимальным. Выбор алгоритма поиска зависит от условий конкретной задачи, которую нам нужно решить.
Список литературы
- Окулов С. М. Основы программирования М.: Юнимедиастайл, 2002 – 424 с.: ил.
- Бьерн Страуструп Язык программирования С++ М.: Бином–Пресс, 2011 – 1136 с.: ил.
- Герберт Шилдт С#: Учебный курс М.: Издательская группа BHV, 2003 – 512 с.: ил.
- 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;