bloody hands

a_d_astra

I give in to sin

because I like to practice what I preach


Previous Entry Share Next Entry
bloody hands
a_d_astra

Курс по алгоритмам, Coursera & Stanford University

Долго ждала, чтобы это написать. Не хотела рассказывать, пока мне не будет чем документально, так сказать, засвидетельствовать. Но не далее как сегодня утром оное свидетельство мне в почту и свалилось - аж как камень с плеч свалился. Вот такое:

Statement of accomplishment

Вот теперь, когда всё закончилось, можно и рассказать, как это было. А было оно отнюдь не просто, и кровушки у меня попило ой как много - устала дичайше, в сочетании с суровой работой-то. Я хотела ещё послушать курс по Machine Learning, но его запустили практически сразу после окончания этого - и я поняла, что если я сейчас ещё во что-то подобное буду залипать, то я просто свалюсь с какой-нибудь психосоматикой прямо посреди такого марафона. Посему, видимо, это будет в другой раз. А пока я по пунктам распишу, что и как было на курсе по алгоритмам, и что оно дало лично мне - вполне возможно, для кого-то это будет не менее полезным :)

Что я уже знала до того. К стыду моему, на деле не так уж и много. В школьные годы доводилось ездить на олимпиаду по информатике - там перед самой олимпиадой проводились лекции, и на одной из них как раз рассказывали про алгоритмы сортировки (в которых я тогда своими 15-летними мозгами поняла не так уж и много, позже эту тему уже прорабатывала самостоятельно). Самые базовые понятия теории графов и теории вероятностей я таки успела узнать в учебных заведениях на дискретной математике - но, увы, там было далеко не всё, что так или иначе мне тут понадобилось, пришлось срочно освежать и пополнять знания. Ещё у меня был купленный в те же 15 лет на деньги от подработки на рынке (и, блин, так и не дочитанный по сей день - до сих пор на полке стоит, аж в Питер привезла с Сахалина) учебник-задачник под названием "Основы программирования в задачах и примерах", где помимо прочего рассказывалось про простейшие структуры данных вроде стека и очереди. Собственно, всё - вот такой я была унылый быдлокодерок. Остальное уже пришлось учить практически с нуля.

Как был поставлен процесс. В общем и целом - очень похоже на другие подобные курсы, видеолекции - теоретические тесты - задачи на программирование. Но с лёгкими модификациями ввиду специфики материала. Если в курсе по SaaS технологии выбирались преподавателями, и надо было зааплоадить сам код, по которому гонялись функциональные и интеграционные тесты - то тут мы были целиком и полностью свободны в выборе того, на чём и как писать. Задания на программирование давались в виде самого вопроса, файла с исходными данными и поля, в которое надо было ввести конечный ответ. Причём какое-либо читерство там было невозможно в принципе - уже начиная с самого первого задания (подсчёт инверсий в массиве из 100000, кажется, чисел) объёмы данных были такими, что угадать ответ не представлялось возможным (а число попыток было ограничено, на каждое такое задание их было не более 5). Более того, ввиду объёма данных порой было совершенно нереально считерить и решить задачу неэффективным брутфорсным "быдло-способом". К примеру, было задание номер 4 - поиск сильно связанных компонентов в графе по алгоритму Косарайю. Надо было запостить число узлов в 5 самых крупных компонентах. Описание графа, на минуточку - файл размером в 70 мегабайт. Ты будешь, блин, добиваться решения задачи в обещанное линейное время - просто потому, что иначе прождёшь в лучшем случае час-другой (в худшем - всю ночь), пока тебе дадут ответ (и вовсе не факт, что он будет правильным, а попыток-то всего пять). Хорошая практика! Ну и были классические multiple choice тесты по теории, на которые давалось по 2 попытки. Тут уже приходилось брать листок бумаги и ручку, прорешивая задания и давая ответ.

Сами же лекции были достаточно приятны, в том плане, что преподаватель не пытался задавить интеллектом и авторитетом и не так уж и много "ругался умными словами". Многие вещи были объяснены куда более доходчиво и живо, чем ровно то же в книгах, но без потери "академической значимости" материала. Мне, к примеру, понравилось объяснение master method для оценки производительности алгоритмов класса "разделяй и властвуй" - преподаватель схохмил, рассказывая про оно как про "войну Добра и Зла" - где силами Добра было количество работы, совершаемое на каждом рекурсивном вызове, а силами Зла стало количество этих самых рекурсивных вызовов :)

Как это делала лично я. Как старая фанатка Ruby - писала домашки на нём. Опять же, по большей части из-за хороших возможностей для метапрограммирования и расширения уже имеющегося кода, дававших немалый выигрыш в скорости при написании и отладке - ну, к примеру, не знаю, как вам, а лично мне проще написать расширение к классу Array, и потом, не парясь, оттестить код в консоли интерпретатора так:

[1, 5, 2, 6, 3].count_inversions

... а не заморачиваться с наследованием и городить нечто вроде такого:

my_arr = Modified_Array.new([1, 5, 2, 6, 3]).
my_arr.count_inversions

Ну и читала спецлитературу, конечно. Обязательного текстбука к курсу не было, но было несколько опционально-рекомендованных. Из них я читала (и продолжаю читать по сей день в общественном транспорте) небезызвестный труд Кормена, Лейзерсона, Ривеста и Стайна - хотела даже купить, но, блин, тут уже пронаблюдала какое-то нездоровое охренение издателей по части цены - всё понимаю, но отдавать 50 с гаком баксов за электронный файл с DRM у меня, если честно, "жаба ква". Посему, каюсь, грешна - файл спиратила. Как будет хотя бы не очень кусачая цена - так куплю, а пока - читаю PDFку с коммуникатора. Но книжка всё равно очень годная и полезная, углубляет понимание многих вопросов из лекций. И я таки надеюсь сей монументальный труд из 1313 страниц дочитать!

Где я собой горжусь. А вот, пожалуй, именно в ходе выполнения того самого программистского задания про сильно связанные компоненты мой мозг поработал так, что я могу собой гордиться. Это задание сожрало у меня три полных дня (не вечера после работы, нет!), и в ходе выполнения оного я напоролась на все возможные (и наверняка специально расставленные преподавателем) грабли. Я упёрлась в то самое stack overflow при огромном количестве рекурсивных вызовов, не разруливаемое даже через ulimit - посему просто списать рекурсивный алгоритм с книжки тут было нереально, пришлось переписывать с нуля на свою итеративную реализацию стека. Я сдуру использовала встроенную функцию сложения массивов при определении порядка второго прохождения по графу - а оно таки давало лишнее O(n) при каждой итерации, и мне довелось изрядно почесать репу, пока я поняла, где именно лажа (а с первого взгляда всё казалось таким простым и логичным, да). И ещё много на что напарывалась, всего уже и не упомню. Но в конце концов я оно отшлифовала, оптимизировала - и получила вожделенный правильный ответ, на что по сей день не нарадуюсь. Да и вообще, как-то такие задания учат оптимизировать каждый шаг и выбирать эффективные структуры данных, чем, опять же, некисло прокачивают мозги. Пусть я вот сейчас смотрю на свой код и понимаю, что многое ещё можно улучшить - таки мне очень приятно, что я сие мозголомательное задание победила, и что я не только не сильно тупее студентов Беркли, я ещё и не сильно тупее студентов Стэнфорда!

Где я облажалась. Ну это достаточно хорошо видно по документу об окончании - облажалась я на экзамене, сдав его на троечку, и то как бы не с минусом. Причина в том, что там были вопросы, очень похожие на те, что присутствовали в домашних заданиях, но слегка, буквально чуть-чуть изменённые - ровно настолько, чтобы ответ был другим, не таким, как в домашних заданиях. К примеру, "каким должен быть граф, чтобы иметь возможность топологической сортировки" заменили на "каким должен быть граф, чтобы иметь единственную возможность топологической сортировки". Я типа умная - "а, да я же уже это решала, я знаю ответ!" - и, конечно же, на вот это самое слово внимания и не обратила. И ответ, разумеется, дала неправильный. И вот так ошиблась ещё на нескольких вопросах - по закону подлости, не так уж и много вопросов я зафейлила, но вот именно те, на которые я ответила неправильно, стоили больше всего баллов. Мораль: надо быть внимательнее, конечно, а самонадеянность сильно вредит делу.

Но в общем и целом итог прохождения курса не так уж и плох. При всём моём перфекционизме и "синдроме отличника" в тяжёлой форме - в общем-то, быть по общему результату пусть и не отличником, но хотя бы вполне себе хорошистом меня устраивает. Good enough. Ибо знание этих вещей таки хорошо прокачалось, и многое по работе стало пониматься куда лучше и на куда более глубоком уровне. Когда в переписке с технарями заказчика, поставляющими нам API, можно со знанием дела заявить, что "ваши записи не грузятся в ExtJS-овское дерево, потому что ваша хэш-функция для формирования айдишников даёт коллизии" - это гораздо приятнее, чем пытаться объяснить то же самое "на пальцах", чувствуя себя при этом тем ещё быдлокодером :)

И, как и в курсе по SaaS, cамое вкусное тут - то, что это действительно не весь оригинальный курс из Стэнфорда, а только его первая часть. Вторую, с более продвинутым материалом, обещают ближе к концу лета - обязательно заслушаю! Ну и вот эту первую вскорости повторят - что я, думаю, тут ещё пропиарю. А там уже можно будет и изучать суровые предметные области вроде вышеупомянутого machine learning. И, да - очень классно, что такие хорошие и крутые учебные программы мирового класса теперь доступны для всех, несмотря на весь "звериный капитализм" в сфере образования - я искренне благодарна университетам и проекту Coursera за такую возможность.Так что, дамы и господа, stay tuned - и не забывайте, что там говорил Владимир Ильич Ленин по поводу "учиться, учиться и ещё раз учиться"!

P.S., просто забавы ради. Учитывая, что с формальным образованием в родных пенатах у меня как-то не складывалось (а если бы и складывалось - вот именно этих вещей там всё равно не проходили), а профессиональную литературу на русском языке я даже не могу точно вспомнить, когда в последний раз читала - получается очень забавно, когда все эти вещи надо так или иначе объяснить по-русски. Особенно смешно было, когда на одной программистско-алкогольной посиделке-междусобойчике сижу вся такая я, слушающая вот эти вот лекции и читающая Кормена с компанией... а напротив меня сидит собеседник, приехавший из места, по сравнению с которым мой родной Корсаков - мегаполис, учившийся совсем не на программиста, но очень сильно втыкающий в тему (я порой себя в разговоре чувствовала блондинкой) и в данный момент читающий Седжвика (тоже по-английски, естественно). После долгих и бесплодных попыток объяснить по-русски, чем я вообще тут с этими домашками занимаюсь, и что ещё имеет смысл почитать, оба уже в конце концов плюнули - "да хватит уже фигнёй страдать, let's speak English!" Неспроста в лекциях упоминались разговоры на nerdiest cocktail parties! :)


  • 1
Уважаю безмерно!
Меня так и не хватило ни на один из курсов. Начинаю и бросаю, не говоря уже о домашних задания.
Ты прекрасна!

Щас покраснею :) За комплимент всячески благодарю, да - но вот чисто интереса ради, а почему не получается закончить ни один из курсов? Тяжело слушать лекции на английском?

Нет, не тяжело. У меня обычно много дел по научным проектам, которые требуют умственных ресурсов. На курсы идёт по остаточному принципу. В общем, не получается, хотя эти знания нужны и важны.

Большое спасибо этот за отзыв. Он оказался весьма полезным при прохождении курса.

  • 1
?

Log in