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

Подписаться 20 тыс.

Просмотров 6 тыс.

50% 1

Практические занятия по языку 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 - ошибки не будет

Опубликовано:

6 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 22

@user-td8wl7dd4m 8 месяцев назад

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

@ddvamp 15 дней назад

51:10 Константин, как заметили ниже, здесь что-то не так. Во-первых, &arr3[0] это указатель на массив, а &arr3 это указатель на указатель на массив (int (**) [3]). Вероятно вы имели в виду &arr[0] и &arr. Во-вторых, адрес массива нельзя записать в int *, там должен быть как раз int (*parr3)[3]

@siarheimarozau6763 3 месяца назад

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

@antonzhurba865 8 месяцев назад

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

@tilir 8 месяцев назад

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

@vdalart 7 месяцев назад

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

@tilir 7 месяцев назад

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

@ShtrikeBirb 8 месяцев назад

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

@tilir 8 месяцев назад

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

@user-nt1re9ym4i 8 месяцев назад

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

@tilir 8 месяцев назад

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

@user-nt1re9ym4i 8 месяцев назад

@@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 8 месяцев назад

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

@user-nt1re9ym4i 8 месяцев назад

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

@tilir 8 месяцев назад

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

@ivankrutov8789 8 месяцев назад

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

@tilir 8 месяцев назад

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

@victormustya1745 8 месяцев назад

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

@tilir 8 месяцев назад

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

@victormustya1745 8 месяцев назад

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