Технотрек: Занятие 02: Указатели тоже бросаются вызовами

Summary

На лекции мы разобрали типичные случаи, трудные для тех, кто раньше не писал на Си. В Си есть явное понятие адреса; это прекрасно, но есть и сложности. Главный инструмент для понимания того, что происходит - рисовать детальную структуру памяти, с обозначением на ней всех массивов, переменных и их адресов. Не ленитесь рисовать! Абсолютно все при этом станет понятно, и код?кот станет белым и пушистым.

Домашнее задание
Collapse )

Технотрек: Занятие 01: Start() { Квадратное уравнение бросает вызов; }


(Копия блога на Технотреке)

Привет!

В понедельник 18 сентября торжественно состоялось первое занятие курса по промышленному программированию на С/С++.

Квота на зачисление была 55 человек. Отбор происходил по задачам на программирование и логическим тестам.

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

Summary
Collapse )

Технотрек: Занятия 09, 10: Рекурсивный спуск


(Копия блога на Технотреке)

Summary

На лекции мы рассмотрели восстановление дерева из записи, в которой взаимоотношение узлов задано неявно, с помощью приоритетов операций, в более общем случае - с помощью грамматики. Эта задача называется синтаксическим анализом. Одно из ее решений - метод рекурсивного спуска. Несмотря на то, что он достаточно прост, к сожалению, в сети нет внятных его описаний. Поэтому на лекции мы рассматривали много примеров, рисовали деревья синтаксического разбора и читали мантры. :) Хорошая метафора рекурсивного спуска - работа строительной бригады, устроенной наподобие этого:



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

Домашнее задание
Collapse )

Технотрек: Занятия 07, 08: Построить проект, вырастить дерево, родить левого или правого сына


(Копия блога на Технотреке)

Summary

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

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

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

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

Домашнее задание

Collapse )

Технотрек: Промышленное программирование. Занятие 07: Внезапно лаба (хеши и списки)


(Копия блога на Технотреке)

Summary

Односвязные и двусвязные списки и хеш-таблицы - классика структур данных, но для них важны правильная реализация и правильное использование. Список возникает как решение противоречия между физически линейным непрерывным размещением объектов в памяти (массив) и необходимостью быстрой вставки/удаления в среднюю часть последовательности. При этих операциях элементы массива неотвратимо надо сдвигать; на это уходит время. Мы отказываемся от того, что логически последовательные элементы будут физически последовательно (смежно) лежать в памяти, теряем формулу быстрого вычисления номера следующего элемента (n+1) и заменяем ее номером или указателем, хранящимся в самом элементе. Теперь мы можем размещать элемент в памяти где угодно, не заботясь о смежности с другими элементами и не делая сдвиги. Это и есть идея списка.

Заметим, что если нужны быстрые вставки/удаления только в начало или конец последовательности, то подойдет обычный массив. Если нужны быстрые вставки/удаления только с началом и с концом последовательности (но не с ее средней частью), достаточно кольцевого буфера. Если все же нужно реализовывать список, то лучше сразу двусвязный: памяти это займет немного больше, но все операции у него быстрые, не зависят от длины последовательности.

Одна из ужасных ошибок использования списков - непонимание того, что индексация у них кошмарно медленная. Это линейный поиск элемента в плохо кешируемом цикле, что практически так же медленно, чем поиск элемента по значению. Как у strlen(), только значительно хуже. Вот пример такого плохого кода:
for (int i = 0; i < List_Size (&list); i++)
    {
    const ListElement* elem = List_ElementAt (i);  // Та самая индексация
    ListElement_Dump (elem);
    }
Этот цикл - квадратичный по времени. Квадратичный, Карл! Не делайте так.

Правильно:
for (const ListElement* elem = List_Begin (&list); elem != NULL; i < List_Next (elem))
    ListElement_Dump (elem);
Сравнение линейных структур данных:

Collapse )

Технотрек: Промышленное программирование. Занятие 06: The Процессор, continued


(Копия блога на Технотреке)

Summary

В этот раз мы разобрали работу с адресами с помощью меток. Они используются в качестве синонимов адресов кода или данных (переменных). Важно понимать, что процессор с метками дело не имеет, он работает только с адресами. С метками работает только ассемблер, он переводит их а адреса. Это часто путают.

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

Домашнее задание

Collapse )