OberonCore
https://forum.oberoncore.ru/

ЦД для подсчёта количества повторяющихся элементов
https://forum.oberoncore.ru/viewtopic.php?f=82&t=4027
Страница 1 из 2

Автор:  Илья Ермаков [ Четверг, 19 Июль, 2012 15:43 ]
Заголовок сообщения:  ЦД для подсчёта количества повторяющихся элементов

При расчёте статистики по результатам ЕГЭ в регионе у нас в ОРЦОКО пришлось кое-что дописывать, т.к. федеральное ПО ужасное и не считает всё, что нужно.
Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена.
Программист сортирует экспортированные из системы результаты экзаменов в Excel по полю "номер паспорта" и дальше сохраняет в CSV одну только эту колонку. Т.е. имеется последовательность строк с номерами паспортов, где каждый номер повторяется (рядом) столько раз, сколько человек сдавал экзаменов.
Программист сейчас ваяет на ББ процедурку, которая посчитает статистику.
Я тоже тут накидал алгоритм. Не напрягая мозги, получился сразу цикл Дейкстры. Тестировать не тестировал, написал на бумажке.
Правда, программист не хочет его брать, говорит, что не понимает :) Колдует уже час над вложенными циклами, пытаясь, к тому же, это сделать прямо над TextMappers.Scanner.

Привожу свой вариант:
Код:
stat[i] имеет смысл количества человек, сдававших i экзаменов
обнуление массива stat
i := 0; j := 1; (* Инвариант: [i, j) - интервал из одинаковых номеров паспортов *)
WHILE (j < len) & (pass[j] = pass[i]) DO
   INC(j)
ELSIF (j < len) & (pass[j] # pass[i]) DO
   INC(stat[j - i]); i := j; j := i + 1
END;
IF i < len THEN (* чтобы алгоритм был применим к пустой последовательности *)
   INC(stat[j - i])
END

Автор:  Peter Almazov [ Четверг, 19 Июль, 2012 17:22 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Программа правильная (не тестировал :) ), цикл Дейкстры оправдан.
Инвариант, как всегда, неправильный. Точнее, сильно неполный.
Кроме того, я бы для наглядности ввел термин "площадка".

Автор:  albobin [ Четверг, 19 Июль, 2012 21:11 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Видимо описка
не INC(i), а INC(j) надо

Автор:  Илья Ермаков [ Четверг, 19 Июль, 2012 23:47 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Peter Almazov писал(а):
Инвариант, как всегда, неправильный. Точнее, сильно неполный.


Ну, фактически, я назвал ровно такой инвариант, который объясняет смысл переменных... А не инвариант для полной формализации цикла.

Автор:  Илья Ермаков [ Четверг, 19 Июль, 2012 23:48 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

albobin писал(а):
Видимо описка
не INC(i), а INC(j) надо

Да, спасибо.

Автор:  Владислав Жаринов [ Пятница, 20 Июль, 2012 02:30 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Да, я вот не сразу понял, что для ББ это именно алгоритм... с записью ЦД на О-07... где-то с полминуты пытался въехать, как IF должен сочетаться с ELSIF на КП... :)

Кстати, в теле IF описка - круглая скобка инкремента не закрыта.

В комментарии у инварианта скобки разные - но это, я так понимаю, потому что запись математическая и имеется в виду интервал со вхождением одной из границ?..

У программиста, видимо, получится по принципу того, с чего начинался этот пример :) - т.е. с дополнительными индексными переменными и операциями над ними.

Автор:  ==== [ Пятница, 20 Июль, 2012 03:56 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Ну вот, всегда так с ЦД.

И инвариант не тот,

и школярская привычка в программировании использовать одно буквенные идентификаторы, при этом визуально мало различимые ( i , j ), а не слова наполненные смыслом из предметной области,

и ошибку признаем, но алгоритм не правим,

и запись алгоритма неизвестно на каком языке, "Правда, программист не хочет его брать, говорит, что не понимает",

и следуя принципу максимальной простоты, т.е. автомата Калашникова и применив декомпозицию необходимость в ЦД исчезнет.

Автор:  ==== [ Пятница, 20 Июль, 2012 05:36 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Видимо описка
не INC(stat[j - i] ,
а INC(stat[j - i]) надо

Автор:  albobin [ Пятница, 20 Июль, 2012 06:33 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Присоединяюсь к тому, что в данном случае ЦД особо и ничего не даёт, проход ведь до конца массива. IMHO наглядней даже без него, в теле тогда будет только IF без веток ELSE.
Несколько напрягает приспособление реализации алгоритма к случаю с пустым массивом.Это по идее надо обеспечивать в охватывающем коде (не вызывать или не выполнять, если не по чему считать). Тогда и последний INC stat будет безусловный.

Автор:  Peter Almazov [ Пятница, 20 Июль, 2012 06:56 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Илья Ермаков писал(а):
Ну, фактически, я назвал ровно такой инвариант, который объясняет смысл переменных... А не инвариант для полной формализации цикла.
Идиотское убеждение (от Info21), что инвариант нужен некоему дяде, причем только в редких, особо торжественных случаях, и только после того, как цикл написан, оставляю без комментариев.

Я говорю о том, что запись
(* Инвариант: [i, j) - интервал из одинаковых номеров паспортов *)
не ведет к построению правильного цикла. Предположим, в последовательности с самого начала идут номера паспортов 1,1,1,1,1. В некоем цикле i=2, j=4.
Между [i и j) одинаковые номера паспортов? - Одинаковые.
Устроит ли нас такая трактовка? - Нет, не устоит.

Шаг в правильном направлении: "в i содержится индекс начала последней площадки".

Автор:  albobin [ Пятница, 20 Июль, 2012 09:00 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Эпитеты случаются быть и самоприменимыми :lol:

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 09:14 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Peter Almazov писал(а):
не ведет к построению правильного цикла.


Какая разница, каким способом построить правильный цикл?
Идея Info21 относительно ЦД в том, что ЦД позволяет многие циклы вывести из категории "требует полностью формального вывода" в категорию "очевидно и правильно строится путём анализа семантики задачи".
Второй вариант более желателен, тогда как первый нужно применять только, если невозможен второй (с этим обычно не соглашаются математики и спорят с физиками и инженерами).

Напоминаю, что доказать - это не значит провести какие-то "священнодействия", а это значит предоставить проверяемую вещь в такой форме, в которой в её правильности может убедиться любой желающий.

Для инженерной практики введение более простых способов обеспечить надёжность - это прогресс... Иначе "полным методом" так и будут пользоваться единицы.

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 09:31 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Peter Almazov писал(а):
Идиотское убеждение (от Info21), что инвариант нужен некоему дяде, причем только в редких, особо торжественных случаях, и только после того, как цикл написан, оставляю без комментариев.


Нет, инвариант, разумеется, нужен до цикла. Но совершенно необходима та его часть, которая задаёт соотношение между значениями переменных цикла. И эта часть очень естественно вытекает из семантики алгоритма.
Если нужен формальный вывод, то часто инвариант усиливается искусственными (очевидными с точки зрения семантики) частями: типа, что в пройденной части массива все элементы меньше искомого. Т.е. начинается эффект "проще было бы опустить, чем загромождать очевидными вещами".

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 09:35 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

albobin писал(а):
Это по идее надо обеспечивать в охватывающем коде (не вызывать или не выполнять, если не по чему считать). Тогда и последний INC stat будет безусловный.


Я придерживаюсь такого принципа:
WHILE должен работать не 1 и более раз, а 0 и более раз...
Т.е. "охранять" WHILE - только в крайних случаях...
В этой задаче, конечно, возникает некая шероховатость, что приходится охранять действие после WHILE.

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 09:37 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Peter Almazov писал(а):
Предположим, в последовательности с самого начала идут номера паспортов 1,1,1,1,1. В некоем цикле i=2, j=4.
Между [i и j) одинаковые номера паспортов? - Одинаковые.
Устроит ли нас такая трактовка? - Нет, не устоит.

Да, конечно, термин "площадка" стоит ввести и вписать в комментарий инвариант точнее. Не опуская очевидную, но достаточно ценную часть его, что i - это начало площадки.

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 09:43 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Цитата:
и школярская привычка в программировании использовать одно буквенные идентификаторы, при этом визуально мало различимые ( i , j ), а не слова наполненные смыслом из предметной области,

Смысловые идентификаторы использую для внешних сущностей, локальные переменные имеет смысл называть короче, чтобы они выделялись.
Смысл их должен быть как можно более очевиден из самой процедуры (и инварианта в комментарии, если нужно). Процедура - обычно не более 10-20 строк....
Перепишите для сравнения с вместо i и j с именами currentAreaBeg и currentAreaEnd и сравните читаемость.

Цитата:
и ошибку признаем, но алгоритм не правим,

Алгоритм там правильный, опечатка "признанная" тоже была исправлена.

Цитата:
и следуя принципу максимальной простоты, т.е. автомата Калашникова и применив декомпозицию необходимость в ЦД исчезнет.

Примените, покажите. Убедиться в том, что два вложенных и тесно связанных цикла работают правильно, будет, думаю, труднее.

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 10:13 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Вчера минут через 40 трудов и нескольких выходов покурить программист закончил свой вариант. Получилось вот что:

Код:
i := 0;
WHILE i < total DO
  count := 0;
  current := m[i];
  WHILE (i < total) & (current = m[i]) DO
    INC(i);
    INC(count)
  END
  INC(stat[count])
END


В общем, тоже разборчиво, но "подозрительно": два цикла манипулируют единственной переменной i и т. д.

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 10:18 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Ну и "на закуску", для сравнения - разворачиваю ЦД в два вложенных цикла:

Код:
i := 0;
WHILE i < len DO
   j := i + 1;
   WHILE (j < len) & (pass[j] = pass[i]) DO
     INC(j)
   END;
   INC(stat[j-i])
   i := j
END


Если сравнивать ЦД и последний вариант (помня, что последний легко написался уже после ЦД), то плюсом ЦД является то, что он требует "полноты анализа ситуаций". Т.е. сразу перечисляешь на одном уровне и все возможные действия, и условия, при которых эти действия активизируются. Не думая о том, как между собой взаимодействуют вложенные циклы.
Но с точки зрения читателя вариант, преобразованный во вложенные, может быть попонятней. С другой стороны, вопрос, хотим ли мы сохранять в коде понятность хода мыслей? Иногда смотришь на понятный алгоритм, но понимаешь, что скрыт объём работы при его построении...
+ фактор развиваемости: если что-то понадобится менять, усложнится задача, то ЦД гораздо проще развивать...
Можно, конечно, класть начальный ЦД в комментарий (в фолд), а писать преобразованный вариант.

Автор:  albobin [ Пятница, 20 Июль, 2012 12:39 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Исходный ЦД-код очевидным образом преобразуется в:
Код:
i := 0; j := 1;
WHILE (j < len)  DO
   IF  (pass[j] # pass[i])  THEN   INC(stat[j - i]); i := j  END;
   INC(j)
END;
IF i < len THEN  INC(stat[j - i]) END;

Не знаю правильно ли ';' расставлены , но это не беда

Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 12:52 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов

Ну да, это получается, по сути, оптимизированная запись ЦД (упаковка двух циклов в один с "щёлкающими" ветками остаётся).

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/