Практика языка C (МФТИ, 2023-2024). Семинар 3.1. Линейный поиск и простые сортировки.

Рет қаралды 5,503

Күн бұрын

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом занятии мы познакомимся с понятием константности, линейным поиском, двумя простейшими алгоритмами сортировок (вставками и выбором) а также научимся читать и писать cdecl и вспомним что такое typedef.
Семинарист: Константин Владимиров.
Дата: 20 октября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Константность
09:25 Typedefs
16:30 Поиск в массивах
23:20 Тасование Фишера-Йетса
28:30 Сортировка: мозговой штурм и наращивание инварианта
36:55 Время решать задачи
40:00 Пузырёк
47:20 Cdecl
52:35 Указатели на функции и qsort
01:03:10 Практикуемся в qsort
01:12:40 Ревью кода и завершение
Errata:
* Слайд 16: опечатка, вместо ++j надо --j
* 5:50 const int * const cpca можно инициализировать и &a, и &b - ошибки не будет

Пікірлер: 21

@user-td8wl7dd4m 7 ай бұрын

Классный сериал👍

@siarheimarozau6763 3 ай бұрын

На рисунке на 52 минуте мне кажется что логичнее написать в первой строчке int *arr[3]; int *pa = &arr[0]; вместо int *arr[3]; int *pa = &arr3[0];

@antonzhurba865 7 ай бұрын

как для практической части не раскрыта тема const для первого курса, когда всё таки его писать и когда его стоит упустить? Также упомянул бы основные проблемы что связанные (потеряна константности, "const poisoning").

@tilir 7 ай бұрын

Мы ещё много раз вернёмся к const. Пока правило простое: не собираемся изменять -- ставим const.

@vdalart 7 ай бұрын

5:50 const int * const cpca можно инициализировать и &a, и &b - ошибки не будет

@tilir 6 ай бұрын

Спасибо, внёс в errata.

@MYYT247 7 ай бұрын

Кстати, а пузырек не выиграет у других в плане утилизации кэша?

@tilir 7 ай бұрын

Нет конечно. Там каждая итерация проходит полное расстояние.

@user-nt1re9ym4i 7 ай бұрын

Спасибо большое за лекцию, было, хоть и не сложно, но интересно. Осталась правда пара вопросов: 1) можно ли написать свою обёртку над qsort, принимающая последним аргументом int (*)(), таким образом нам для каждого компаратора не пришлось бы писать эти явные преобразования из void * в TYPE *? (Вопрос, конечно, почему разработчики qsort так не сделали (скорее всего из-за ухудшения читаемости прототипа функции)) 2) вы рассказали о расстановке квалификатора const и его смысл, однако не объяснили семантику выражения const void *ptr, правда это больше не вопрос, конечно, а придирка) 3) касательно сидекл и динамических массивов, что вы думаете по поводу указателя на vla в роли матрицы? т.е. int (*matrix)[m] = malloc(sizeof *matrix * n); это хорошая практика или же нет?

@tilir 7 ай бұрын

(1) Вы имели в виду int(*)(...)? Это добавить оверхеда которого и так немало. Каст же бесплатный. (3) Плохая практика. Работа VLA не гарантируется на конформной реализации в C и VLA явно запрещены в C++.

@user-nt1re9ym4i 7 ай бұрын

@@tilir с vla понял, а касательно первого вопроса - нет, я имел в виду именно int (*)(), т.е. определение функции-обёртки выглядело бы так: void qsort_(void *arr, size_t num, size_t size, int cmp()) { qsort(arr, num, size_t, cmp); } Либо же ввести макрос а-ля #define QSORT_CB(CMP) (int (*)())CMP и потом вызывать qsort(arr, num, size, QSORT_CB(cmp)); ну либо макрос на сам кусорт Хотя первый вариант мне нравится больше, там же обёртка заинлайнится. И в сухом остатке мы получаем преимущество в виде экономии двух строк для каждого компаратора. т.к. имхо const int *lhsi = lhs; const int *rhsi = rhs; выглядит ужасно

@tilir 7 ай бұрын

@@user-nt1re9ym4i а как может работать компаратор без аргументов?

@user-nt1re9ym4i 7 ай бұрын

@@tilir так в си же объявление функции как int foo(); - синонимично тому, что для функции не предоставлено информации о количестве и типе аргументов, т.е. её можно вызвать с любыми аргументами, а определение int foo() {} да, синонимично функции не принимающей аргументов. UPD: и да, тип int (*)() является совместимым с любым типом int (*)(parameter type list)

@tilir 7 ай бұрын

Я к слову был уверен что это уже запретили году этак в 99м. Это немыслимо дурной хак, подписывающий вас на все возможные проблемы с ABI. Функция без аргументов это void, всё остальное не должно применяться.

@ivankrutov8789 7 ай бұрын

Слайд 16. Кажется нужно заменить ++j на --j.

@tilir 7 ай бұрын

Спасибо, занёс в errata

@victormustya1745 7 ай бұрын

На 17 слайде косяк: следующий минимальный элемент 3, хотя в массиве есть 2 не на своём месте.

@tilir 7 ай бұрын

Мы вслепую запускаем bubble sort каждый раз от конца массива. Он подхватывает в данном случае 3 и начинает её топить обменами вниз. Причём даже когда она перестаёт топиться, он идёт дальше. По дороге он установит и двойку.

@victormustya1745 7 ай бұрын

@@tilirв случае bubble sort да. А в случае selection sort надо выбирать сначала двойку.