|
Zaporozhtsev | Дата: Суббота, 15.10.2011, 22:28 | Сообщение # 1 |
| Сообщений: |
1 |
| Награды: |
0 |
| Статус: |
Offline |
|
Уважаемые учителя информатики, подскажите, пожалуйста, почему способ чтения, приводимый в книгах для подготовки к ЕГЭ, является более эффективным, чем тот, который мне предложили сами учащиеся.
Итак, есть файл, в котором 120000 строк. Каждая строка имеет формат записи о баллах ученика: Фамилия Имя Число.
Есть два алгоритма для тестирования. Каждый из алгоритмов выполняет чтение данных (по 60000 строк каждый, набор строк один и тот же) и небольшую обработку (находит ученика, у которого максимальный балл). Когда алгоритм отработан, выводим количество затраченных секунд.
Код получился следующий
Code
uses crt,dos;
const n = 60000;
var leader_surname, temp_surname: string[30];
temp_name: string[10];
total_line: string[50];
i: longint;
c: char;
max_mark, temp_mark: integer;
position,code: integer;
f: Text;
delta: longint;
bHour,eHour,bMinute,eMinute,bSecond,eSecond,bHund,eHund: word;
begin
clrscr;
assign(f,'input.txt');
reset(f);
max_mark := 0;
getTime(bHour,bMinute,bSecond,bHund);
for i := 1 to n do
begin
temp_surname := '';
repeat
read(f,c);
temp_surname := temp_surname + c;
until c = ' ';
temp_name := '';
repeat
read(f,c);
temp_name := temp_name + c;
until c = ' ';
readln(f,temp_mark);
if temp_mark > max_mark
then leader_surname := temp_surname
else if temp_mark = max_mark
then leader_surname := 'Нет';
end;
getTime(eHour,eMinute,eSecond,eHund);
delta := eHour - bHour;
delta := delta*60 + eMinute - bMinute;
delta := delta*60 + eSecond - bSecond;
delta := delta*100 + eHund - bHund;
writeln('Первый алгоритм -> ',delta div 100,',',delta mod 100,' сек.');
max_mark := 0;
getTime(bHour,bMinute,bSecond,bHund);
for i := 1 to n do
begin
readln(f,total_line);
position := pos(' ',total_line);
temp_surname := copy(total_line,1,position);
delete(total_line,1,position);
position := pos(' ',total_line);
temp_name := copy(total_line,1,position);
delete(total_line,1,position);
val(total_line,temp_mark,code);
if temp_mark > max_mark
then leader_surname := temp_surname
else if temp_mark = max_mark
then leader_surname := 'Нет';
end;
getTime(eHour,eMinute,eSecond,eHund);
delta := eHour - bHour;
delta := delta*60 + eMinute - bMinute;
delta := delta*60 + eSecond - bSecond;
delta := delta*100 + eHund - bHund;
writeln('Второй алгоритм -> ',delta div 100,',',delta mod 100,' сек.');
close(f);
readkey
end.
Первый алгоритм с посимвольным чтением (он приводится в книгах) выполнялся дольше, чем тот, который считывает строку целиком, а затем проводит её разбиение. Результаты: около 2,5 секунд и 0,9 секунд соответственно.
Понятно, что расплатой за быстродействие является строка total_line, то есть нет эффективности по памяти.
Какой же алгортм рекомендовать учащимся? Заранее благодарен.
15.10.2011
|
|
|
|
| |
|
|
astronom | Дата: Суббота, 22.10.2011, 16:16 | Сообщение # 2 |
astronom
Ранг: Магистр (?)
Группа: Пользователи
|
| Сообщений: |
562 |
| Награды: |
7 |
| Статус: |
Offline |
|
 :cranky:
Естественно, второй алгоритм эффективнее по времени, чем первый. Однократное чтение большим блоком всегда быстрее многократного посимвольного чтения.
Просто, первый алгоритм, в чем-то более "естественный" и его проще перенести на другие языки или расписать в виде блок-схемы или псевдокода. Т.к., в нем не используются специфические функции позиционирования в строке и удаления части строки.
По идее, самая неэффективная процедура второго алгоритма - именно удаление части строки, т.к., при этом происходит копирование всей строки в новую область памяти и перемещение указателя.
p.s. Кстати, оба алгоритма уязвимы из-за ориентации на пробельный символ.
Они оба рассчитаны на то, что в каждой строке слова отделены друг от друга одним пробелом.
И они оба будут работать некорректно, если этих пробелов два и более (или в случае табуляции в качестве разграничителя).
Quote Какой же алгортм рекомендовать учащимся?
Здесь выбор между классическим алгоритмом разделения строки (который был еще в K&R) и алгоритмом, ориентированным на знание возможностей конкретного ЯП.
С теоретической точки зрения важнее первое. С практической - второе.
Истины нет нигде 
22.10.2011
Сообщение отредактировал astronom - Суббота, 22.10.2011, 16:39
|
|
|
|
| |
|
|
ИнфоКонсалтинг | Дата: Вторник, 01.11.2011, 02:32 | Сообщение # 3 |
| Сообщений: |
15 |
| Награды: |
1 |
| Статус: |
Offline |
|
Вы можете рекомендовать учащимся любой алгоритм, исходя из критериев оценки эффективности C4. Эффективность в C4 оценивается так, чтобы: 1) не было лишних циклов (в т. ч. вложенных), которых может быть лишен другой (аналогичный) алгоритм; 2) не сохранялись данные, которые не требуют сохранения; 3) не было лишних массивов, без которых может обойтись другой алгоритм, и, тем более, просмотров их содержимого; 4) не использовался оператор множественного выбора (в разных языках switch, select и т. п.); 5) были правильно выбраны типы данных (хотя это - более сложный вопрос, иногда на типы можно закрыть глаза).
При этом имеет смысл говорить о неком плане, согласно которому должно быть выдержано решение: 1) ввод, 2) обработка данных, 3) вывод (часто оказывается необходимым - из соображений той же эффективности - смешивать этапы решения, чтобы, к примеру, избежать двух проходов одного и того же массива).
Не следуйте так буквально книжкам для подготовки, подготовка - это не дрессировка и даже не натаскивание. Тем более теперь. В конце концов, пусть лучше Ваши ученики потеряют балл на эффективности, чем все три-четыре балла из-за нехватки времени, потерянного на раздумья.
01.11.2011
|
|
|
|
| |
|
