Страница 1 из 11
Модератор форума: Екатерина_Пашкова 
Форум учителей об образовании в России и мире » Форум педагогов по предметам, разделам » Форум учителей информатики » "Эффективный" ввод данных в задаче С4: память или время?
"Эффективный" ввод данных в задаче С4: память или время?
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, то есть нет эффективности по памяти.
Какой же алгортм рекомендовать учащимся? Заранее благодарен.
Спасибо
astronomДата: Суббота, 22.10.2011, 16:16 | Сообщение # 2

Алексей Шеллер
Ранг: Магистр (?)
Группа: Пользователи
Российская Федерация
Подольск

Сообщений:
562
Награды: 7
Статус: Offline
cranky :cranky: cranky
Естественно, второй алгоритм эффективнее по времени, чем первый. Однократное чтение большим блоком всегда быстрее многократного посимвольного чтения.
Просто, первый алгоритм, в чем-то более "естественный" и его проще перенести на другие языки или расписать в виде блок-схемы или псевдокода. Т.к., в нем не используются специфические функции позиционирования в строке и удаления части строки.
По идее, самая неэффективная процедура второго алгоритма - именно удаление части строки, т.к., при этом происходит копирование всей строки в новую область памяти и перемещение указателя.

p.s. Кстати, оба алгоритма уязвимы из-за ориентации на пробельный символ.
Они оба рассчитаны на то, что в каждой строке слова отделены друг от друга одним пробелом.
И они оба будут работать некорректно, если этих пробелов два и более (или в случае табуляции в качестве разграничителя).

Quote
Какой же алгортм рекомендовать учащимся?

Здесь выбор между классическим алгоритмом разделения строки (который был еще в K&R) и алгоритмом, ориентированным на знание возможностей конкретного ЯП.
С теоретической точки зрения важнее первое. С практической - второе.
Истины нет нигде biggrin


Сообщение отредактировал 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) вывод (часто оказывается необходимым - из соображений той же эффективности - смешивать этапы решения, чтобы, к примеру, избежать двух проходов одного и того же массива).
Не следуйте так буквально книжкам для подготовки, подготовка - это не дрессировка и даже не натаскивание. Тем более теперь. В конце концов, пусть лучше Ваши ученики потеряют балл на эффективности, чем все три-четыре балла из-за нехватки времени, потерянного на раздумья.
Спасибо
Форум учителей об образовании в России и мире » Форум педагогов по предметам, разделам » Форум учителей информатики » "Эффективный" ввод данных в задаче С4: память или время?
Страница 1 из 11
Поиск:



Спорная ситуация с родителями или администрацией? Ищете выход из проблемы на уроке или с учеником?
Не знаете, как что-то сделать на компьютере?


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