[Перевод] Сложные проекты для программистов, чтобы учиться новому
В основном я учился программированию самостоятельно. Когда у меня появлялась захватывающая идея, я разбирался, что необходимо для решения этой задачи. Например, когда я заинтересовался работой поисковых движков, то начал читать о вычислительной эффективности множеств. Так я обнаружил задачу «как понять, что я уже выполнил краулинг этого URL?», если их уже были тысячи. Чтобы ускорить ответ на этот вопрос, я использовал множество, поиск по которому занимает O (1), а не O (n).
Изучение того, что нужно для решения задачи, увлекательно, но при движении по собственному пути в кодинге в твоих знаниях остаются пробелы. Мне кажется, что если постоянно ставить перед собой сложные задачи, то эти пробелы будут заполняться по ходу. (Даже если это займёт больше времени, чем при прохождении курса. Интерес — важный мотиватор движения вперёд; стремитесь к тому, что любопытно вам.)
В тот момент, когда я начал понимать вычислительную эффективность и стремиться к ускорению своих программ, я как раз решал задачу, связанную с поисковым движком. С тех пор я иногда задаюсь вопросом: что стоит сделать дальше? Каким будет моё следующее сложное задание? Это сильно зависит от имеющихся у вас на текущий момент знаний; некоторые идеи имеют смысл, другие пока недостижимы. Так мы и учимся.
Я решил составить собственный список проектов, поддерживающих мой интерес к программированию. Это список в стиле серии Challenging projects every programmer should try Остина Хенли.
Создать поисковый краулер
Краулер — это бот, ходящий по веб-страницам и сохраняющий их содержимое. Краулеры используются поисковыми движками для исследования веба. Содержимое веб-страниц «индексируется». Это означает, что страницы куда-то сохраняются для дальнейшего поиска по ним.
Я решил создать поисковый движок для небольшого сообщества, в котором участвую. Сообществу был известен список из примерно тысячи сайтов, составленный людьми, делающими вклад в общую wiki. Я использовал его как список для краулинга. Вы можете составить собственный список сайтов и написать свой поисковый движок. Допустим, можно сделать поисковый движок по своим любимым аниме-блогам. Или фан-сайтам Тейлор Свифт. Всего, чего угодно, если только это есть в вебе.
Самым важным открытием для меня в этом процессе стало то, что веб — это Дикий Запад. Никогда нельзя ожидать, что чья-то веб-страница будет именно такой, какая нужна вам. Создание поискового краулера — это упражнение, обучающее нас надёжным образом получать максимально возможное количество веб-сайтов, и чтобы при этом сайты не валились.
При создании поискового краулера вы узнаете:
Как скачивать веб-страницу
Стандарты краулинга контента (robots.txt, тэги meta «взрослого» контента)
Об ограничениях частоты опросов
Об экспоненциальных выдержках
Когда выполнять краулинг и повторный краулинг сайтов
О content negotiation
Об Etag
И обо многом другом
Веб и в самом деле Дикий Запад. Но у этого Дикого Запада есть множество восхитительных технически сложных задач, которые можно решить. Эта задача занимала мой мозг несколько месяцев. Хотя мой поисковый движок уже неактивен, этот проект придал мне уверенности в том, что я могу сделать нечто большее, чем написание крошечных скриптов на Python.
Создать систему автоматического завершения
Представьте, что вы пишете пост для блога. Как можно автоматически завершать слова на основании последовательности букв? Возьмём для примера эту статью. Если я начал слово с «экспонен», то как можно эффективно предложить «экспоненциальных» в качестве готового слова? В этом и заключается сложность. Я не буду подробно рассказывать о внутреннем устройстве этого проекта, но при его создании я получил много удовольствия!
Когда поймёшь, как автоматически завершать слова, возникает ещё одна сложность: как рекомендовать, какое слово завершать автоматически. Если я введу «экспоне», то как алгоритм автоматического завершения узнает, рекомендовать ли «экспонента» или «экспоненциальных»?
Нaписать программу для сжатия файлов
Существует множество замечательных инструментов, сжимающих файлы, но задавались ли вы когда-нибудь вопросом, как они уменьшают эти файлы?
Вот вам задание: скачайте оригинал статьи как файл HTML. Напишите программу, создающую сжатую версию файла HTML. Ваша программа должна уметь воспроизводить файл в точности. Всё должно остаться таким же, включая пробелы и заглавные буквы.
Вот некоторые из тем, которые могут вам пригодиться в изучении этой области (хотя если вам интересна эта задача, то рекомендую попробовать написать программу сжатия, не читая особо много об этом!):
Теория информации
Метод сжатия с использованием словаря (способ описания информации)
Код Хаффмана (популярный алгоритм сжатия)
Энтропия (мера величины «информации» в файле; «информация» намеренно поставлена в кавычки)
Реализовать BitCask
BitCask — это алгоритм хранения ключей и значений. Хранилища ключей и значений сопоставляют ключи (имена) с значениями (блоками информации). Например, я бы мог хранить информацию о постах в своём блоге так:
{"title": "(Even more) challenging programming projects you should try", "published": "2024-02-28"}
Где title и published — это имена, связанные со значениями.
BitCask работает только с использованием вашей файловой системы. Ключи и значения сохраняются в файлы. В каждый файл можно только добавлять информацию. Можно удалять ключи, но при этом переопределяется старый ключ, а не явным образом удаляется значение. Документация по BitCask — это короткая и полезная статья, помогавшая мне при реализации алгоритма. Задача для вас:
Создать cask (хранилище ключей и значений на основе алгоритма BitCask)
Добавить элементы в cask
Извлечь элементы из cask
Удалить элементы из cask
Закрыть cask
При закрытии cask выполняется операция слияния, объединяющая все файлы cask в один.
Написать язык программирования
Ого, ничего себе! Язык программирования? Только серьёзные специалисты способны на такое! Я тоже так думал. Но оказалось, что это неправда! Вы тоже можете создать язык программирования. И прежде чем приступить к этому, даже не нужно читать сотни страниц литературы по теории (однако чем больше вы читаете, тем больше информации у вас будет для проектирования своего языка!).
Проектирование языка программирования позволяет вам решать, как именно вы хотите писать код. Можно воспользоваться готовыми паттернами или придумать собственный. Правила пишете вы сами.
Существует множество типов языков программирования, но лучше всего начать с написания языка, не требующего компилятора. Возможно, я пристрастен, потому что сам так учился, но мысль о необходимости писать компилятор, прежде чем у меня появится чуть больше опыта в теории языков программирования, казалась мне пугающей. Поэтому я написал «интерпретируемый» язык. Файл считывается, парсится, затем исполняется; никакой компиляции.
Интерпретируемый язык состоит из нескольких основных элементов:
«Грамматики», определяющей структуру языка;
«Лексического анализатора»/«парсера», получающего произвольный текст (например, скрипт, написанный на вашем языке!) и превращающего его в абстрактное синтаксическое дерево (Abstract Syntax Tree, AST) на основании вашей грамматики;
Системы символьных выражений, считывающей синтаксическое дерево и выполняющей с ней какие-то операции.
Каждый из перечисленных выше трёх компонентов представляет собой отдельную техническую сложность. Я рекомендую начинать с написания грамматики и парсера. Ваша грамматика будет определять, как работает язык (то есть как объявлять переменные, список разрешённых и запрещённых символов, то, как работает или не работает вложенность). Для интерпретации грамматики можно использовать готовый лексический анализатор. Я воспользовался Lark для Python. Система символьных выражений будет брать синтаксическое дерево и применять логику программы (то есть хранить переменные, выполнять математические вычисления, работать со строками и булевыми значениями и делать всё то, что вы захотите от языка).
P.S. Неплохо также начать с языка Lisp!
Сам список и другие идеи, которые в нём могут быть
Приведённый выше список — это не обязательный чек-лист, а, скорее, источник вдохновения для выбора своих проектов. Возможно, один из пунктов вдохновит вас что-нибудь сделать. Возможно, ни один из них вас не заинтересует. Это тоже нормально. Если так случилось, то рекомендую сохранить этот пост где-то глубоко в сознании. Возможно, настанет день, когда одна из идей понравится вам. Пять лет назад я бы, наверно, посчитал представленный выше список слишком сложным. Год назад я бы мечтал его реализовать.
Я рекомендую поискать интересные идеи в статье Остина Хенли. Именно благодаря его посту я написал свой.
Если после прочтения этого поста вы реализуете что-то, то сообщите мне! Напишите письмо на readers [at] jamesg [dot] blog. Кроме того, если вам нужна помощь с представленными выше идеями, тоже пишите, буду рад помочь. Я выполнил все перечисленные здесь задачи; они продолжают культивировать моё детское восхищение кодингом; надеюсь с вами будет так же.
Теперь вопрос: какие ещё идеи должны быть в этом списке? Что, по вашему мнению, было бы отличной сложной задачей для программистов?
