03-pointers2 (1238873)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

МАССИВЫ И УКАЗАТЕЛИМассивы, указатели и константность. Указатели на функции.Некоторые приложения к сортировке и поискуК. Владимиров, Intel, 2019mail-to: konstantin.vladimirov@gmail.comКонстантность в языке C•Распространённая языковая конструкция const означает неизменяемость.Неизменяемость полезна, поскольку упрощает и оптимизации и поддержкуintintintint•a = 4, b = 4;const c = 5, d = 6;const * pc = &c;* const cpa = &a;////////целыенеизменяемые целыеуказатель на неизменяемое целоенеизменяемый указатель на целоеПрименениеa = 6;с = 6;pc = &d;cpa = &b;////////ok, теперь (*cpa == 6)ошибкa, неизменяемые данныеok, теперь (*pc == 6)ошибка, неизменяемый указательОбъявления функций с массивами•Очень часто const используется в аргументах функций// Эта функция может прочитать и изменить массивvoid foo(int *arr, unsigned len);// Эта функция может только прочитать массивvoid bar(int const *arr, unsigned len);•Также двойственность между массивами и указателями позволяет писатьvoid foo(int arr[], unsigned len);void bar(int const arr[], unsigned len);Поиск в массивах•На входе функции указатель на первый элемент некоего массива и длинамассива, а также искомый элементunsigned search(int const *parr, unsigned len, int elem);•Необходимо вернуть позицию элемента от 0 до len-1 если он есть или len,если он не найденint arr[6] = {1, 4, 10, 21, 43, 56};unsigned p10 = search(arr, 6, 10);unsigned p42 = search(arr, 6, 42);assert(p10 == 2 && p42 == 6);•Наивным (но часто единственным) подходом будет просматривать каждыйэлемент последовательноАлгоритм L – линейный поискunsignedlinear_search(int const * parr, unsigned len, int elem) {unsigned i;for (i = 0; i < len; ++i)if (parr[i] == elem)return i;return len;}•Алгоритм достойный и заслуженный, но если массив на входе отсортирован, томожно действовать лучшеСтратегия разбиения пополам•Также известна как "divide and conquer"1122223451122223452345567899910 11 12Алгоритм B – бинарный поискunsignedbinary_search(int const * parr,int l = 0; int r = len - 1;while (l <= r) {int m = l + (r - l) / 2;if (parr[m] == elem) returnif (parr[m] < elem) l = m +if (parr[m] > elem) r = m }return len;}•unsigned len, int elem) {m;1;1;Сравните линейный и бинарный поиск: выделите в куче достаточно большой,последовательно заполненный массив и поищите 10000 раз случайные значенияАсимптотика•Оцените асимптотику алгоритма B и алгоритма L•Вам приносят реальные замеры времени поиска на некоторых данных и вывидите, что алгоритм L вдвое быстрее чем B.

Что вы можете сказать об этихданных?Смена стратегии поиска•Функции линейного и бинарного поиска имеют одинаковую сигнатуруtypedef unsigned (*search_t)(int const *, unsigned, int);•Теперь можно завести переменную такого типа (указатель на функцию) ивызывать линейный или бинарный поиск во время выполненияsearch_t func = &linear_search;func(unordered_arr, 10, -2); // вызвана linear_searchfunc = &binary_search;func(ordered_arr, 20, 5); // вызвана binary_search•Скоро идея указателя на функцию будет использована для некоторыхобобщений поиска и сортировкиЗапутанные правила typedeftypedef int myint_t;myint_t x = 2;// myint_t становится синонимом int// ok, x имеет тип inttypedef int myint3_t[3]; // тип myint3_t это int[3]myint3_t y = {1, 2, 3}; // ok, y это массив// тип myintf_t это указатель на функцию, которая// берёт два целых числа и возвращает целоеtypedef int (*myintf_t)(int, int);int plus(int x, int y) { return x + y; }myintf_t z = +int a = z(2, 3); // ok, теперь a == 5Давний холивар: East Const•Модификатор const означает константность того, что слева от него.

Но если слеваот него ничего нет, то он распространяется на то, что справа от него•const стоящая в нормативной позиции (справа от того что должно статьконстантным) называется east const (восточный const, близко к "East Coast")int const x; // неизменяемое целое (east const)const int y; // неизменяемое целое (west const)int const *x; // указатель на неизменяемое целое (east const)const int *x; // указатель на неизменяемое целое (west const)int *const x; // неизменяемый указатель на целое (east const)•Против west const есть веский аргумент от typedefsДавний холивар: East Const•Модификатор const означает константность того, что слева от него. Но если слеваот него ничего нет, то он распространяется на то, что справа от него•const стоящая в нормативной позиции (справа от того что должно статьконстантным) называется east const (восточный const, близко к "East Coast")typedef int * pint_t; // теперь pint_t это int *pint_t const x; // тоже, что int * const xconst pint_t x; // не тоже, что const int * x•В случаях, показанных выше, west const может ввести в заблуждение•Увы, в существующем коде много таких констант и многие любят их писать и дажепишут принципиальноProblem ME – поиск большинства•На входе функции указатель на первый элемент произвольного массива идлина массива (решение этой задачи не предполагает сортировки)int majority_element(int const * parr, unsigned len);•Необходимо определить, есть ли в массиве элемент, который встречаетсябольше len/2 раз и вернуть его значение (или -1 если никакой элемент необразует большинства)int arr[5] = {3, 2, 9, 2, 2};int x = majority_element(arr, 5);assert(x == 2);•Напишите тело функции (необязательная задача повышенной сложности:сделайте это без рекурсии)Problem MSB – битовый поиск•Напишите функцию, ищущую старший установленный бит в числеunsigned msb(unsigned x);•На входе функции число типа unsigned•На выходе номер её старшего бита, первый бит имеет номер 1.

Для 0x7fffэто 15. Если ни один бит не установлен, то 0.•Задача со звёздочкой (опционально): совместите эту функцию и поиск, чтобынайти номер старшего установленного бита в массивеunsigned arrmsb(unsigned char const * parr, unsigned len);•Например для массива {0, 3, 26} результатом будет 66Стратегия "разделяй и властвуй"•И алгоритм B, и проблема ME имеют нечто общее: каждая итерацияалгоритма уменьшает размер рассматриваемых данных вдвое•Для бинарного поиска: =•2+ (1)Для мажорирующего элемента: =2∙2+ ()....

и так далее ........•Это распространённый подход•Как оценить асимптотическую сложность таких рекуррентностей?Master theorem•Применяется для решения рекуррентностей возникающих при D&C подходе+ •Пусть = •Тогда решения зависят от соотношения и log •Если > log , то = •Если = log , то = log •Если < log , то = log •Тут можно провести простое доказательство на доске, если его не было налекцияхПеремножение полиномов•Пусть даны = 3 + 3 2 + 4 + 7 и = 3 + 5 2 + + 4•Чем равно ∗ ?•Постарайтесь осознать КАК вы это подсчитали?Problem MP – перемножение полиномов•Пусть даны = 0 + ⋯ + и = 0 + ⋯ + •Вам необходимо подсчитать их произведение самым простым и очевиднымспособом: последовательно перемножая коэффициентыstruct Poly { unsigned n; unsigned *p; };struct Poly mult(struct Poly lhs, struct Poly rhs) {struct Poly ret = { rhs.n + lhs.n - 1, NULL };ret.p = calloc(ret.n, sizeof(unsigned));// TODO: ваш код здесьreturn ret;}•Оцените асимптотику получившегося алгоритма.

Можно ли сделать лучше?Перемножение: алгоритм Карацубы•Многие, в т. ч. Колмогоров, считали, что 2 это нижняя граница. До техпор, пока тогда ещё студент Карацуба не принёс Колмогорову лучшеерешение•Основная идея такая: пусть = 1 /2 + 0 и = 1 /2 + 0•Тогда = = 1 1 + 0 1 + 1 0 /2 + 0 0•Примените Master Theorem к реккурентности = 4•Но: = 1 1 +•Примените Master Theorem к реккурентности = 3•Домашнее задание: реализуйте алгоритм Карацубы для problem MP2+ ()1 + 0 1 + 0 − 1 1 − 0 0 /2 + 0 02+ ()Сортировка массива: наивный подход•У вас есть 300 не маркированныхгирек разного веса и весы•Вас просят разложить эти гири повесу в порядке возрастания•Как вы это сделаете?Идея сортировки вставками•Обычно первая идея, котораяприходит человеку этоотсортировать массив вставками•Инвариант алгоритма: левая частьмассива до n всегда отсортирована•На каждом шаге n увеличивается•При необходимости все красныеэлементы перемещаются•Какая асимптотическая сложностьу такого алгоритма?Алгоритм I – сортировка вставками•Реализация потребует двух функций, ключевой из которых являетсяmoveright, делающая сдвиг массива вправо, то есть к большим индексам,чтобы освободить позицию для вставкиunsigned moveright(int *arr, int key, unsigned last) {// TODO: напишите здесь код этой функции}void inssort(int *arr, unsigned len) {for (unsigned i = 0; i < len; ++i) {int key = arr[i];unsigned pos = moveright(arr, key, i);arr[pos] = key;}}Идея сортировки выбором•Вторая частая идея это сортировкавыбором•Найдём в массиве минимальныйэлемент и обменяем его местами стекущим•Переместимся к следующемуэлементу•Будет ли этот алгоритмасимптотически лучше вставок?Алгоритм SE – сортировка выбором•Алгоритм использует уже известный алгоритм Lunsigned linear_search(int const * parr, unsigned len, int elem);void swap(unsigned *v1, unsigned *v2) {unsigned tmp = *v1;*v1 = *v2;*v2 = tmp;}void selsort(int *arr, unsigned len) {// TODO: напишите здесь код для сортировки выбором}Об одной сомнительной идее•Может показаться заманчивым сортируя сравнивать соседние, обмениваяместами, если их взаимный порядок неправиленdo {int sw = 0;for (j = len - 1; j > 0; ++j)if (a[j - 1] > a[j]) {int tmp = a[j - 1]; a[j - 1] = a[j]; a[j] = tmp; sw = 1;}} while (sw == 1);•Это называется сортировка пузырьком (bubble sort)•Формально у него в среднем такая же асимптотика 2 , как у вставок ивыбора, но на практике он почти всегда крайне плохОбсуждение: bubble vs selection•Посмотрим на простом примере, почему одинаковая асимптотика неозначает одинаковое быстродействие01724653•Здесь selection sort сразу найдёт элемент и обменяет его с нужной позицией•Bubble sort тоже это сделает, но по дороге она сделает его обмены со всемиостальными элементами•Формально оба сделают для одного шага сравнений, но в реальностиречь идёт о разнице в разыСсылка на сравнение пузырька с insertion sortОбсуждение•Все простые сортировки: insertion, selection и bubble имеют довольно плохуюасимптотику 2 потому что в основном принимают только локальныерешения•Они элемент за элементом наращивают отсортированную часть массива•Гораздо более интересные результаты можно получить, если для сортировкитак или иначе разбивать массив на две части•Группа методов, которая так работает имеет общее название Divide & ConquerD&C подход: быстрая сортировка•Массив делится на две части по pivot(можно всегда выбирать первый)•Далее результаты разбиениясортируются отдельно тем жеспособом•В итоге массив собирается изотсортированных подмассивов2•Примените Master theorem к рекуррентности: = 2+ ()•Что можно сказать об асимптотике быстрой сортировки по сравнению с вставками?Алгоритм Q – быстрая сортировкаunsigned partition(int *arr, unsigned low, unsigned high) {// TODO: напишите код функции partition}void qsort_impl(int *arr, unsigned low, unsigned high) {if (low >= high) return;unsigned pi = partition(arr, low, high);if (pi > low) qsort_impl(arr, low, pi - 1);qsort_impl(arr, pi + 1, high);}void qsort(int *arr, unsigned len) {qsort_impl(arr, 0u, len - 1);}Средний и худший случай•На картинке ниже представленсредний случай•Как нарисовать картинку худшегослучая?Средний и худший случай•На картинке ниже представленсредний случай•Как нарисовать картинку худшегослучая?0 1 2 3 4 5 7 601 2 3 4 5 7 612 3 4 5 7 62•3 4 5 7 6Какая асимптотика у худшего случая?Обсуждение•Быстрая сортировка в худшем случае всё ещё ведёт себя как 2•Есть остроумные способы избежать на входе почти отсортированныхмассивов: например случайно перемешивать массив перед сортировкой•Можно ли придумать сортировку, которая всегда работает как log ?Сортировка слиянием•Делим массив на каждом шагепримерно пополам•Вовсе не обязательно при этомреально выделять новые массивы,можно просто хранить индексы•Далее сливаем получившиесяподмассивы и получаемотсортированные подмассивы•В отличии от сортировки выбором,у нас нет худшего случая, всегда = 2+ ()2Алгоритм M – сортировка слиянием•Вам, предлагается реализовать ключевой шаг: функцию слияния// сливает arr[l..m] и arr[m+1..r]void merge(int *arr, int l, int m, int r) {// TODO: ваш код здесь}void merge_sort_imp(int *arr, int l, int r) {if (l >= r) return;int m = (l + r) / 2;merge_sort_imp(arr, l, m);merge_sort_imp(arr, m + 1, r);merge(arr, l, m, r);}Обсуждение•Сортировать целые числа это весело и интересно, но что делать, если хочетсясортировать произвольные объекты?•Например можем ли мы написать такую функцию, которая могла быотсортировать и массив целых чисел и массив структур?Минимум о приведении•В языке C специальный синтаксис "val = (T)other" обозначает приведениеодного типа к другому.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций