WW #4

[Sokolov Viacheslav]

Главная цель выполнена (программа свою функцию выполняет корректно), но есть несколько замечаний по стилю, проверке контрактов и эффективности.

в компараторах: хорошо бы добавить not null проверки; при cast-е теряется константность, что плохо (в C++ так уже нельзя будет делать).

В реализации mergesort:
можно использовать shirt-circuit computation ​https://en.cppreference.com/w/c/language/operator_logical , чтобы сократить количество if ... return -1

Чем обусловлен выбор типа int mid = elements / 2;?

int (*comparator) тоже может быть NULL

Можно проверить еще несколько условий: elements * element_size не переполняется, а также element_size != 0

Лично мне кажется неудачным такой стиль выравнивания

11     while (ptr2 < len2 && (comparator(array1 + i * elem_size,
12                                       array2 + ptr2 * elem_size)) >= 0) {

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

Могу предложить несколько альтернатив:

    while (ptr2 < len2 && (comparator(array1 + i * elem_size,
        array2 + ptr2 * elem_size)) >= 0) {

    while (ptr2 < len2 
        && (comparator(array1 + i * elem_size
            , array2 + ptr2 * elem_size)) >= 0) {

    while 
    (
        ptr2 < len2 
        && 
        (
            comparator
            (
                array1 + i * elem_size,
                array2 + ptr2 * elem_size
            )
        ) >= 0
    ) 
    {

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

Сейчас суммарно O(n) аллокаций, можно обойтись одной (это не влияет на корректность, но влияет на производительность. Для целей лабораторной неважно).

Реализацию merge можно упростить, сделав один while, предположение которого - один из указателей еще не достиг границы (метод двух указателей). Будет меньше дублирования кода. Может быть удобно поддерживать не i, ptr2 (названия, кстати, не говорящие и ассиметричные), а полноценные char* ptr1, char* ptr2. Это тоже улучшит производительность: сейчас много умножений, а можно и без них.

Хорошая мысль - после mergesort проверить постусловие: массив отсортирован.

[Alexander Morozov]

1) Поправил компараторы
2) Заменил на один return -1 с short-circuit
3) Я добавил проверку на element_size != 0 и на переполнение, но второе мне кажется очень странным, тогда уж надо брать размер оперативной памяти и проверять, что в него влезает этот массив по размеру, например. Чтобы size_t переполнился, учитывая, что наша сортировка рассчитана ну по крайней мере на данные до терабайта, нужно передать ну совсем какую-то фигню, скорее всего, отрицательные или просто случайные числа. В обоих случаях работает, например, проверить, что значения меньше, чем одна десятая от size_t. Я для проверки переполнения использовал встроенную функцию, которой, видимо, нет в стандарте, но она есть в GCC и Clang. Как-то очень не хотелось использовать деление.
4) Мне тоже такой стиль не особо понравился, тем более, учитывая, что редактор сам просто переносит вылезающие строки, так что они идут ровно по длине монитора, и читаемость особо не ухудшается. Но, я попробовал разные style-гайды в настройках clang-format, и подавляющее большинство из них отформатировало именно так. Наверное, я пока что так и оставлю. Кстати, оно же отформатировано так, чтобы длины строк совпадали, поэтому максимальная длина строки совпадает с длиной строки в первой альтернативе ( и я верю, что style-гайды составлены так, чтобы эта длина строки не превышала какой-то общепринятой константы, 80 в Google, например).
5) Да, я не очень понимаю, как это красиво сделать, поэтому лучше делать не буду. Видимо, надо как-то передавать нашу память вниз по рекурсии, но проблема в том, что нужно ее аллоцировать при первом вызове, видимо, надо добавить аргумент, и сделать ему значение по умолчанию.
6) Если говорить о производительности, то я протестировал оба варианта с for(...){while()} и с while(){if(){}else{}}, первый вариант работает в 5/4 раз быстрее при merge двух массивов размера 1e8, хотя, конечно, это много от чего зависит. На всякий случай все равно переписал на while(), потому что дублирование кода - достаточно весомый аргумент. Еще я считаю нормальным, что в асимметричном алгоритме названия асимметричны. Попробовал заменить их на говорящие, хотя пока что у меня плохо это получается.
7) Да, проверил.

[Sokolov Viacheslav]

3 - да, это защита от "фигни"; отрицательное число передать может оказаться проще, чем кажется. Проблема в том, что в Си очень мало возможностей проверять корректность предположений, потому что работаем на достаточно низком уровне, абстракций мало и они простые.

Одна десятая от size_t

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

на данные до терабайта

size_t может быть 32-битным, тут никакого противоречия нет

4 - на практике 80 - неудачный архаичный выбор, зачастую и в 120 тяжело укладываться из-за прозрачного именования (по 15-20 символов на имя может быть) и выравнивания (4 символа на scope, а их может быть 5-6 вложенных); к сожалению, общепринятый != удачный, общество в целом не рационально

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

6 - здесь будет зависеть в том числе от оптимизаций компилятора и предсказаний переходов внутри процессора. Сравнивать производительность имеет смысл в режиме -DNDEBUG -O3 . Но, конечно, наиболее производительный код зачастую менее читаемый, требования к нему совсем другие.

Кстати, void* некорректно складывать с size_t: ​https://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c