Старая форма входа
Регистрация
Дорогие друзья!
Наш форум закрыт для общения сейчас,
но вы можете задать свой вопрос или перейти в чат Телеграм.
Пожалуйста, напишите на почту files@21vu.ru ваш вопрос, ситуацию, чтобы обратиться к коллегам в чате.
Если вы хотите просто вступить в чат, также напишите на почту, укажите сведения о себе: ФИО, кто вы, кто по профессии, чем можете быть полезны педагогам, и мы направим вас в Чат Телеграм.
  • Страница 1 из 1
  • 1
Модератор форума: Екатерина_Пашкова  
"Эффективный" ввод данных в задаче С4: память или время?
ZaporozhtsevДата: Суббота, 15.10.2011, 22:28 | Сообщение # 1
Zaporozhtsev

Иван Запорожцев
Ранг: Дошколенок (?)
Группа: Зарегистрированные
Сообщений:
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 :cranky: cranky
Естественно, второй алгоритм эффективнее по времени, чем первый. Однократное чтение большим блоком всегда быстрее многократного посимвольного чтения.
Просто, первый алгоритм, в чем-то более "естественный" и его проще перенести на другие языки или расписать в виде блок-схемы или псевдокода. Т.к., в нем не используются специфические функции позиционирования в строке и удаления части строки.
По идее, самая неэффективная процедура второго алгоритма - именно удаление части строки, т.к., при этом происходит копирование всей строки в новую область памяти и перемещение указателя.

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

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

Здесь выбор между классическим алгоритмом разделения строки (который был еще в K&R) и алгоритмом, ориентированным на знание возможностей конкретного ЯП.
С теоретической точки зрения важнее первое. С практической - второе.
Истины нет нигде biggrin
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
  • Страница 1 из 1
  • 1
Поиск:



Отзывы

Егорова Елена 5.0
Отзыв о товаре ША PRO Анализ техники чтения по классам
и четвертям
Хочу выразить большую благодарность от лица педагогов начальных классов гимназии «Пущино» программистам, создавшим эту замечательную программу! То, что раньше мы делали «врукопашную», теперь можно оформить в таблицу и получить анализ по каждому ученику и отчёт по классу. Великолепно, восторг! Преимущества мы оценили сразу. С начала нового учебного года будем активно пользоваться. Поэтому никаких пожеланий у нас пока нет, одни благодарности. Очень простая и понятная инструкция, что немаловажно! Благодарю Вас и Ваших коллег за этот важный труд. Очень приятно, когда коллеги понимают, как можно «упростить» работу учителя.
Наговицина Ольга Витальевна 5.0
учитель химии и биологии, СОШ с. Чапаевка, Новоорский район, Оренбургская область
Отзыв о товаре ША Шаблон Excel Анализатор результатов ОГЭ
по ХИМИИ
Спасибо, аналитическая справка замечательная получается, ОГЭ химия и биология. Очень облегчило аналитическую работу, выявляются узкие места в подготовке к экзамену. Нагрузка у меня, как и у всех учителей большая. Ваш шаблон экономит время, своим коллегам я Ваш шаблон показала, они так же его приобрели. Спасибо.
Чазова Александра 5.0
Отзыв о товаре ША Шаблон Excel Анализатор результатов ОГЭ по
МАТЕМАТИКЕ
Очень хороший шаблон, удобен в использовании, анализ пробного тестирования занял считанные минуты. Возникли проблемы с распечаткой отчёта, но надо ещё раз разобраться. Большое спасибо за качественный анализатор.
Лосеева Татьяна Борисовна 5.0
учитель начальных классов, МБОУ СОШ №1, г. Красновишерск, Пермский край
Отзыв о товаре Изготовление сертификата или свидетельства конкурса
Большое спасибо за оперативное изготовление сертификатов! Все очень красиво. Мой ученик доволен, свой сертификат он вложил в портфолио. Обязательно продолжим с Вами сотрудничество!
Язенина Ольга Анатольевна 4.0
учитель начальных классов, ОГБОУ "Центр образования для детей с особыми образовательными потребностями г. Смоленска"
Отзыв о товаре Вебинар Как создать интересный урок:
инструменты и приемы
Я посмотрела вебинар! Осталась очень довольна полученной информацией. Всё очень чётко, без "воды". Всё, что сказано, показано, очень пригодится в практике любого педагога. И я тоже обязательно воспользуюсь полезными материалами вебинара. Спасибо большое лектору за то, что она поделилась своим опытом!
Арапханова Ашат 5.0
ША Табель посещаемости + Сводная для ДОУ ОКУД
Хотела бы поблагодарить Вас за такую помощь. Разобралась сразу же, всё очень аккуратно и оперативно. Нет ни одного недостатка. Я не пожалела, что доверилась и приобрела у вас этот табель. Благодаря Вам сэкономила время, сейчас же составляю табель для работников. Удачи и успехов Вам в дальнейшем!
Дамбаа Айсуу 5.0
Отзыв о товаре ША Шаблон Excel Анализатор результатов ЕГЭ по
РУССКОМУ ЯЗЫКУ
Спасибо огромное, очень много экономит времени, т.к. анализ уже готовый, и особенно радует, что есть варианты с сочинением, без сочинения, только анализ сочинения! Превосходно!
Спорная ситуация с родителями или администрацией? Ищете выход из проблемы на уроке или с учеником?
Не знаете, как что-то сделать на компьютере?


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