WW#4

[Sokolov Viacheslav]

COMPARATOR выглядит отвратительно: баланс скобок не сходится. Если уж делать такой макрос, то лучше либо разбить на две части (START / END), что неудобно в использовании, либо заносить и само выражение под макрос.
Кроме того, теряется const, что не есть хорошо. "Удобно" оформлять макросы как и обычные функции с помощью символа переноса '\'. При этом для читаемости может быть хорошей идеей выравниать \ между разными строками одинакого.

TYPE зависит от sort_type, поэтому стоит либо сузить область видимости этого макроса до такой, что его гарантированно можно использовать, либо вынести sort_type в параметры.

При такой любви к макросам удивительно видеть в main.c кусок, повторяющийся 5 раз.

Чем обусловлен выбор strtol? Есть же atoi и sscanf

like за naming conventions

Проверка контрактов! ​https://wiki.compscicenter.ru/index.php/C%2B%2B_1MIT_осень_1_2019#.D0.A2.D1.80.D0.B5.D0.B1.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F_.D0.BA.D0.BE.D1.80.D1.80.D0.B5.D0.BA.D1.82.D0.BD.D0.BE.D1.81.D1.82.D0.B8.2C_.D0.BF.D1.80.D0.B5.D0.B4.D1.8A.D1.8F.D0.B2.D0.BB.D1.8F.D0.B5.D0.BC.D1.8B.D0.B5_.D0.BA_.D1.80.D0.B0.D0.B1.D0.BE.D1.82.D0.B0.D0.BC
Есть нетривиальный контракт: nel * width не переполняется, его тоже хорошо бы проверить

nel*width встречается несколько раз. В цикле так вообще будет вычисляться на каждую итерацию (или нет). Лучше вынести в отдельную переменную.

Та же истрия с p1 * width, p2 * width.
Реализацию можно упростить: поддерживать два указателя на области памяти в первой и второй половине; сделать один while, в котором предполагается, что один из указателей уже достиг своего конца. Уйдет дублирование кода.
Кроме того, операцию копирования памяти можно вынести в отдельную функцию (опять же, выше модульность, меньше шанс ошибиться).

Из минусов такой реализации (не предлагаю исправлять): malloc позовется О(n) раз, а можно было бы позвать всего 1 раз.

[Igor Engel]

Слегка поменял компаратор. Не получается сделать совсем красиво, не делай при этом страшных костылей( (типа #define { ; ...)
const вроде поставил
О, не знал что \

Переместил

Ну штош..

О, когда искал как это в C делать, чёт не нашёл atoi....

)

Вроде впихнул, кроме контракта про поведение компаратора, но его как-то нормально не проверить, и вообще, это вроде UB а не контракт)

Декомпозировал сортировку во много фнукций, немного другим образом, но от большинства дублирований вроде избавился.

[Sokolov Viacheslav]

Несимметрично

57     if(mergesort(a, nel1, width, cmp) != 0) return -1;
58     if(mergesort(a+shift, nel2, width, cmp)) return -1;

Мне не очень нравится именование, но сейчас я не готов тратить время на комментарии (потому что еще много других работ, а это не столь важно). Я бы просто рекомендовал почитать что-нибудь (/посмотреть видеоролик) про именование и почаще задавать себе вопрос "почему я называю эту сущность именно так, а не иначе". Примеры: m, pa; комментарий про Mem-суффикс - нет ни одного указателя с суффиксом Mem.

Готов поставить 11й балл за ответ на серию вопросов.

1) Действительно ли программа полностью соответствует требованию, описанному в задании? Если нет, то почему?

2) Какие еще проверки можно было бы добавить в файл mergesort.c?

[Igor Engel]

Упс. Поправил.

m от merge, но да, как-то черезмерно сократил, согласен. pa - указатель на положение в a. -Mem присутствует в copyElement, но вообще да, можно было-бы убрать, учитывая что все остальные перестали быть -Mem.

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

2) width != 0, каким-то неясным образом проверить контракт компаратора (ну, или падать если вдруг заметили ошибку), ещё возможно выравнивание width, так-как невыровненная память это вроде как UB, но не уверен.

[Sokolov Viacheslav]

1 - вывод ошибки аллокации в main, тут все как надо. Предлагаю еще подумать, вопрос с подвохом (предполагает знание стандарта языка).

2 - компаратор проверить не получится (потому что он может быть недетерменированным и работать неправильно, если температура процессора поднялась выше скольки-то градусов, а в указателях зашифрованно послание). Проверять UB не предлагаю. Речь о проверках, которые можно сделать в предположении, что вызывающий код написан без UB, но с логическими ошибками. Предлагается проверять три вещи: предусловия, инварианты, постусловия. Здесь есть, что проверить.

[Igor Engel]

1) чёт пока ничего не могу найти... имеется ввиду какое-то несоответствие конкретным условиям лабы, или что-то вроде UB? (учитывая, что предпологается знание стандарта...)

2)
mergesort:
Предусловия:
Массив содержит хотя-бы nel элементов, каждый размера width - непроверяемо
массив и компаратор не NULL - проверено
width не 0 - чё-то забыл
nel*width не приводит к переполнению - проверено
Инварианты:
После рекурсивных вызовов, каждая половина массива должна быть отсортированна - в теории можно проверить
Постусловия:
Массив должен быть отсортирован - в теории можно проверить
merge:
Предусловия:
a1 != NULL, a2 != NULL - можно проверить
a1, a2 отсортированы - в теории можно проверить
Непересечения a1, a2 и m - навесить restrict
width != 0, cmp != NULL - можно проверить
Инварианты:
-
Постусловия:
m отсортирован - в теории можно проверить
finalize_merge:
Предусловия:
a, m != NULL, width != 0 - можно проверить
a - отсортирован - в теории можно проверить
Инварианты:
-
Постусловия:
Префикс m до pm отсортирован - в теории можно проверить

copy_element:
Предусловия:
src, dest != NULL, wdith != 0 - можно проверить
Инварианты:
-
Постусловия:
dest[destPos..destPos+width] == src[srcPos..srcPos+width]

[Sokolov Viacheslav]

1) Предлагаю обратить внимание вот на это место

3. При возникновении данной ошибки программа должна вывести единственную строчку Error: memory allocation failed. и завершить работу с кодом возврата 1

2)

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

достаточно в конце функции проверить, что массив отсортирован

Пример инварианта для merge: очередной отправляемый "в конец" элемент должен быть не меньше предыдущего (либо первым). Такая проверка позволяет поймать в точности тот момент алгоритма, когда что-то идет не так.

Постусловия: dest[destPos..destPos+width] == src[srcPos..srcPos+width]

В каком-то идеальном мире можно, но это в большей степени трата сил и времени. Не могу себе представить ситуацию, когда проверка подобной однострочной функции была бы оправдана. Тем не менее и эта проверка нетривиальна: это неверно, если области перекрываются.

[Igor Engel]

1)
Так. Заметил что у main нету return 0; в конце... Очень странно что gcc на такое не ругается, причём, никак не получилось его заставить ругаться... В осталоьном по этому пункту вроде всё норм... doSort развёрнутый из макроса выводит строку, возвращает 1, это обрабатывается макросом, и возвращает 1 из main'а...

2)
Да, действительно

Хм, интересно, почему-то не подумал о таком

Там вообще много условий для "идального" (или наоборот, ужасающего...) мира...

[Sokolov Viacheslav]

Про return 0: по стандарту так можно ​https://stackoverflow.com/a/13232919

Возвращаясь к исходному вопросу:

При возникновении данной ошибки программа должна вывести единственную строчку Error: memory allocation failed. и завершить работу с кодом возврата 1.

должна вывести

А может ли? Завершить работу с кодом возврата 1 получится. А вот вывести на экран может не получиться по не зависящим от программиста причинам:
1) функция вывода и не гарантирует, что она что-то выведет (она и не может - всегда может быть отказ оборудования); но она гарантированно вернет управление
2) при этом в стандарте не описано, требуется ли для вывода аллокация памяти или нет - а вдруг почему-то требуется? В таком случае стоит насторожиться: память-то, вероятно, закончилась (мы точно знаем, что не удалось аллоцировать), это нештатная ситуация; может быть, и с выводом на возникнут трудности.

В общем я считаю, что в этот раз бонусный балл остается у меня (поработайте над именованием и чистотой - в следующий раз будет Ваш); надеюсь, размышления и обсуждения были полезными (что важнее баллов и оценок).