Описание работы программы на контрольных примерах. Расчет оптимального количества строк в группе.
Описание работы программы
Вводим имя сортируемого файла, например, test.txt.
Вводим количество строк в группе, например, 300.
Нажимаем кнопку “sort”.
Запускается алгоритм сортировки.
При создании очередного файла на этапе разбиения, в консоли компилятора выводится сообщение:
file 65.txt created
При слиянии в консоли компилятора выводятся сообщения:
80.txt + 81.txt = 168.txt
delete 80.txt
delete 81.txt
По окончании алгоритма, в соответствующие поля выводятся время разбиения, слияния, общее время и время конечного файла с результатом сортировки. Например так:
Расчет оптимального количества строк в группе
Для расчета возьмем три файла:
8000 строк
16000 строк
32000 строк
И измерим время реализации алгоритма при различном количестве строк в группе.
Результаты приведены в таблице:
-
8000 строк
N
t разб, сек
t сл., сек
t общ, сек
300
0,344
0,828
1,172
400
0,266
0,828
1,094
500
0,281
0,563
0,844
600
0,329
0,578
0,907
700
0,375
0,578
0,953
1000
0,562
0,313
0,875
1200
0,937
0,391
1,328
1500
0,75
0,344
1,094
2000
1,125
0,203
1,328
3000
1,015
0,188
1,203
4000
1,454
16000 строк
200
0,484
1,875
2,359
400
0,484
1,469
1,953
500
0,562
1,203
1,765
700
0,656
1,188
1,844
1000
0,969
0,969
1,938
2000
2,906
64000 строк
200
11,578
300
9,89
400
10,312
500
9,5
600
8,906
700
9,469
800
9,531
1000
9,563
2000
13,297
Из таблицы видно, что не смотря на существенные отличия в размерах файлов оптимальное количество строк в группе примерно одинаково и равно 500-600 строк.
Так же из таблицы можно сделать вывод, что разбиение с сортировкой значительнее влияет на общее время чем слияние. Наблюдаем такую зависимость:
Функция времени разбиения с увеличение количества строк возрастает.
Функция времени слияния с увеличение количества строк убывает.
Но заметно, что время разбиения возрастает быстрее, чем убывает время слияния, поэтому при разбиении файла группами по 500-600 строк алгоритм работает быстрее.
Из аналитического исследования было получено, что функция времени разбиения от количества строк – это парабола, ветви которой направлены вверх, а функция времени слияния – это логарифм. Очевидно, что парабола будет возрастать быстрее, чем уменьшаться логарифм, что подтверждает результаты эксперимента.